[C++] 프로그래머스 124 나라의 숫자

programmers.co.kr/learn/courses/30/lessons/12899

코딩테스트 연습 - 124 나라의 숫자

 

1. 서론

 

3진법을 활용해서 푸는 문제. 솔직히 너무 어려웠다 ㅎㅎ 

 

2. 문제 풀이

 

1, 2, 4 만을 활용해서 숫자를 표현하는 문제이다. 3진법이 0, 1, 2만 사용해 숫자를 표현하는 것과 유사하다. 0이 4로 바뀐 거로 봐도 된다. 다만 0, 1, 2처럼 일정한 숫자 패턴이 아니기 때문에 단순하게는 풀 수 없다.

 

처음에는 숫자를 쭉 늘어놓고 수동으로 변환해서 쭉 써놓고 규칙을 찾으려고 노력했다. 주어지는 숫자의 500,000,000이기 때문에 1부터 구현하면 100% 시간초과가 나기 때문이다. 처음에 바로 3진법을 떠올리진 못했고 숫자로 패턴을 찾기 위해 조합을 찾아보다가 눈치챈 게 1, 2, 4 세 개의 숫자를 돌아가면서 쓰기 때문에 숫자 3개를 기점으로 규칙이 바뀌며 3으로 나누었을 때 나머지가 0이면 맨 뒤의 자리가 4, 1이면 1, 2면 2로 끝나는 걸 보고 3진법에 대한 것을 눈치챘다.

그런데 그냥 0을 4로 대치한다고 문제는 풀리지 않는다. 그래서 처음에 숫자를 쪼개다가 알아낸게 3개를 기점으로 바뀌는데 3으로 나눈 경우 나머지가 0인 경우는 앞자리 숫자가 혼자 다르게 나오는 것이 문제였다.

 

예를 들어

 

16 121

17 122

18 124

 

1,2,4의 규칙대로 변환하면 이렇게 나와야 하는데 3으로 그냥 나눴을 경우에는

 

16 121

17 122

18 200

 

이런 식으로 나오는 것이다. 나는 이 문제를 해결하기 위해서 처음에 200 중에서 마지막자리 0은 4로 대치하고 20의 부분은 16의 앞자리 두 개를 따오게 바꿨다. 주어진 테스트 케이스에서는 문제가 없었는데 돌렸을 때는 역시 문제가 생겼다. 그래서 질문하기를 둘러봤는데 거기에서 어떤 테스트 케이스를 봤다. 513을 넣었을 때 124224가 나오는지 보라는 것이다. 내 코드로 돌리자 224는 맞게 나왔는데 앞에 124 부분이 200으로 나와버린 것이다... 위의 18의 케이스와 같은 경우인데 이렇게 숫자가 큰 경우는 생각하지 못하고 대충 꼬랑지만 처리하다 보니 문제가 생긴 것이다.... 나는 고민에 빠졌다. 이 코드를 아예 날리는 게 맞는 것인지. 아니면 수정해서 풀어야 하는지. 이렇게 앞자리와 뒷자리를 조악하게 합쳐서 푸는 건 아니라고 판단했고 문제 전체를 관통하는 알고리즘이 필요했다.... 

 

그러다 질문하기에 누가 글 제목 자체를 이렇게 써놓은 것을 봤다. 그냥 3진법으로 푸는건데 3으로 나누어 떨어지는 경우에 -1씩 해주면 되는 거네요. 이런 식으로 써놨다. 나는 그때 그 말을 잘못 이해했다. 내 코드랑 논리가 똑같은데 어떻게 푼 거야?라는 생각이 들었다. 왜냐면 나도 3으로 나눴고 3으로 나누어 떨어질 때 앞의 숫자랑 맞춰서 앞자리를 대치해줬으니까. 근데 나는 완전 잘못 이해하고 있었다. 

 

*** 여기서부터 진짜 풀이 ***

 

이 문제와 3진법의 차이는 0이 4인 것이다. 즉 3으로 숫자가 나누어 떨어졌을 때 처리를 따로 해줘야 하는 것이다.

의외로 간단하게 처리할 수 있다. 숫자가 3으로 나눴을때 0으로 나누어 떨어진 경우에는 그 자리에 그냥 4를 넣어주는 것이다. 여기까지는 누구나 쉽게 생각할 수 있지만 다음 부분에서 놀랐다. 4를 넣어주고 주어진 숫자를 3으로 나눈 후 -1 하는 것이다.

이해는 했지만 다시 돌아가서 풀더라도 난 이 방법은 생각해내지 못할 것 같다. 내가 생각했던 -1과 어찌 보면 한끝차이기도 하지만 전혀 다른 발상이라서... 내가 생각했던 -1은 그냥 큰 숫자를 한 번만 -1 하는 것이고, 이 풀이법은 나눌 때마다 나머지가 0으로 나누어 떨어지면 4를 넣고 -1을 해버리는 것이다... 약간의 충격^^

 

스케치

진짜 별 짓을 다했다^^...

 

 

3. 코드 설명

 

#include <string>
#include <algorithm>

using namespace std;

string solution(int n) {
    string answer = "", s = "";
    int x = 0;
    
    while(n > 3)
    {
        x = n % 3;
       
        if (x == 0)
        {
            n = n / 3 - 1;
            s = '4';
        }
        else
        {
            n /= 3;
            s = x + '0';
        }
        answer += s;     
    }
   
    if (n == 3)
        n = 4;
    answer += n + '0';
    reverse(answer.begin(), answer.end());
    
    return answer;
}

 

n이 3보다 큰 경우 반복문을 돌린다. n을 3으로 나누는데 나누어 떨어지는 경우에는 위에서 말한 것처럼 n을 3으로 나눈 것에서 -1 한다.

그리고 바로 4를 넣어 준다. 나머지의 경우에는 그냥 3으로 나누고 나머지 값을 answer 문자열에 넣는다.

반복문을 돌리는 조건이 n > 3이었기 때문에 n이 3인 경우 0 -> 4로 대치 해주고 남은 n을 answer 문자열에 추가한다.

그리고 나눈 순서대로 1의자리부터  문자열이 들어가기 때문에 다시 역순으로 문자열을 뒤집어서 return 해준다.