[카카오공채] 2018 1차 코딩테스트 python 풀이

2018 카카오 1차 코딩테스트 리뷰

실제 번호는 이게 아니었던 것 같은데(프로그래머스 기준 왜 어려운것들이 앞에있지??? 만약 저 순서대로 나왔다면 좀 많이 당황했을 듯..) 쉬운문제들부터 리뷰하도록 하겠습니다.

이때는 3차에 거쳐서 코딩테스트를 봤더라고요. 그래서 그런지 1차는 전체적으로 지금에 비하면 쉬운수준의 문제들입니다.

1. 다트 게임

다트를 던진 결과가 문자열로 들어오고 규칙에 맞춰서 획득한 점수를 반환하면 되는 문제로 어떻게 문자열을 쪼개고 판단할지가 중요한 문제였습니다.

1) 0~10의 정수
2) S, D, T : 정수에 몇제곱을 할지
3) *, # : 추가 점수

한번 다트를 던질 때마다 1)2)3)의 조합이 생기고 그것이 연달아 붙어있는 문자열이 입력으로 들어옵니다

따라서 저는 일단 숫자가 나오면 다음 다트로 넘어갔다고 판단했고 그 뒤에 나오는 SDT로 해당 숫자에 N제곱을 해주고 *,#가 나왔다면 각각 분기처리로 추가처리를 해줬습니다.

1)2)3)은 각각 isdigit, isalpha와 나머지로 구분했습니다.

def solution(dartResult):
    idx = -1
    result = []
    pre = ""
    
    for char in dartResult:
        # 숫자면 
        if char.isdigit():
            # 두자리수
            if pre.isdigit():
                score = 10
            else:
                idx +=1
                score = int(char)
        # 알파벳이면 
        elif char.isalpha():
            if char == "S":
                result.append(score)
            elif char == "D":
                result.append(score ** 2)
            else:
                result.append(score ** 3)
        # 특수문자이면 
        else:
            if char == "*":
                result[idx] *= 2
                if idx > 0:
                    result[idx-1] *= 2
            else:
                result[idx] *= (-1)
                
        pre = char
                
    return sum(result)

이 문제에서 까다로웠던 부분은 10이 들어오는 경우입니다. 나머지는 다 한자리수인데 10만 두자리수라 숫자라고해서 바로 끝내면 안되고 뒤에도 숫자인지 확인해서 두자리인지 확인을 해줘야합니다. 그래서 저는 이전 문자를 저장해두고 연속해서 숫자가 나온것이면 score을 10으로 인식해줬습니다.

다른 답들을 둘러보니 정규표현식으로 하신분들도 있고(카카오 옛날 기출들이 정규표현식으로 풀면 유리한 문제들이 몇 있는 것 같네요) 처음부터 10을 처리해주고 시작하는 경우도 있었습니다.

그 중 괜찮았던 처리방법은 아래와 같이 10 -> k로 바꾸고 k는 '10'으로 파싱되도록하고 나머지는 다 문자로 끊어서 point라는 배열을 만들고 시작하는 것입니다.

dartResult = dartResult.replace('10','k')
point = ['10' if i == 'k' else i for i in dartResult]

2. 비밀지도

이 문제는 두개의 지도가 주어지는데 각각 십진수로 주어진 숫자들을 이진수로 변경해서 지도를 해독해야합니다. 그리고 두개의 지도를 겹쳐서 하나라도 1인 구간은 # 아니면 공백으로 반환하는 문제입니다.

어떻게든 풀려면 푸는 문제입니다. 일단 나는 내장함수 bin()을 사용해서 십진수를 이진수로 바꾸고 결과를 n자리수로 통일해주기위해 앞에 0으로 채워 반환하는 함수를 만들었습니다.

그리고 그냥 문제그대로 수행했습니다..

def solution(n, arr1, arr2):
    answer = []
    
    def to_bin(num):
        result = bin(num)[2:]
    
        return "0" * (n-len(result)) + result

    for i in range(n):
        result = ""
        line1 = to_bin(arr1[i])
        line2 = to_bin(arr2[i])
        
        for j in range(n):
            if line1[j] == line2[j] == "0":
                result += " "
            else:
                result += "#"
        
        answer.append(result)
        

    return answer

여기서 개선할점 하나는 이렇게 길이가 같은 두가지 배열을 한번에 하나씩 땡겨와서 처리해줘야할 때 zip()을 쓸 수 있다는 점입니다. 사실 이 함수 알고는 있었지만 굳이 써야돼? 라는 마음으로 외면하고있던 함수인데 이 문제를 풀면서 확실히 불편함을 느꼈고 뭔가 이제는 쓸 때가 온 것 같습니다(저는 필요성을 느끼고 받아드리는게 좋더라고요^^;;)

여기에 비트연산과 zfill, replace까지 써주면 완벽합니다. 내장함수의 힘이죠! 이렇게보니 너무 내장함수 활용을 못하고 풀었네요ㅎㅎ

def solution(n, arr1, arr2):
    answer = []

    for i,j in zip(arr1,arr2):
        binary = bin(i|j)[2:]
        binary = binary.zfill(n)
        binary = binary.replace("1", "#")
        binary = binary.replace("0", " ")
        answer.append(binary)
        

    return answer

3. 캐시

이 문제는 캐시 hit, miss 그리고 교체까지 녹여낸 문제입니다. 문제조건이 간단해서 조건에 맞춰 구현해주면 되는 문제였습니다.

저는 가장 쓰이지 않은 것을 판단해주기위해 queue를 선택했습니다. 쓰일 때마다 뒤로 보내면 결국 맨 앞이 교체대상이 됩니다.

일단 hit하면 hit한 것을 찾아서 해당요소를 뽑아 맨뒤에다가 다시넣어줍니다. miss라면 자리가 남아있다면 그냥 뒤에 넣어주고 자리가 찼다면 맨앞을 뽑아 자리를 만들어주면 됩니다!

만약 N이 컸다면 list를 deque로 교체하면 좋을 것 같습니다~

def solution(cacheSize, cities):
    answer = 0
    if not cacheSize:
        return len(cities) * 5
    queue = []
    for city in cities:
        city = city.lower()
        try: # hit
            idx = queue.index(city)
            queue.append(queue.pop(idx))
            answer += 1
        except: # miss
            answer += 5
            if len(queue) >= cacheSize:
                queue.pop(0)
            queue.append(city)
    return answer

4. 프렌즈4블록

이 문제는 2 x 2 크기의 블록이 모두 캐릭터가 같으면 사라지면서 위에있는 블록이 그 자리를 채우고를 반복하며 몇개의 블록이 삭제되었는지 세는 문제입니다.

2x2가 겹쳐있는 경우에도 해당되기때문에 저는 일단 (0,0)좌표부터 (m-2,n-2)까지 돌면서 2x2영역을 확인하고 삭제해야하는 경우 그 해당좌표를 remove 리스트에 넣어주고 탐색이 끝나면 삭제했습니다. 그리고 더이상 지울것이 없으면 반환하면서 끝이 납니다.

만약 지울 것이 있다면 2x2영역에 해당되는 모든 블록을 공백처리해주고 중복으로 셀수있기 때문에 이미 공백이면 제외해줬습니다.

이제 위에있던 블록들을 떨어뜨려야합니다. 여기서 하나 주의할 점은 위부터 진행하면 아래쪽이 떨어지면서 위쪽이 떨어져야하는 상황이 나중에 발생할 있습니다. 따라서 아래에서 위로 올라가면서 하는 것이 맞습니다. 그리고 한번 떨어질때 쭉 밑에까지 떨어뜨리면 됩니다.

def solution(m, n, board):
    answer = 0
    board_arr = []

    for b in board:
        board_arr.append(list(b))

    while True:
        # 블록탐색
        remove = []
        for i in range(m - 1):
            for j in range(n - 1):
                if board_arr[i][j] and board_arr[i][j] == board_arr[i + 1][j] == board_arr[i][j + 1] == board_arr[i + 1][j + 1]:
                    remove.append([i, j])

        # 더 이상 지울거 없음
        if not remove:
            return answer

        # 지우기
        for rm in remove:
            i, j = rm
            if board_arr[i][j]:
                board_arr[i][j] = ""
                answer += 1
            if board_arr[i + 1][j]:
                board_arr[i + 1][j] = ""
                answer += 1
            if board_arr[i][j + 1]:
                board_arr[i][j + 1] = ""
                answer += 1
            if board_arr[i + 1][j + 1]:
                board_arr[i + 1][j + 1] = ""
                answer += 1

        # 공백 채우기 : 아래부터 위로
        for i in range(m-2,-1,-1):
            for j in range(n):
                if board_arr[i][j]:
                    p = i + 1
                    while p < m and not board_arr[p][j]:
                        board_arr[p][j], board_arr[p - 1][j] = board_arr[p - 1][j], board_arr[p][j]
                        p += 1

5. 뉴스 클러스터링

뉴스클러스팅 또한 주어진 문자열을 규칙대로 분할하고 데이터를 얻어 계산하면 됩니다. 여기서는 합집합과 교집합의 개념이 나오기 때문에 set을 사용하면 좋습니다. 그리고 반환처리만 주의하면 됩니다.

import collections

def solution(str1, str2):
    str1 = str1.lower()
    str2 = str2.lower()
    
    chars1 = collections.defaultdict(int)
    chars2 = collections.defaultdict(int)
    for i in range(len(str1)-1):
        if str1[i:i+2].isalpha():
            chars1[str1[i:i+2]] += 1
    
    for i in range(len(str2)-1):
        if str2[i:i+2].isalpha():
            chars2[str2[i:i+2]] += 1
            
    n = set(chars1.keys()) & set(chars2.keys())
    u = set(chars1.keys()) | set(chars2.keys())
    
    n_score = 0
    u_score = 0
    for c in n:
        n_score += min(chars1[c], chars2[c])
        
    for c in u:
        u_score += max(chars1[c], chars2[c])
        
    
    if not n_score and not u_score:
        return 1 * 65536
      
    return (n_score * 65536) // u_score

6. 셔틀버스

가장 늦게 버스 save할 수 있는 시간을 구하는 문제입니다. 참 뭔가 재미있는 문제라고 생각했습니다. 회사는 가되 가장 늦게가고싶은 마음...(저도 직장인이 되어 느껴보고싶네요;;)

그리디 문제이고 가능한 경우를 모두 생각해서 분기처리를 잘 해주면 되는 문제입니다. 저는 스택자료구조를 사용했습니다.

이 문제는 문자열로 시간을 주고 실제 시간계산을 해야합니다. 이런문제가 종종 나오는데 이럴때는 일단 문자열을 단위시간으로 바꿔야합니다. 우리야 9시 59분 다음이 10시인걸 알지만 이걸 코드로 처리해주려면 머리가 아프기 때문에 분이나 초로 환산해서 계산을 하고 마지막에 바꿔줘야 합니다.

여기서는 분으로 바꾸면 됩니다.(이렇게 환산하는 것은 함수로 만들어두고 쓰면 좋습니다)
그리고 일단 제일 마지막 버스를 타야하기때문에 그 앞까지는 시간 안에 온사람들을 대기열에서 pop해줍니다.

그리고 마지막버스에서 구체적으로 따져주면됩니다.
1. 마지막버스가 꽉찬경우 => 제일 늦게탄 사람보다 1분 빨리 오면 된다
2. 마지막버스가 여유인경우 => 마지막버스 도착시간에 딱 오면 된다

이렇게 두가지 경우로 나뉘기때문에 이대로 구현하면 끝입니다. 이렇게 보니까 진짜 약간 얄미운 문제네요 ㅎㅎ

def time_to_minute(time):
    hour, minute = time.split(':')
    return int(hour) * 60 + int(minute)

def minute_to_time(minute):
    hour, minute = divmod(minute,60)
    
    hour = str(hour)
    minute = str(minute)
    
    return hour.zfill(2) + ":" + minute.zfill(2)

def solution(n, t, m, timetable):
    timetable.sort()
    arrive_time = time_to_minute("09:00")
    
    for _ in range(n-1):
        cnt = 0
        while timetable and cnt < m and time_to_minute(timetable[0]) <= arrive_time:
            timetable.pop(0)
            cnt += 1
            
        arrive_time += t
    
    # 마지막버스 
    people = []
    while timetable and len(people) < m and time_to_minute(timetable[0]) <= arrive_time:
        people.append(timetable.pop(0))
    
    if len(people) == m:
        return minute_to_time(time_to_minute(people.pop()) - 1)
    
    else:
        return minute_to_time(arrive_time)
        

7. 추석 트래픽

이 문제는 좀 저에게 절망을 안겨준 문제입니다.. 뭔가 분명 쉬워보이는데 계속 풀리지 않는 이상한 느낌을 줬고 이런느낌을 코테에서 받게되면 굉장히 기분더러워지는 그런 문제였습니다...

일단 처음에는 슬라이딩 윈도우를 생각했습니다. 근데 단위가 ms즉 0.001초기 때문에 저는 모든 시간을 ms로 변환해줬습니다. 또 이런문제는 어려운게 처음과 끝 범위처리입니다. 문제마다 조건이 다르기때문에 잘 읽고 또 꼭 그려가면서 푸세요!! 머리로 하면 뽀개집니다..❗️

슬라이딩 윈도우로 0.001초 단위로 움직이면서 변화를 기록하고 매번 최대를 갱신하는 코드로 풀었는데 착하게도 테케중에 끝과 끝을 범위로 갖는게 있었고 이렇게하면 억이 시간을 초과합니다.

이 문제는 N이 크지는 않지만 문제는 0.001ms라는 것입니다. 그래서 힌트를 살짝 봤더니 O(N^2)으로 푸셨다는 게 보이더라고요 그래서 뭔가 N에 즉 트래픽블럭에 집중해보기로 했습니다.

어떻게 하면 좀더 효율적으로 구할 수 있을까 하다가 문제에서 끝시간만 줬고 또 이를 정렬해서 준 것이 단서처럼 보였습니다. 결국 블럭의 끝을 기준으로 1초간 몇개의 블럭이 걸치는지 계산해주면 모든 경우를 빠짐없이 셀 수 있다는 것을 알게되었습니다.

그래서 이 끝을 기준으로 매번 1초의 범위를 정하고 이 범위안에 N개의 블록이 들어오는지 다 따져줘도 N이 2000이기 때문에 타임아웃없이 문제를 풀 수 있습니다. 오히려 비효율적으로 보였던 것이 0.001ms단위여서 슬라이딩윈도우보다 더 좋은 시간복잡도를 갖게 되었습니다!(문제분석이 중요하네요!)

아 그리고 이 문제는 끝에 블록이 걸쳐도 그 블록이 포함된다고 세야합니다. 그리고 0 - 0.999ms가 1초간격입니다.

import collections

def start_ms(finish, T):
    hour, minute, second = finish.split(":")
    time = int(hour) * 3600000 + int(minute) * 60000 + float(second) * 1000
    time -= float(T[:-1]) * 1000
    
    
    return max(0, int(time + 1))

def time_to_ms(time):
    hour, minute, second = time.split(":")
    
    return int(int(hour) * 3600000 + int(minute) * 60000 + float(second) * 1000)

def solution(lines):
    answer = 1
    if len(lines) == 1:
        return answer
    
    records = []
    
    for line in lines:
        date, finish, T = line.split()
        
        start = start_ms(finish,T)
        finish = time_to_ms(finish)
        
        records.append([start, finish])
    
    for i, line in enumerate(lines):
        head = records[i][1]
        tail = head + 999
        cnt = 0
        for i in range(len(lines)):
            if records[i][0] > tail or records[i][1] < head:
                continue
            cnt += 1
        
        answer = max(cnt, answer)
        
    
        
    return answer

후기

일단 2018 카카오는 확실히 요즘과는 결이다르다는 느낌을 받았습니다. 약간 토스코테처럼(그정도는 아니지만) 문제를 많이 주고 N은 작게 줘서 좀 빨리 푸는 느낌과 정말 특정 자료구조 혹은 알고리즘을 문제에 담아서 확인하려는 듯한 느낌의 문제가 많았습니다. 요즘은 여러 알고리즘과 자료구조를 섞어서 내는 느낌인데 말이죠!

악명높은 카카오 코테가 이런식으로 출제된 적도 있구나 하는 흥미로움과 저는 아마 실제로 풀었으면 추석트래픽은 시간안에 멘붕이 와서 못풀지 않았을까..라는 생각이 들었습니다. 요즘으로 따지면 2-3번쯤 나오는 문제를 대비하기에 좋은 난이도인 것 같습니다! 곧 다가오는 2023 공채도 기대되네요(아니 떨려요🙄)