[PGM_12899] 124 나라의 숫자 (Java)

문제링크

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

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

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 3진수

이 문제는 1과 2 그리고 4로 숫자를 표현하는 진법으로 변환해주는 것이다. 문제를 계속 들여다보면 3진법으로 구성되는 것을 알 수 있다.

 

10진법의 수가 1일 경우 1,

2일 경우 2,

3일 경우에는 4,

4일 경우에는 11

이 되는 것을 알 수 있다.

 

원래 3진수의 경우 3이 될 때는 carry가 발생하여 자리수를 변경해주어야하는데, 딱 3일 경우에는 4로 변경이 되는 특이점이 있다.

따라서 주어진 값을 진수로 변경하여주고 이러한 특이점을 해결해주면 문제를 풀 수 있다.

 

n진수로 변환하는 방법은 %연산자와 /연산자를 사용하여 변환해줄 수 있다. n값을 %연산해준 값이 앞 자리수부터 사용되는 값이고 / 연산을 해줘서 다시 %연산을 해주며 n진법의 값을 구해줄 수 있다.

while (n > 0){
    list.add(n%3);
    n = n / 3;
}

코드로 3진법을 표현하기 위해서는 이렇게 구현해주면 된다.

 

이 때 ArrayList를 활용하여 진법의 각 값들을 넣어주었다. 이유는 3일 경우에만 케리가 아닌 4로 변환해주어야하는 문제를 해결하기 위해서이다. 4로 변환해야하는 경우는 0일 경우이다. 0이라면 carry값이 1 올라가 있을 것이다. 따라서 그 carry값을 다시 내려주고, 0 값을 4로 변경해주면 된다.

 

문제를 해결하는 방법은 다음과 같다.

1. 입력값인 n을 3진수로 변환한다.
2. 3진수의 값을 뒤에서부터(가장 작은 자리수) 0이거나 음수인지 확인하여준다.
3. 만약 0일 경우 그 값을 4로 변환해주고 다음 자리의 값을 -1 해준다.
4. 만약 음수일 경우 다음 자리의 값에 -1을 해주고 4에서 해당 값을 더해준 값을 넣어준다.
5. List를 반환하여 진수를 만들어준다. 이 때, 0은 제외한다.(0이 있는 경우는 3진법 값이 맨 앞 자리수만 1 나머지는 0인 경우이다.)

구현코드

package pgm_12899;

import java.util.ArrayList;

class Solution {
    public String solution(int n) {
        String answer = "";
        ArrayList<Integer> list = new ArrayList<>();
        while (n > 0){
            list.add(n%3);
            n = n / 3;
        }

        for(int i = 0; i < list.size()-1; i++){
            if(list.get(i) == 0) {
                list.remove(i);
                list.add(i,4);
                int carry = list.remove(i + 1) - 1 ;
                list.add(i+1,carry);
            }
            if(list.get(i) < 0){
                int removeI = list.remove(i);
                list.add(i,3+removeI);
                int carry = list.remove(i + 1) - 1 ;
                list.add(i+1,carry);
            }
        }

        for(int i = 0; i < list.size(); i++){
            if(list.get(i) != 0)
                answer = list.get(i) + answer;
        }
        return answer;
    }
}

 

시간복잡도

정수의 크기 n을 3으로 나누어 가며 3진수로 바꾸어주고 n만큼 모두 돌며 확인하기 떄문에 $O(n)$이 된다.

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)