2018 3차 코딩테스트 풀이
오늘은 2018 1차에 이어 3차 코테를 풀어봤습니다. 전체적으로 문자열조작 문제들이 많았고 난이도도 요즘 카카오 코테에 비하면 낮은 편이었습니다
1번 방금그곡
이 문제는 음악의 일부분(m)을 듣고 어떤 음악인지 맞추는 것입니다. 정렬조건은 재생길이가 긴 음악이고 만약 같다면 musicinfos에 먼저 들어있었던 곡으로 출력하면됩니다. 그리고 없다면 "(None)"을 출력하면 됩니다.
여기서 가장 까다로웠던 부분은 바로 C#과 같은 #이 붙은 코드였어요. 총 재생시간을 구하고 그만큼 연주된 악보를 구해야하는데 이때 CC#이 길이가 3이지만 2분이 걸리는 것으로 계산을 해줘야하기때문입니다.
풀이 순서
곡들마다 반복
1. 재생시간동안의 악보를 만들어준다 ->divmod사용
2. 1번에서 만든악보에 m이 부분문자열로 들어가 있는지 찾는다 -> in연산
3. 있다면 answer리스트에 [재생시간, 곡이름]으로 넣기
반복 끝
4. answer를 첫번째요소 기준(재생시간)으로 내림차순 정렬해서 맨앞원소의 두번째 요소(곡이름) 출력
def to_playtime(start, end):
hour, minute = start.split(":")
start = int(hour) * 60 + int(minute)
hour, minute = end.split(":")
end = int(hour) * 60 + int(minute)
return end - start
def change_code(string):
return string.replace("A#", "H").replace("C#", "I").replace("D#", "J").replace("F#", "K").replace("G#", "L")
def solution(m, musicinfos):
answer = []
for music in musicinfos:
start, end, title, sheet = music.split(",")
playtime = to_playtime(start,end)
# 재생음악출력
sheet = change_code(sheet)
cnt, mod = divmod(playtime, len(sheet))
song = sheet * cnt + "".join(sheet[:mod])
# 찾기
if change_code(m) in song:
answer.append([playtime, title])
if answer:
return sorted(answer, key=lambda x : -x[0])[0][1]
else:
return "(None)"2번 압축
이 문제는 규칙에 따라서 사전에서 참조할 색인을 나열하는 것이었습니다.
풀이 순서
- 모든 알파벳에 대한 색인 넣기 ->
dictionary에 {"a" : 1}이런식으로 넣기 ,아스키코드이용 - i는 포인터입니다
<msg 끝까지 반복> - j는 i+1로 세팅
- msg[i:j]가 사전에 없을 때까지 j이동 (이때 계속해서 이동하면 안되기때문에
len(msg)까지만 갈 수 있도록) - msg[i:j]는 새로 사전에 넣어주고, msg[i:j-1]은 색인을 참고한다
- i는 j-1로 옮겨주기
<반복끝>
def solution(msg):
answer = []
dictionary = {}
for idx in range(65, 91):
dictionary[chr(idx)] = idx - 64
i = 0
while i < len(msg):
j = i + 1
# 사전에 없을 때 까지
while j < len(msg) + 1 and msg[i:j] in dictionary.keys():
j += 1
# 사전에 있는 것
answer.append(dictionary[msg[i:j - 1]])
# 사전에 없는 것
if j < len(msg) + 2:
dictionary[msg[i:j]] = len(dictionary) + 1
i = j - 1
return answer3번 압축
이 문제는 규칙에 따라 게임을 진행합니다. 숫자를 n진수로 바꿔주는 과정이 가장 핵심 부분입니다.
풀이 순서
- 내가 대답해야하는 가장 마지막 답이 몇번째인지 구하기
- 거기까지 모든 답 구하기 -> n진수로 바꿔가면서 계속해서 붙이기
- 내가 대답해야하는 것들만 뽑아서 반환
여기서는 n진수로 바꿀때 처음에 num이 0이면 "0"으로 예외처리를 해줘야하는 것이 중요합니다.
# [3차] n진수 게임
change = {10: "A", 11: "B", 12: "C", 13: "D", 14: "E", 15: "F"}
# 숫자를 n진수로
def get_n_notation(num, n):
if not num:
return "0"
result = ""
while num:
k, mod = divmod(num, n)
if mod > 9:
mod = change[mod]
result = str(mod) + result
num = k
return result
def solution(n, t, m, p):
answer = ''
limit = m * (t - 1) + (p - 1) + 1
nums = ""
start = 0
# 최대구해야하는 idx까지 계속해서 구하기
while len(nums) < limit:
nums += get_n_notation(start, n)
start += 1
# 출력할 인덱스만 따로 추출
for i in range(t):
answer += nums[m * i + (p - 1)]
return answer4번 파일명 정렬
이 문제 숫자를 문자열로 만들어 정렬할 때의 문제점에 대한 문제입니다. (예 : "9" > "13")
풀이 순서
- 파일에서 HEAD와 NUMBER부분추출
- fs리스트에 [HEAD, NUMBER, file명]를 넣어줍니다.
- 그리고 마지막에 fs를 첫번째(HEAD), 두번째 요소(NUMBER)를 정렬기준으로 정렬해주고 세번째요소(file명)만 모아 추출합니다.
def solution(files):
answer = []
fs = []
for file in files:
head = ""
number = ""
i = 0
# HEAD
while i<len(file):
if file[i].isdigit():
break
head += file[i]
i += 1
# NUMBER
while i < len(file):
if not file[i].isdigit():
break
number += file[i]
i += 1
fs.append([head.lower(), int(number), file])
return [ i[2] for i in sorted(fs, key=lambda x : (x[0], x[1]))]5. 자동완성
이 문제는 전체 문제중 가장 어려운 문제로 저는 트라이를 사용해서 해결했습니다.
풀이 순서
- 전체 단어를 트라이로 저장해줍니다. 이때 지나가는 node마다 count를 올려줍니다
- 전체 단어를 돌면서 트라이에서 찾아줍니다. 이때 count가 1이 되거나 탐색이 끝날때까지 탐색횟수를 저장해 출력합니다.
class Node:
def __init__(self, char):
self.char = char
self.cnt = 1
self.children = {}
def solution(words):
answer = 0
# 트라이만들기
root = Node("!")
for w in words:
p = root
for c in w:
if c in p.children.keys():
p.children[c].cnt += 1
else:
p.children[c] = Node(c)
p = p.children[c]
# 검색
for w in words:
p = root
cnt = 0
for c in w:
p = p.children[c]
cnt += 1
if p.cnt == 1:
break
answer += cnt
return answer