[coding test] 2019 카카오 개발자 겨울 인턴십 문제

1,2,3번은 평이한 난이도라 코드만 keep. 10~20줄 내외다.(각 문제당 약 2~30분 동안 풀었음)

 

1.크레인 인형뽑기 게임

from collections import deque
def solution(board, moves):
    leng = len(board)
    q = deque([])
    count = 0
    for i in moves:
        for j in range(leng):
            if board[j][i - 1] != 0:
                q.append(board[j][i - 1])
                if len(q) >1 and q[len(q)-1]==q[len(q)-2]:
                    count += 2
                    q.pop()
                    q.pop()
                board[j][i - 1] = 0
                break
    return count

2. 튜플

def solution(s):
    ss = s[2:-2].split('},{')
    ss_len = [len(i) for i in ss]
    ss_len.sort()
    sorted_len = ss_len.copy()
    for i in range(len(ss_len)):
        for j in ss:
            if ss_len[i] == len(j):
                sorted_len[i] = j
    sorted_len = [i.split(',') for i in sorted_len]
    result = []
    for i in sorted_len:
        for j in result:
            if j in i:
                i.remove(j)
        result.append(i[0])
    result = [int(i) for i in result]
    return result

3. 불량 사용자

from itertools import product
def solution(user_id, banned_id):
    suspected_id = []
    for i in banned_id:
        suspected = []
        for j in user_id:
            if len(i)==len(j):
                score = 0
                for z in range(len(i)):
                    if i[z] != '*' and i[z] == j[z]:
                        score +=1
                if score == len(i)-i.count('*'):
                    suspected.append(j)
        suspected_id.append(suspected)
    confirm = list(product(*suspected_id))
    confirm = [sorted(list(i)) for i in confirm if len(set(i))==len(i)]
    answer = len(list(set(map(tuple,confirm))))
    return answer

4. 호텔 방 배정

# 정확 100, 효율 100
def solution(k, room_number):
    room_dic = {}
    ret = []
    for i in room_number:
        n = i
        visit = [n]
        while n in room_dic:
            n = room_dic[n]
            visit.append(n)
        ret.append(n)
        for j in visit:
            room_dic[j] = n+1
    return ret

# 내 풀이 : 정확 100, 효율 0
from collections import deque
def solution(k, room_number):
    q = deque([i for i in range(1,k+1)])
    confirm_num = room_number.copy()
    leng = len(room_number)
    for i in range(leng):
        if room_number[i] in q:
            q.remove(room_number[i])
            confirm_num[i] = room_number[i]
        else:
            p = q.copy()
            for j in p:
                if j > room_number[i]:
                    confirm_num[i] = j
                    q.remove(j)
                    break
    return confirm_num

• 너무 모든 문제를 collections으로 풀려고 했다.
• append의 시간복잡도는 O(1)이다(써도 된다!) remove나 del은 조금 곤란..

5. 징검다리 건너기

# 정확 100, 효율 100
def check(stones,k,n):
    temp = k
    for stone in stones:
        if stone < n:
            temp -= 1
        else:
            temp = k

        if temp == 0:
            return False
    return True

def solution(stones, k):
    l = 0
    r = 200000000
    while l<r-1:
        n = (l+r)//2
        canJump = check(stones,k,n)

        if canJump:
            l = n
        else:
            r = n

    rok = check(stones,k,r)
    if rok:
        return r
    else:
        return l

• 아래는 패기롭게 구현해봤지만 test case 고작 2개 성공(어디가 에러인지 찾는 중)

count = 0
con = '0, '*k
con = con[:len(con)-2]
while True:
    stones = [i - min([i for i in stones if i > 0]) if i - min([i for i in stones if i > 0]) >= 0 else i for i in stones]
    count += 1
    if con in str(stones):
        break