[C++] 프로그래머스 3진법 뒤집기

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

코딩테스트 연습 - 3진법 뒤집기

 

1. 서론

 

level 1의 문제이다. 간단해 보이면서도 생각하기가 조금 어려웠다. '3진법을 어떻게 구현할 것인가'가 관건이다.

3진법만 구현하면 어렵지 않다.

 

2. 문제 풀이

 

입력된 숫자를 3진법으로 변환 후, 그 변환된 수를 역순으로 뒤집어서 다시 10진법으로 바꾸는 문제이다.

 

예를 들어 10진법으로 45라는 숫자가 있다. 이것을 3진법으로 변환하면 1200이 된다. 그리고 이것을 역순으로 뒤집으면 0021이 된다. 이 0021을 다시 3진법으로 변환하면 7이 된다. 그렇다면 답은 7이다. 

 

처음에는 3진법으로 어떻게 변환해야 하지? 그것부터가 문제였다. 학부시절 2진법으로 바꾸는 문제는 수도 없이 풀었지만 너무 오래돼서 2진법으로 변환하는 방법조차 까먹었다. 뭔가 나누고 나머지를 활용했던 것만 기억났다. 그래서 그걸 활용했다.

 

예시인 45를 활용해보면

 

45 / 3 = 15 ... 0
15 / 3 = 5 ... 0
5 / 3 = 1 ... 2

 

이렇게 3진법을 변환할 수 있는데, 이렇게 하면 3진법을 역순으로 뒤집을 필요도 없다. 저 나머지를 순서대로 저장하면 되기 때문이다. 

그렇게 나머지가 나오는 순서대로 저장하면 자동으로 역순이다. 

 

0 0 2 1

 

저 순서대로 나머지를 저장하고 3진법으로 변환해주면 된다.

 

3. 코드 설명

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(int i, int j)
{
    return i > j;
}

int solution(int n) {
    int answer = 0, i = 0, t = 1, j;
    vector<int> v, x;
 
    while(1)
    {
        if (n < 3) 
        {
            v.push_back(n);
            break;
        }
        
        v.push_back(n % 3);
        n /= 3;
    }

    x.push_back(t);
    for (i = 1; i < v.size(); i++)
    {
        t *= 3;
        x.push_back(t);
    }
    
    sort(x.begin(), x.end(), compare);
    
    for (i = 0; i < v.size(); i++)
        for (j = 0; j < v[i]; j++)
            answer += x[i];

    return answer;
}

 

v는 3진법을 담는 배열, x는 3의 배수를 저장하는 배열이다. 

while문에서 3진법으로 변환을 해준다.

 

나 같은 경우에는 break를 거는 조건 때문에 조금 고생했다.

처음에는 단순하게 n == 1인 경우에 멈췄는데 n == 1 이 아닌 경우에 무한루프에 빠져 메모리 초과가 발생했다.

n을 3으로 나누다 보면 마지막엔 결국 1일 거라고 생각했는데 1일 수도 있고 0일 수도 있다. 3보다 작은 경우도 있기 때문이다.

그래서 n < 3으로 조건을 바꾸니 테스트 케이스를 전부 통과했다. 

 

x에는 v의 size만큼 3의 배수를 계산해 넣었는데 3의 0승도 포함이기 때문에 미리 1을 넣어주고 i를 1부터 시작했다.

그리고 sort 함수를 이용해서 내림차순으로 3의 배수의 순서를 바꿔줬다. 3진법을 역순으로 계산해야 하기 때문이다.

compare 함수는 정렬을 내림차순으로 하게 해준다.

그리고 answer에 3진법만큼 x배열에 저장해둔 3의 배수들을 꺼내다가 값을 넣어준다.

 

코드를 좀 이상하고 복잡하게 짠 것도 같은데 더 간결하게 할 생각이 안 난다....