PGMS_봉인된 주문 (Java)
[level 3] 봉인된 주문 - 389481
성능 요약
메모리: 154 MB, 시간: 129.59 ms
구분
코딩테스트 연습 > 2025 프로그래머스 코드챌린지 2차 예선
채점결과
정확성: 100.0
합계: 100.0 / 100.0
제출 일자
2025년 03월 07일 02:52:31
문제 설명
어느 날, 전설 속에 전해 내려오는 비밀 주문서가 세상에 다시 모습을 드러냈습니다. 이 주문서에는 마법 세계에서 사용되는 모든 주문이 적혀 있는데, 각 주문은 알파벳 소문자 11글자 이하로 구성되어 있습니다. 주문서에는 실제로 마법적 효과를 지니지 않는 의미 없는 주문들 즉, 알파벳 소문자 11글자 이하로 쓸 수 있는 모든 문자열이 고대의 규칙에 따라 아래와 같이 정렬되어 있습니다.
- 글자 수가 적은 주문부터 먼저 기록된다.
- 글자 수가 같다면, 사전 순서대로 기록된다.
예를 들어, 주문서의 시작 부분은 다음과 같이 구성됩니다.
- "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"→...
하지만 이 주문서에는 오래전 봉인된 저주받은 주문들이 숨겨져 있었고, 이를 악용하려는 자들을 막기 위해 마법사들이 몇몇 주문을 주문서에서 삭제했습니다. 당신은 삭제가 완료된 주문서에서 n번째 주문을 찾아내야 합니다.
예를 들어, 주문서에서 "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 함수를 완성해 주세요.
제한사항
- 1 ≤
n≤ 1015 - 1 ≤
bans의 길이 ≤ 300,000bans의 원소는 알파벳 소문자로만 이루어진 길이가 1 이상 11 이하인 문자열입니다.bans의 원소는 중복되지 않습니다.
입출력 예
| n | bans | result |
|---|---|---|
| 30 | ["d", "e", "bb", "aa", "ae"] | "ah" |
| 7388 | ["gqk", "kdn", "jxj", "jxi", "fug", "jxg", "ewq", "len", "bhc"] | "jxk" |
테스트 케이스 구성 안내
아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.
| 그룹 | 총점 | 추가 제한 사항 |
|---|---|---|
| #1 | 15% | n ≤ 1,000, bans의 길이 ≤ 100 |
| #2 | 15% | n ≤ 1,000,000 |
| #3 | 70% | 추가 제한 사항 없음 |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
주어진 주문을 지운 후 주문서의 7,388 번째 주문은 "jxk"입니다.
따라서 "jxk"를 return 합니다.
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
문제풀이
-
해결 접근법:
- 26진법 체계를 활용하여 문자열을 위치 값으로 변환하고 역변환
- 누적합을 이용해 각 길이별 문자열 총 개수 미리 계산
-
주요 데이터 구조:
- pow26[]: 26의 거듭제곱 값 저장 (26^0, 26^1, …)
- totalCnt[]: 각 길이까지의 문자열 누적 개수 저장
-
핵심 알고리즘:
- 위치→문자열, 문자열→위치 변환 함수 구현
- 밴 목록을 위치 값으로 변환 후 정렬
- n보다 작거나 같은 위치의 밴 개수만큼 n을 증가시켜 최종 위치 계산
- 최종 위치를 다시 문자열로 변환
-
최적화 포인트:
- 26의 거듭제곱 미리 계산하여 재사용
- 불필요한 반복 계산 제거
- 효율적인 이진 변환 로직 사용
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.*;
class Solution {
static StringBuilder sb;
static long[] totalCnt, pow26;
public String solution(long n, String[] bans) {
String answer = "";
// 누적합으로 길이별 개수 계산
pow26 = new long[12];
pow26[0] = 1;
for(int i=1; i<=11; i++){
pow26[i] = pow26[i-1] * 26;
}
totalCnt = new long[12];
totalCnt[0] = 0;
for(int i=1; i<=11; i++){
totalCnt[i] = totalCnt[i-1] + pow26[i];
}
// 밴 목록 위치 값으로 변환
long[] banPos = new long[bans.length];
for (int i = 0; i < bans.length; i++) {
banPos[i] = wordToPos(bans[i]);
}
Arrays.sort(banPos);
long targetPos = n;
for(long b : banPos){
if(b <= targetPos){
targetPos++;
}
else break;
}
return posToWord(targetPos);
}
private static long wordToPos(String word){
int len = word.length();
long pos = totalCnt[len-1] + 1;
for(int i=0; i<len; i++){
int charVal = word.charAt(i) - 'a';
pos += charVal * pow26[len - 1 -i];
}
return pos;
}
private static String posToWord(long pos){
int len = 1;
while(len <= 11 && totalCnt[len] < pos){
len++;
}
long offset = pos - 1 - totalCnt[len-1];
sb = new StringBuilder();
for(int i=len-1; i>=0; i--){
int digit = (int) (offset/pow26[i]);
sb.append((char)('a' + digit));
offset -= digit * pow26[i];
}
return sb.toString();
}
}