코딩 테스트 연습 문제 코딩테스트 연습에 공개된 문제는 (주)그렙이 저작권을 가지고 있습니다.(지문 하단에 별도 저작권 표시 문제 제외)코딩테스트 연습 문제의 지문, 테스트케이스, 풀이 등과 같은 정보는 비상업적, 비영리적 용도로 게시할 수 있습니다.다만 문제의 지문, 풀이 등과 같은 정보를 단순히 게시하는 것을 넘어, 이를 바탕으로 문제를 풀고 채점이 가능하도록 하는 등의 방식으로 활용하는 것은 제한됩니다. ※ 2020 KAKAO BLIND RECRUITMENT, Summer/Winter Coding 등의 문제는 기업 코딩 테스트에 나온 문제이나, 코딩테스트 연습에 공개된 문제이기 때문에 마찬가지로 비상업적, 비영리적 용도로 게시할 수 있습니다. (2021. 01. 08 업데이트)
문제 정보
- 프로그래머스
- python
- level 3
- 점수 : 12
- 문제 링크
문제
문제 설명 펼치기/접기
봉인된 주문
어느 날, 전설 속에 전해 내려오는 비밀 주문서가 세상에 다시 모습을 드러냈습니다. 이 주문서에는 마법 세계에서 사용되는 모든 주문이 적혀 있는데, 각 주문은 알파벳 소문자 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 합니다.
풀이
풀이 코드
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
def num_to_spell(n): # 숫자를 문자열(주문)로 변환
spell = ""
while n > 0:
n = n-1
remainder = n % 26
spell += chr(97 + remainder)
n = n // 26
return spell[::-1]
def spell_to_num(spell:str): # 문자열(주문)을 숫자로 변환
result = 0
for i, char in enumerate(spell[::-1]):
result += (ord(char) - 97 + 1)*(26**i)
return result
def solution(n, bans):
# 제외할 주문을 숫자료 변환하고 정렬
bans = [spell_to_num(ban) for ban in bans]
bans.sort()
# 제외할 숫자 개수 탐색 (upper)
prev = 0
cur_n = n
while prev != cur_n: # 제외할 개수는 동적으로 움직여야 하므로
prev = cur_n
left, right = 0, len(bans)
while left < right: # 이진탐색
mid = (left + right) // 2
if bans[mid] <= cur_n:
left = mid + 1
else:
right = mid
cur_n = n + left
n = cur_n
answer = num_to_spell(n)
return answer
풀이 방식
이번 문제풀이에는 총 세가지 포인트가 있다.
n번째 주문을 찾는 방법
- 알파벳을 26진수라고 여기고, n/26 을 반복하여 구성 알파벳을 찾는다.
- 알파벳 소문자 a 의 ASCII 는 97이므로 n=20 일 경우 결과 주문은 chr(97 + 20%26 - 1) = ‘t’
1
2
3
4
5
6
7
8
def num_to_spell(n): # 숫자를 문자열(주문)로 변환
spell = ""
while n > 0:
n = n-1
remainder = n % 26
spell += chr(97 + remainder)
n = n // 26
return spell[::-1]
주문을 숫자로 변환하는 방법
- 이 문제는 여러모로 주문을 숫자로 변환하면 빠른 연산이 가능하다.
- 위에서 본 “n번째 주문을 찾는 방법”과 같은 결로 수행한다.
1
2
3
4
5
def spell_to_num(spell:str): # 문자열(주문)을 숫자로 변환
result = 0
for i, char in enumerate(spell[::-1]):
result += (ord(char) - 97 + 1)*(26**i)
return result
제거된 주문을 제외하는 방법
- 우선 빠른 주문(a, b…)부터 제거되어야 하므로, 제거될 주문을 정렬해야 한다
- 제거된 주문은, 그 뒤의 주문들이 제거되어야 할지 여부에도 영향을 미친다. 따라서 동적으로 주문을 제거해야 한다. (아래 예시)
- 시간복잡도를 낮추기 위해 이진탐색을 적용했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 제외할 주문을 숫자료 변환하고 정렬
bans = [spell_to_num(ban) for ban in bans]
bans.sort()
# 제외할 숫자 개수 탐색 (upper) -- 이진탐색
prev = 0
cur_n = n
while prev != cur_n:
# 이전에 결정한 제외 주문이 다음 주문들에도 영향을 미칠지 계속 확인
# (이전 결과와 이번 결과가 같아질 때까지)
prev = cur_n
left, right = 0, len(bans)
while left < right:
mid = (left + right) // 2
if bans[mid] <= cur_n:
left = mid + 1
else:
right = mid
cur_n = n + left
n = cur_n
리뷰
문제를 풀 방법이 빠르게 떠오른, 운이 좋았던 문제였다.
Comments