[카카오] 2018 3차 코딩테스트 python 풀이

su_y2on·2022년 9월 18일
0

알고리즘

목록 보기
43/47
post-thumbnail

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번 압축

이 문제는 규칙에 따라서 사전에서 참조할 색인을 나열하는 것이었습니다.

풀이 순서

  1. 모든 알파벳에 대한 색인 넣기 -> dictionary에 {"a" : 1}이런식으로 넣기 , 아스키코드 이용
  2. i는 포인터입니다
    <msg 끝까지 반복>
  3. j는 i+1로 세팅
  4. msg[i:j]가 사전에 없을 때까지 j이동 (이때 계속해서 이동하면 안되기때문에 len(msg)까지만 갈 수 있도록)
  5. msg[i:j]는 새로 사전에 넣어주고, msg[i:j-1]은 색인을 참고한다
  6. 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 answer




3번 압축

이 문제는 규칙에 따라 게임을 진행합니다. 숫자를 n진수로 바꿔주는 과정이 가장 핵심 부분입니다.

풀이 순서

  1. 내가 대답해야하는 가장 마지막 답이 몇번째인지 구하기
  2. 거기까지 모든 답 구하기 -> n진수로 바꿔가면서 계속해서 붙이기
  3. 내가 대답해야하는 것들만 뽑아서 반환

여기서는 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 answer




4번 파일명 정렬

이 문제 숫자를 문자열로 만들어 정렬할 때의 문제점에 대한 문제입니다. (예 : "9" > "13")

풀이 순서

  1. 파일에서 HEAD와 NUMBER부분추출
  2. fs리스트에 [HEAD, NUMBER, file명]를 넣어줍니다.
  3. 그리고 마지막에 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. 자동완성

이 문제는 전체 문제중 가장 어려운 문제로 저는 트라이를 사용해서 해결했습니다.

풀이 순서

  1. 전체 단어를 트라이로 저장해줍니다. 이때 지나가는 node마다 count를 올려줍니다
  2. 전체 단어를 돌면서 트라이에서 찾아줍니다. 이때 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

0개의 댓글