Pelikan's Glide

/home

/posts

/about

Home/Posts/ 키패드 누르기

키패드 누르기

2020 카카오 인턴쉽 기출문제

  ·  6 min read

#Cpp #Algorithm #Programmers #Kakao

문제 설명 #

스마트폰 전화 키패드에서 숫자를 입력할 때, 왼손과 오른손의 엄지손가락만을 이용하여 숫자를 입력하려고 합니다. 엄지손가락을 사용하는 규칙에 따라, 순서대로 눌러야 할 번호를 담은 배열 numbers와 사용자 손잡이 정보 hand가 주어졌을 때, 각 번호를 누른 손을 나타내는 문자열을 반환하는 문제입니다.1

입력 규칙 #

  1. numbers: 누를 번호가 담긴 정수 배열.
    • 크기: 1 이상 1,000 이하.
    • 값: 0 이상 9 이하.
  2. hand: 문자열로 사용자의 주 사용 손을 나타냄.
    • "left": 왼손잡이.
    • "right": 오른손잡이.

동작 규칙 #

  1. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며, 키패드 이동 한 칸은 거리로 1에 해당합니다.
  2. 왼쪽 열 (1, 4, 7)은 왼손 엄지손가락으로만 누릅니다.
  3. 오른쪽 열 (3, 6, 9)은 오른손 엄지손가락으로만 누릅니다.
  4. 가운데 열 (2, 5, 8, 0)은 두 엄지손가락의 현재 위치에서 가까운 손으로 누릅니다.
    • 거리가 같으면, 사용자의 주 사용 손(hand)으로 누릅니다.

출력 규칙 #

  • 왼손 엄지손가락을 사용한 경우 "L", 오른손 엄지손가락을 사용한 경우 "R"을 반환합니다.
  • 반환 형식은 문자열로, 숫자를 누른 순서에 따라 연속된 형태로 나타냅니다.

입출력 예시 #

예시 1

  • 입력
    numbers = [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5]
hand = "right"
  • 출력
    "LRLLLRLLRRL"

예시 2

  • 입력
    numbers = [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2]
hand = "left"
  • 출력
    "LRLLRRLLLRR"

예시 3

  • 입력
    numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
hand = "right"
  • 출력
    "LLRLLRLLRL"

동작 예시 #

왼손 위치오른손 위치눌러야 할 숫자사용한 손설명
*#1L1은 왼손으로 누릅니다.
1#3R3은 오른손으로 누릅니다.
134L4는 왼손으로 누릅니다.
……………

문제 나누기 #

문제를 처음 보고 아래와 같은 단계로 문제를 나누었다.

  1. numbers에 있는 숫자 중 왼쪽 열 또는 오른쪽 열에 있는 숫자인 경우 y값을 기록 후 answer에 L 또는 R을 추가한다.
  2. numbers에 있는 숫자가 중앙에 있는 숫자인 경우 가까운 손의 엄지로 누른다.
    • 만약 오른손과 왼손 모두 y값이 동일한 경우 hand값에 따라 손을 결정한다.

하지만 위와 같이 문제를 나누어 구현하였으나 거리를 구할 때 엄지손가락의 x, y 위치 값이 모두 필요함을 깨달았다. 따라서 아래와 같이 x, y 값 모두 갱신되도록 함수를 작성하였다.

bool checkLeftNumber(int number);
bool checkRightNumber(int number);
bool checkMiddleNumber(int number);
int getPosY(int number);
int getPosX(int number);
void readPosition(int number, int& pos_y);
std::string decideHand(int number, std::pair<int, int>& left, std::pair<int, int>& right, std::string hand);

문제 해결하기 #

#include <string>
#include <vector>
#include <iostream>
#define X first
#define Y second

bool checkLeftNumber(int number);
bool checkRightNumber(int number);
bool checkMiddleNumber(int number);
int getPosY(int number);
int getPosX(int number);
void readPosition(int number, int& pos_y);
std::string decideHand(int number, std::pair<int, int>& left, std::pair<int, int>& right, std::string hand);

std::string solution(std::vector<int> numbers, std::string hand) {
    std::string answer = "";
    auto left = std::make_pair(0,3);
    auto right = std::make_Pair(2,3);
    
    for(auto& number: numbers){
        if(checkLeftNumber(number)){
            readPosition(number, left.Y);
            left.X = 0;
            answer += "L";
        }else if(checkRightNumber(number)){
            readPosition(number, right.Y);
            right.X = 2;
            answer += "R";
        }else if(checkMiddleNumber(number)){
            answer += decideHand(number, left, right, hand);
        }else{
            continue; // 키패드에 존재하지 않는 숫자
        }
    }
    return answer;
}

bool checkLeftNumber(int number){
    if(number == 1 || number == 4 || number == 7) return true;
    return false;
}

bool checkRightNumber(int number){
    if(number == 3 || number == 6 || number == 9) return true;
    return false;
    
}

bool checkMiddleNumber(int number){
    if(number == 2 || number == 5 || number == 8 || number == 0) return true;
    return false;
}

int getPosX(int number){
    if(checkLeftNumber(number)) return 0;
    else if(checkMiddleNumber(number)) return 1;
    else return 2;
}

int getPosY(int number){
    if(0 < number && number < 4) return 0; // 1 <= num <= 3
    else if(4 <= number && number < 7) return 1; // 4 <= num <= 6
    else if(7 <= number && number < 10) return  2; // 7 <= num <= 9
    else return 3; // num == 0
}

void readPosition(int number, int& pos_y){
    pos_y = getPosY(number);
}


std::string decideHand(int number, std::pair<int, int>& left, std::pair<int, int>& right, std::string hand){
    auto number_pos = std::make_pair(getPosX(number), getPosY(number));
    int left_distance = std::abs(number_pos.first - left.first) + std::abs(number_pos.second - left.second);
    int right_distance = std::abs(number_pos.first - right.first) + std::abs(number_pos.second - right.second);
    if(left_distance == right_distance){
        if(hand == "right"){
            right = {number_pos.X, number_pos.Y};
            return "R";
        }else{
            left = {number_pos.X, number_pos.Y};
            return "L";
        }
    }else if(left_distance < right_distance){
        left = {number_pos.X, number_pos.Y};
        return "L";
    }else{
        right = {number_pos.X, number_pos.Y};
        return "R";
    }
}

문제 나누기에서 계획한대로 구현하기만하면 풀 수 있는 문제였다.

고칠점 생각해보기 #

논리 개선하기

문제에서 check**Number 함수는 숫자의 크기를 3으로 modulo 연산과 division 연산을 통해 개선할 수 있음 알 수 있다. 또한 이로 인해 getPosX와 getPosY도 간단화시킬 수 있다.

가독성 개선하기

함수의 이름이 명확하지 않다. 왜 중앙열에 있는 숫자들은 decideHand라고 작성했는지 다시봐도 잘 이해가 되지 않는다. 함수명의 경우 코테 중간에는 수정하거나 교체하는것이 쉽지가 않으므로 처음부터 논리를 잘 계획하고 함수를 잘 쪼갠 뒤 그 역할에 알맞는 함수의 이름을 작성해야됨을 느꼈다. 그렇다면 문제 나누기에서 작성했던 함수명을 더욱 알맞게 고쳐보면 아래와 같다.

bool checkLeftNumber(int number);
bool checkRightNumber(int number);
bool checkMiddleNumber(int number);
int getPosY(int number);
int getPosX(int number);
void updateThumbPosition(int number, int& pos_y);
std::string chooseHandAndupdateThumbPositionWithCentralNumber(int number, std::pair<int, int>& left, std::pair<int, int>& right, std::string hand);

마지막 chooseHandAndupdateThumbPositionWithCentralNumber 함수의 경우 이름에서부터 하나의 역할이 아닌 최소 2개의 역할을 하고 있음을 알 수 있다. 따라서 해당 함수는 2가지로 다시 나누어 최적화할 필요가 있다.

  1. 각 엄지의 위치 거리를 통해 이동해야 할 손을 결정하는 함수
  2. 해당 손의 엄지 위치를 갱신하는 함수

사실 더 명확하게 거리 계산과 이동해야 할 손을 결정하는 것까지도 나눌 수 있다.

코테에서의 함수 사용에 대한 단상 #

명확하게 이해를 한 뒤 최대한 잘게 기능을 나누어 함수를 작성하면 문제를 조금 더 쉽게 풀 수 있음을 최근 느끼고 있다. 하지만 알고리듬 테스트의 경우 최소 시간 복잡도와 공간 복잡도로 문제를 푸는것이 핵심이다. 하지만 이렇게 함수로 모든 기능을 나누는 것이 알맞은 코딩인지는 잘 모르겠다.

풀이 개선하기 #

#include <string>
#include <vector>
#include <cmath>

std::pair<int, int> getPosition(int number) {
    if (number == 0) return {1, 3};
    return {(number - 1) % 3, (number - 1) / 3};
}

std::string solution(std::vector<int> numbers, std::string hand) {
    std::string answer = "";
    std::pair<int, int> left = {0, 3}, right = {2, 3}; // 초기 위치
    bool isRightHanded = (hand == "right");

    for (int number : numbers) {
        std::pair<int, int> target = getPosition(number);

        if (target.first == 0) { // 왼쪽 열
            answer += "L";
            left = target;
        } else if (target.first == 2) { // 오른쪽 열
            answer += "R";
            right = target;
        } else { // 가운데 열
            int leftDistance = std::abs(target.first - left.first) + std::abs(target.second - left.second);
            int rightDistance = std::abs(target.first - right.first) + std::abs(target.second - right.second);

            if (leftDistance == rightDistance) {
                if (isRightHanded) {
                    answer += "R";
                    right = target;
                } else {
                    answer += "L";
                    left = target;
                }
            } else if (leftDistance < rightDistance) {
                answer += "L";
                left = target;
            } else {
                answer += "R";
                right = target;
            }
        }
    }

    return answer;
}

Refernces #

  1. “코딩테스트 연습 - 키패드 누르기,” 프로그래머스 스쿨. https://school.programmers.co.kr/learn/courses/30/lessons/67256 ↩︎

←
HTTP API
성격 유형 검사하기
→
back to top