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

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

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

124 나라의 숫자 문제

구현 방법

 

이 문제를 보자마자 3진법과 비슷한 패턴이 떠올랐습니다.

 

해당 패턴 다음과 같은 순서로 진행됩니다.

기존 숫자	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
패턴	1	2	3	11	12	13	21	22	23	31	32	33	111	112	113	121	122	123

 

하지만 124 나라의 숫자 문제에서는 다음과 같은 순서로 진행됩니다.

기존 숫자	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
124 나라	1	2	4	11	12	14	21	22	24	41	42	44	111	112	114	121	122	124

 

얼핏 보면 비슷한 패턴으로 진행됩니다.

단, 기존 숫자를 3으로 나눈 몫이 3으로 나누어 떨어지면 상황이 달라집니다.

 

124 나라의 숫자 패턴을 다음과 같은 알고리즘으로 생각했습니다.

• 숫자를 3으로 나누고, 나머지를 정답 문자열에 더해주고 몫을 전달해줍니다.
• 전달받은 몫이 0이 될 때까지 반복합니다.
• 단, 전달 받은 몫을 3으로 나눌 때, 나누어 떨어지면 나머지인 0 대신에 , 4를 문자열에 더해주고, 몫에서 1을 뺀 숫자의 몫을 전달해 줍니다.  (전달할 몫 = (전달받은 몫 - 1) / 3 )

위 알고리즘을 예를 들어 설명하겠습니다.

 

숫자: 13

13을 3으로 나누면 몫은 4, 나머지는 1 이므로 문자열에 "1"을 추가해줍니다.

문자열 : "1"

 

전달 받은 몫 4를 3으로 나누면 몫은 1, 나머지는 1이므로 문자열에 "1"을 추가해줍니다.

문자열 : "11"

 

전달받은 몫 1을 3으로 나누면 몫은 0, 나머지는 1이므로 문자열에 "1"을 추가해줍니다.

문자열:  "111"

 

전달받은 몫이 0이므로 종료합니다.

 

이때의 결과는 "111"임을 알 수 있습니다.

 

숫자: 20

20을 3으로 나누면 몫은 6, 나머지는 2이므로 문자열에 "2"를 추가해줍니다.

문자열 : "2"

 

전달받은 몫 6을 3으로 나누면 나누어 떨어지므로 문자열에 "4"를 추가하고, 6-1을 3으로 나눈 몫인 1을 전달해줍니다.

문자열: "42"

 

전달 받은 몫 1을 3으로 나누면 몫은 0, 나머지는 1이므로 문자열에 "1"을 추가해줍니다.

문자열 "142"

 

전달 받은 몫이 0이므로 종료합니다.

 

이때의 결과는 "142"임을 알 수 있습니다.

 

위 로직은 아래 소스코드와 같이 구현했습니다.

 

소스코드

string solution(int n) {
    string answer = "";

    int num = n;

	//전달 받은 몫이 0일때 까지 반복
    while(num != 0) {
        int remainder = num % 3;
		
        //나머지가 0이면 문자열에 "4" 더하고
        //(전달받은 몫 - 1) / 3 리턴
        if(remainder == 0) {
            answer = "4" + answer;
            num = (num-1) / 3 ;     
        }//나머지가 1이면 문자열에 "1"더하고
        //몫 / 3 리턴
        else if(remainder == 1) {
            answer = "1" + answer;
            num /= 3;
        }//나머지가 2이면 문자열에 "1"더하고
        //몫 / 3 리턴
        else if(remainder == 2) {
            answer = "2" + answer;
            num /= 3;
        }
    }
    return answer;
}