[프로그래머스 / Java] 봉인된 주문

문제 개요

주문서는 알파벳 소문자로 이루어진 모든 문자열을 특정 규칙에 따라 정렬한 리스트다.

1. 문자열 길이가 짧을수록 먼저 온다.
2. 길이가 같다면 사전 순으로 정렬된다.

예를 들어 "a", "b", ..., "z", "aa", "ab", ..., "zz", "aaa", ... 순으로 이어진다.

하지만 일부 문자열이 삭제된 상태이며, 삭제된 문자열들을 제외하고 남은 문자열 중에서 n번째에 위치한 문자열을 찾아야 한다.

 

 

접근 방법

 이 문제는 문자열을 정렬 순서대로 하나씩 탐색하는 방식으로는 풀 수 없다. 최대 n이 10^15까지 가능하기 때문에 효율적인 방식이 필요하다. 따라서 문자열을 고유한 숫자에 매핑해서 계산하고, 삭제된 문자열이 영향을 주는 범위를 고려해 n을 보정한 후 다시 문자열로 변환하는 방식으로 해결했다.

 

1. 문자열을 숫자로 변환한다.
   • 26진법을 기반으로 문자열을 고유한 숫자로 치환한다.
   • 예를 들어 "ab"는 1*26 + 2 = 28
   • "a"는 1, "z"는 26이 되도록 1-based로 계산한다.
2. 삭제된 문자열들을 숫자로 변환해 정렬한다.
   • 이후 삭제된 문자열들 중 현재 n보다 작거나 같은 값이 몇 개인지를 계산해 n을 그만큼 증가시킨다.
   • 삭제된 문자열이 끼어들어 순서가 밀렸기 때문에 그만큼 보정한다.
3. 보정된 숫자를 다시 문자열로 변환한다.
   • % 26 연산을 반복하며 각 자리의 알파벳을 구하고, a부터 시작하는 문자로 매핑해 문자열을 만든다.
   • StringBuilder로 역순으로 조립한다.

 

코드

import java.util.*;
class Solution {
    public String solution(long n, String[] bans) {
        long[] arr = new long[bans.length];
        
        for(int i=0; i<bans.length; i++) arr[i] = alphabetToNum(bans[i]);
        
        Arrays.sort(arr);
        for(int i=0; i<arr.length; i++) if(arr[i] <= n) n++;
        
        return numToAlphabet(n);
    }
    
    public String numToAlphabet(long num) {
        StringBuilder sb = new StringBuilder();
        
        while(num > 0) {
            num--; //26진수 0이 a인데 해당 문제는 1이 a임
            long bucket = num % 26;
            sb.append((char) ('a' + bucket));
            num /= 26;
        }
        
        return sb.reverse().toString();
    }
    
    public long alphabetToNum(String s) {
        long res = 0;
        
        for(int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            long bucket = ch - 'a' + 1;
            res = res*26 + bucket;
        }
        
        return res;
    }
}