봉인된 주문 (Java)

🔗 문제 링크

---

📝 문제 설명

이 문제는 고대의 주문서에 기록된 모든 주문(알파벳 소문자 11글자 이하로 구성된 모든 문자열)이
다음 규칙에 따라 정렬되어 있다고 가정합니다.

• 길이가 짧은 주문부터 기록됨.
• 길이가 같으면 사전 순으로 기록됨.

예를 들어, 주문서의 시작 부분은
"a" → "b" → ... → "z" → "aa" → "ab" → ... → "zz" → ...
와 같이 구성됩니다.

그러나 주문서에는 저주받은 주문들이 포함되어 있어, 일부 주문은 삭제되었습니다.
문제의 목표는, 삭제된 주문들을 고려하여 실제 주문서에서 n번째 주문이 무엇인지 찾는 것입니다.

---

✅ 접근 방식 및 시도한 방법들

문제 해결을 위한 주요 아이디어는 숫자 n을 주문서의 순서대로 변환하는 것입니다.
즉, "n번째 주문"을 구하는 함수 getString(n)을 작성하여,
숫자 n을 위에서 설명한 정렬 순서(길이 우선, 길이가 같으면 사전 순)대로 대응되는 문자열로 변환합니다.

첫 번째 시도: Math.pow 사용

• 아이디어:
  숫자 n을 주문 문자열로 변환할 때, 26의 제곱값을 이용해 몫과 나머지를 구하는 방식으로 진행함.
• 문제점:
  Math.pow는 부동소수점 연산을 사용하기 때문에,
  단순 정수 연산에 비해 오버헤드가 발생하고,
  정밀도 문제로 올바른 정수 계산이 어려울 수 있음.

두 번째 시도: 제곱 값을 배열에 미리 저장

• 아이디어:
  반복문이나 배열을 이용하여 26의 거듭제곱 값을 미리 계산해 저장한 후 사용.
• 문제점:
  나머지가 0이 되는 경우(예: n가 26의 배수)에는
  몫 계산 때문에 원래 의도와 다른 문자가 출력되는 현상이 발생함.
  (예: 반례 52와 같은 상황)

세 번째 시도: 26으로 나누면서 몫과 나머지를 계산 (진수 변환 방식)

• 아이디어:
  getString 메서드에서 Math.pow를 제거하고,
  반복적으로 n을 26으로 나눈 몫과 나머지를 이용해 문자를 결정하는 방식으로 변환.
• 장점:
  정수 연산만 사용하므로 오버헤드가 줄어들고,
  효율적으로 n을 문자열로 변환할 수 있음.

네 번째 시도: banned(삭제된 주문) 처리 조건 개선

• 문제 상황:
  삭제된 주문(bans)들이 사전 순 및 길이 기준으로 이미 정렬되어 있음.
  원래 조건은

  if (cur.length() < target.length() || cur.compareTo(target) <= 0)

  와 같이 되어 있었는데,
  이것은 길이 비교와 사전 순 비교를 별도로 적용하는데 일관성이 떨어짐.
• 해결:
  길이 비교를 먼저 수행하고,
  길이가 같은 경우에만 사전 순 비교를 하도록 조건을 수정함:

  if (cur.length() < target.length() || (cur.length() == target.length() && cur.compareTo(target) <= 0))

  이렇게 하면, banned에 저장된 문자열이 후보 문자열보다 앞쪽에 위치할 때만
  n을 증가시켜 건너뛰도록 처리할 수 있음.

---

🔍 최종 코드

아래 코드는 위의 아이디어를 모두 반영한 최종 풀이입니다.

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

// Math.pow를 사용하면 부동소수점 연산으로 인한 오버헤드가 발생할 수 있으므로,
// 반복문과 정수 연산을 이용하여 26진법 변환을 수행합니다.

class Solution {
    
    public String solution(long n, String[] bans) {
        // banned 주문들을 길이, 사전순으로 정렬
        Queue<String> bansQueue = new ArrayDeque<>();
        Arrays.sort(bans, (o1, o2) -> {
            if (o1.length() == o2.length()) return o1.compareTo(o2);
            return o1.length() - o2.length();
        });
        for (int i = 0; i < bans.length; i++) {
            bansQueue.add(bans[i]);
        }
        
        // banned 주문들보다 순서가 앞에 있는 주문이 있으면 n을 증가시킴.
        // 조건: banned 주문의 길이가 현재 n번째 주문(getString(n))보다 짧거나,
        //       길이가 같을 경우 사전순으로 같거나 앞서 있으면.
        while (!bansQueue.isEmpty()) {
            String cur = bansQueue.peek();
            String target = getString(n);
            if (cur.length() < target.length() || (cur.length() == target.length() && cur.compareTo(target) <= 0)) {
                bansQueue.poll();
                n++;
            } else {
                break;
            } 
        }
        return getString(n);
    }
    
    // getString: 숫자 n을 주문서의 순서에 맞는 문자열로 변환
    // 변환 방식: 26진법 변환과 유사하게 처리하며, n이 26의 배수인 경우를 따로 처리함.
    private String getString(long n) {
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            long remained = n % 26;
            n /= 26;
            if (remained == 0) {
                n--;
                sb.append('z');
            } else {
                sb.append((char)('a' + remained - 1));
            }
        }
        return sb.reverse().toString();
    }
}

---

✅ 코드 로직 상세 설명

1. bans 정렬 및 큐 초기화

   • Arrays.sort(bans, ...)를 이용해 banned 주문들을 먼저 길이 순으로 정렬하고,
     길이가 같으면 사전 순으로 정렬합니다.
   • 이후, 정렬된 banned 주문들을 bansQueue에 추가합니다.

2. banned 주문 처리

   • while 루프 내에서 getString(n)을 호출하여 현재 n번째 주문(후보 문자열)을 구합니다.
   • 후보 문자열과 bansQueue의 맨 앞 문자열(cur)을 비교합니다.
   • 비교 조건은 두 가지입니다:
     • 길이 비교:
       만약 cur의 길이가 후보 문자열보다 짧다면,
       cur는 후보보다 앞쪽에 있으므로 banned에 포함되어 있으므로 n을 증가시켜 건너뜁니다.
     • 사전 순 비교 (길이가 같은 경우):
       만약 두 문자열의 길이가 같고, cur.compareTo(target) <= 0라면,
       즉, cur가 후보와 같거나 사전순으로 앞서면 역시 n을 증가시켜 건너뜁니다.
   • 이 조건을 만족하면 banned 문자열을 큐에서 제거하고, n을 1 증가시킵니다.
   • 조건을 만족하지 않으면 루프를 종료합니다.

3. n번째 주문 문자열 반환

   • 최종적으로 getString(n)을 호출하여, banned 주문들을 고려한 실제 n번째 주문 문자열을 반환합니다.

4. getString 메서드 (26진법 변환 방식)

   • 이 메서드는 n을 반복적으로 26으로 나누며,
     각 자릿수에 대응하는 알파벳을 결정합니다.
   • 주의: n이 26의 배수인 경우, 나머지가 0이 되므로 이 경우를 특별히 처리하여
     'z'를 추가하고 n을 1 감소시킵니다.
   • 마지막에 결과 문자열을 뒤집어 반환합니다.

---