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

https://school.programmers.co.kr/learn/courses/30/lessons/389481

프로그래머스

 

문제 유형

• 구현

 

문제 난이도

• Lev3

 

문제 분석

n 번째에 해당하는 문자열을 출력하는 문제이다. 그러나 조건이 있다.
1. 글자 수가 적은 주문부터 먼저 기록된다.
2. 글자 수가 같다면 사전 순서대로 기록된다.

ex)
"a"→"b"→"c"→"d"→"e"→"f"→...→"z"→"aa"→"ab"→...→"az"→"ba"→...→"by"→"bz"→"ca"→...→"zz"→"aaa"→"aab"→...→"aaz"→"aba"→...→"azz"→"baa"→...→"zzz"→"aaaa"→...→"aazz"→"abaa"→...→"czzz"→"daaa"→...→"zzzz"→"aaaaa"→...

3. 봉인된 주문서인 bans 의 문자열들은 제외하고 해당하는 문자열을 출력한다.


문제에서 n <= 10^15, bans[] 배열의 크기 <= 300,000 이므로 단순하게 완전 탐색을 한다면 시간 초과가 날 것이다.

 

풀이 방법

봉인된 주문서를 빠르게 탐색하기 위해 HashMap에 저장해서 사용하였고, count 배열을 통해, 금지된 주문서를 제외하고 현재 n 번째가 실제로 몇 번째 문자열인지 탐색하기 위해 사용하였다.

 

처음에 count[] 배열을 int 타입으로 선언해서 왜 안되지 혼자 계속 삽질했다. -> 26^11이면 당연히 long 타입이지 바보야

Map<String, Integer> map = new HashMap<>();
long[] count = new long[12];

count[1] = 26;

for(int i = 2; i < 12; i++) {
    count[i] = count[i-1] * 26;
}

for(int i = 0; i < bans.length; i++) {
    map.put(bans[i], 1);
    count[bans[i].length()]--;
}

 

 

size는 결과값의 글자 길이를 구하는 것이고, idx는 실제 금지된 주문서를 제외한 구해야하는 문자열이 몇 번째 수인지를 파악하는 변수이다.

answer 값에는 'z' 만큼 나눴을 떄, 나오는 문자열을 출력해준다.

long sum = 0;
        
int size = 0; // 글자 길이
long idx = 0; // 같은 자리수에서 구해야하는 순서
for(int i = 1; i < 12; i++) {

    if(sum + count[i] < n) sum += count[i];
    else {
        size = i;
        idx = n - sum - 1;
        break;
    }
}

int length = size;


for (int i = 0; i < size; i++) {
    long pow = (long) Math.pow(26, size - i - 1);
    answer += (char) (idx / pow + 'a');
    idx %= pow;
}

 

 

해당 부분은 앞서 구한 answer은 자신의 문자열 길이보다 작은 값에 대해서 idx를 구한 것이다.

예를 들면, 

 

n = 30, bans = ["d", "e", "bb", "aa", "ae"] 일때,

이전 상태에서 answer = "af"인 상태이다. (idx가 5이므로)

 

해당 상태는 문자열의 길이가 2일 때에 대한 봉인된 주문서를 제외한 상태가 아니므 현재 "af"와 문자열 길이가 같으면서 해당 문자열보다 내림차순에 있는 개수만큼 문자열의 순서를 늘려주어야 한다.

 long ct = 0;
for(String key : map.keySet()) {
    if(key.length() == length && answer.compareTo(key) >= 0) {
        ct++;
    }
}

 

 

해당하는 개수만큼에 대해 문자열을 오름차순한다. 증가시켰을 때, 'z' 다음 순서인 경우는 다음 자리로 올림해줘야하므로 다음과 같이 코드를 작성하였다.

 while(ct > 0) {

    char[] answers = answer.toCharArray();

    int upper = answer.length()-1;

    while(upper >= 0 && answers[upper] == 'z') {
        answers[upper] = 'a';
        upper--;
    }

    if(upper < 0) {
        answer = "a" + String.valueOf(answers);
        if(map.containsKey(answer)) ct++;
    }
    else {
        answers[upper] += 1;
        if(map.containsKey(String.valueOf(answers))) ct++;
        answer = String.valueOf(answers);
    }

    ct--;
}

전체 코드

import java.util.*;
import java.io.*;

class Solution {
    public String solution(long n, String[] bans) {
        String answer = "";
        
        Map<String, Integer> map = new HashMap<>();
        long[] count = new long[12];
        
        count[1] = 26;
        for(int i = 2; i < 12; i++) {
            count[i] = count[i-1] * 26;
        }
        
        for(int i = 0; i < bans.length; i++) {
            map.put(bans[i], 1);
            count[bans[i].length()]--;
        }
        
        long sum = 0;
        
        int size = 0; // 글자 길이
        long idx = 0; // 같은 자리수에서 구해야하는 순서
        for(int i = 1; i < 12; i++) {
            
            if(sum + count[i] < n) sum += count[i];
            else {
                size = i;
                idx = n - sum - 1;
                break;
            }
        }

        int length = size;
        
        
        for (int i = 0; i < size; i++) {
            long pow = (long) Math.pow(26, size - i - 1);
            answer += (char) (idx / pow + 'a');
            idx %= pow;
        }
        
        long ct = 0;
        for(String key : map.keySet()) {
            if(key.length() == length && answer.compareTo(key) >= 0) {
                ct++;
            }
        }
        
        while(ct > 0) {

            char[] answers = answer.toCharArray();
            
            int upper = answer.length()-1;
            
            while(upper >= 0 && answers[upper] == 'z') {
                answers[upper] = 'a';
                upper--;
            }
            
            if(upper < 0) {
                answer = "a" + String.valueOf(answers);
                if(map.containsKey(answer)) ct++;
            }
            else {
                answers[upper] += 1;
                if(map.containsKey(String.valueOf(answers))) ct++;
                answer = String.valueOf(answers);
            }
            
            ct--;
        }
           
        return answer;
    }
}