[프로그래머스] Lv3. 봉인된 주문

풀이 방법 

예를 들어, 주문서에서 "d", "e", "bb", "aa", "ae" 5개의 주문을 지웠을 때, 주문서에서 30번째 주문을 찾으려고 합니다.
1~3번째 주문은 "a", "b", "c" 입니다."d"와 "e"는 삭제됐으므로 4~24번째 주문은 "f" ~ "z"입니다."aa"는 삭제됐으므로 25~27번째 주문은 "ab", "ac", "ad"입니다."ae"는 삭제됐으므로 28~30번째 주문은 "af", "ag", "ah"입니다.
따라서 30번째 주문은 "ah"가 됩니다. 삭제된 주문 중 “bb”와 같이 n번째 주문보다 뒤에 위치해 있어서 n번째 주문을 찾는 데 영향을 주지 않는 주문도 존재할 수 있습니다.
정수 n과 삭제된 주문들을 담은 1차원 문자열 배열 bans가 매개변수로 주어질 때, 삭제가 완료된 주문서의 n번째 주문을 return 하도록 solution 함수를 완성해 주세요.

 

문제에서 삭제가 완료된 주문서의 n번째 주문을 return하라고 합니다.

 

 

이 문제는 주문 목록에서 특정 문자열이 삭제된 후, 남은 주문 목록에서의 n번째 주문을 찾는 문제입니다.

일반적으로 n번째 주문을 찾기 위해 처음부터 순서대로 알파벳을 나열하는 방식은 너무 많은 경우의 수를 처리해야 하므로 효율적이지 않습니다. 따라서 문제를 효율적으로 해결하려면 다음과 같은 아이디어를 사용해야 합니다.

 

알파벳으로 구성된 문자열의 순서를 숫자(위치 값)로 표현할 수 있습니다.

• 단일 문자인 경우엔 26개가 존재합니다.
• 두 글자인 경우(aa ~ zz)는 26 × 26개로, 각 문자는 26진수로 생각할 수 있습니다. (예: aa는 27, ab는 28...)
• 이와 같은 방식으로 문자열은 26진수 숫자 표현으로 생각할 수 있습니다.

 

삭제된 주문은 어떻게 고려해야 할까요?

 

삭제된 주문 목록(bans)을 미리 숫자 형태로 변환하고 오름차순으로 정렬합니다.

그런 다음 n번째 주문을 찾을 때, 삭제된 주문이 있는 위치를 만나면 실제로 반환해야 할 위치 값(n)을 1씩 증가시켜가며 건너뛰는 방식으로 처리하면 됩니다.

 

예를 들어 다음과 같습니다.

• 주어진 n번째 위치가 4인데, bans 배열에 이미 지워진 문자열 중 그 위치보다 앞에 위치한 문자열이 있다면, 원래의 4번째는 5번째로 밀립니다.
• 이 과정을 모든 bans 요소에 대해 수행하면 정확한 위치를 얻을 수 있습니다.

이렇게 하여 실제 문자열로 변환할 때, 위치 값을 다시 문자열로 변환하면 됩니다.

 

위치 값에서 어떻게 문자열을 도출할 수 있을까요?

 

위치 값에서 문자열로 변환하는 방법은 다음과 같습니다.

• 문자열의 숫자 표현을 26으로 나누어 각 자리의 알파벳을 찾습니다.
• 나머지를 통해 알파벳 문자를 역으로 추출할 수 있습니다.
• 0을 처리할 때는 'z'로 처리하고 자리 올림 처리를 해주어야 합니다.

 

풀이 코드 

import java.util.*;

class Solution {
    public String solution(long n, String[] bans) {
        
        int cnt = 0;

        Arrays.sort(bans, (o1, o2) -> {
            if (o1.length() == o2.length()) {
                return o1.compareTo(o2);
            }
            return o1.length() - o2.length();
        });

        for (String b : bans) {
            long num = 0;
            for (int i = 0; i < b.length(); i++) {
                num = num * 26 + (b.charAt(i) - 'a' + 1);
            }
            if (num <= n + cnt) cnt++;
        }

        n += cnt;

        StringBuilder sb = new StringBuilder();

        while (n > 0) {
            long remain = n % 26;

            if (remain == 0) {
                sb.append('z');
                n = (n / 26) - 1;
            } else {
                sb.append((char) ('a' + (remain - 1)));
                n /= 26;
            }
        }

        return sb.reverse().toString();
    }

}

 

 

다음은 코드의 각 부분을 풀이한 내용입니다.

 

1. 삭제된 주문 정렬하기

Arrays.sort(bans, (o1, o2) -> {
            if (o1.length() == o2.length()) {
                return o1.compareTo(o2);
            }
            return o1.length() - o2.length();
        });

 

bans 배열을 문자열 길이 순으로 정렬하고, 길이가 같으면 사전순으로 정렬합니다.

이는 더 작은 값부터 숫자로 변환해 순서대로 처리하기 위함입니다.

 

2. 삭제된 문자열의 위치 값 계산하기

for (String b : bans) {
        long num = 0;
        for (int i = 0; i < b.length(); i++) {
            num = num * 26 + (b.charAt(i) - 'a' + 1);
        }
        if (num <= n + cnt) cnt++;
    }

n += cnt;

 

각 삭제된 문자열을 26진수에서 10진수 값으로 변환합니다. 이 때, 'a'는 1, 'b'는 2, ... 'z'는 26으로 매핑됩니다.

만약 삭제된 문자열의 위치(num)가 현재 찾고 있는 주문의 위치(n + cnt)보다 같거나 작으면, 이미 삭제된 주문이기 때문에 실제 찾는 위치가 하나 뒤로 밀리므로 카운트(cnt)를 증가시킵니다. 마지막에 누적된 cnt를 더해 실제 찾는 주문의 위치로 조정합니다.

 

3. 최종 위치 값(n)을 문자열로 변환하기

StringBuilder sb = new StringBuilder();

        while (n > 0) {
            long remain = n % 26;

            if (remain == 0) {
                sb.append('z');
                n = (n / 26) - 1;
            } else {
                sb.append((char) ('a' + (remain - 1)));
                n /= 26;
            }
        }

        return sb.reverse().toString();

 

 

 

이제 최종 위치 값을 다시 문자열로 변환하는 과정입니다. 26진수 숫자 표현을 문자로 변환할 때, 나머지 연산(n % 26)을 통해 각 자리의 알파벳을 결정합니다. 숫자가 정확히 26으로 나누어 떨어지면('0'이 되는 경우), 알파벳 'z'를 사용하고 한 자리 위 숫자를 1 감소시키는 처리(자리 올림 처리를 위한)를 수행합니다. 이렇게 문자열을 역순으로 생성했으므로 마지막에 뒤집어 원래 순서로 되돌립니다.

 

1은 왜 빼야 하는 걸까요?

 

알파벳으로 나타낼 때 a부터 z는 각각 1부터 26에 해당합니다. 숫자를 26으로 나누었을 때 나머지가 0이라는 것은, 실제로는 문자가 z라는 의미입니다.

 

그러나 일반적인 숫자 체계에선 나머지가 0일 때는 다음 자리의 숫자가 이미 자리 올림이 이루어진 상태로 넘어가야 합니다. (예를 들어, 10진수에서 10을 나누어 떨어질 때, 자리 올림을 해야 하는 것과 같은 개념입니다.)

 

따라서 숫자가 26으로 나누어 떨어질 때는 다음과 같은 작업이 필요합니다.

1. 문자는 z로 표현하고 (실제 값 26)
2. 다음 상위 자리로 자리 올림이 이루어져야 하므로 다음 자리의 계산을 위해 1을 감소시킵니다.

 

예를 들어, 52이라는 숫자를 알파벳으로 변환할 경우 문자 "az"가 나와야 합니다.

 

먼저, 1을 빼주지 않은 경우엔 어떻게 되는지 알아보겠습니다.

1 ~ 26과 매칭되는 문자는 a ~ z 입니다.

 

52 % 26은 0이 됩니다. 숫자 0이 나타내는 문자는 존재하진 않지만, 0인 경우엔 문자 "z"를 할당해야 하기 때문에 z를 할당해줍니다.

현재 할당된 문자는 "z"입니다.

 

그 다음 자리의 문자는 52 / 26 % 26이기 때문에 2가 됩니다.

2는 b를 의미하므로, 할당된 문자는 "b"가 됩니다.

 

최종적으로 "zb"를 reverse하면 "bz"가 됩니다. "az"가 나와야 하지만 "bz"가 나오게 됩니다.

따라서, 문자가 "z"가 할당된 경우엔 1을 빼줌으로써 다음 자릿수의 문자를 맞춰주어야 합니다.

 

출력 결과