[Programmers] 프로그래머스 > 124 나라의 숫자(c++)

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

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

코딩테스트 연습 > 연습문제 > 124 나라의 숫자

 

 

처음엔 dp 방법으로 풀었는데, 시간초과가 나서 다른 방법으로 접근했다.

아무리 시도해봐도 숫자가 3자리수가 넘어가게 되면 답이 거꾸로 출력이 돼서, 구글 검색으로 

answer = 연산 도중 계산된 숫자 + answer

이렇게 하면 거꾸로 출력되지 않는것을 확인하고 다시 풀었다.

 

1. remainder에는 (n-1)%3으로 나눈 나머지를 num의 인덱스에서 찾은 값 저장

2. answer에 연산된 remainder를 끝부분에 추가

3. n은 (n-1)/3 해주고, n<=0일때까지 반복

 

n%3, n/3이 아닌 이유는, num[0] = 1, num[1] = 2, num[2] = 4이지만

인덱스로 계산해봤을때, 1 2 3 이 나와야 하는데 num의 인덱스는 0 1 2 이므로 (n-1)%3을 해줬고,

1/3 = 0,

2/3 = 0,

3/3 = 1,

4/3 = 1,

5/3 = 1,

6/3 = 1 

이므로 예상한것과 1씩 차이가 난다. 1,2,3일때는 3으로나눴을때 1이어야하고 4,5,6일때는 2여야 하므로 (n-1)해준값에 /3을 해서 연산했다.

다른분들 풀이를 보니까 n/3, n%3으로 계산하려면 num를 { 4, 1, 2 }로 두고 풀면 되는거였다!

 

---

main포함 코드(c++)

 

#include <string>
#include <vector>

using namespace std;

string solution(int n) {
    
    int num[3] = {1,2,4};
    string answer = "";
    
    while (n > 0) {
        int remainder = num[(n-1)%3];
        answer = to_string(remainder) + answer;
        n = (n-1)/3;
    }
    
    return answer;
}

int main()
{
    
    int n = 30;
    solution(n);
    
    return 0;
}