문제 정보

• 총 5 문제 (Level 1 한 문제, Level 2 한 문제, Level 3 두 문제, Level 4 한 문제)
• 제한 시간 : 4시간
• 푼 시간 : 스터디에서 같이 푼 시간 4시간, 따로 푼 시간 30분
• 커트라인 : 3솔
• 내 점수 : 3.5솔

제한 시간과 커트라인은 정확하진 않다.
문제 링크

링크에서 2019 카카오 개발자 겨울 인턴십으로 필터를 적용하면 된다.

크레인 인형뽑기 게임

• 걸린 시간 : 30분 (부끄럽다..)

문제가 굉장히 길어서 문제 설명은 요약 못하겠다.
결론은 이 게임에서 크레인의 움직임 정보가 주어지고, 크레인이 모두 작동된 후 터트려저 사라진 인형의 개수를 구하는 문제이다.

문제 자체가 조건을 쉽게 줘서 Level 1인 것 같다. 조건을 어렵게 주면 삼성전자 구현 문제 처럼 굉장히 어려울 것 같다.

그림처럼 스택을 구현하고, 조건 분기만 잘하면 금방 풀 수 있는 문제이다.
굉장히 간단한 문제인데, 처음이라 긴장을 했는 지 break  위치를 잘못 두어서 자꾸 틀려 30분을 낭비했다.

정답 코드

from collections import deque


def solution(board, moves):
    answer = 0
    stack = deque()
    for move in moves:
        move -= 1
        for n in range(0,len(board)):
            if board[n][move] != 0: # 인형이 있는 경우
                doll = board[n][move]
                board[n][move] = 0 # 인형을 꺼낸다
                stack.append(doll)  # 스택에 인형을 담는다.
                if len(stack) >= 2 and stack[-1] == stack[-2]:
                    stack.pop()  # 인형 두 개 터트린다.
                    stack.pop()
                    answer += 2
                break
    return answer

# 실수 때문에 30분 걸림
# 인형 터트리는 경우만 break 해버리는 어이없는 실수..

튜플

문제

• 걸린 시간 : 15분?

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

여기서부턴 카카오 코테 특징이 나오는 것 같다. Input이 문자열로 들어오는 경우가 굉장히 많다. 문자열을 숫자, 숫자를 문자열로 바꾸는 것을 자유자제로 할 수 있도록 연습해야겠다.

아마 이 문제를 푸는 방법은 여럿 있겠지만, 나는 길이가 짧은 배열의 순서부터 무조건 따르도록 하였다. 그리고 배열의 길이를 늘려가면서 DP처럼 이미 순서가 정해진 숫자면 무시하도록 하였다.

solution 함수 보다 String Input을 Int로 만드는 것이 더 오래걸렸다.(단순하게 구현하니 두 자리수 이상의 경우 배열을 잘못 만드는 경우가 발생했다.)

정답 코드

# String To Arr 함수 구현하는 부분이 시간이 제일 오래 걸렸다.
# 시간 단축하는 방법은 여럿 있겠지만 나는 isfind를 써서 DP처럼 할 수 있게 품
# 걸린 시간 : 15분?

def stringtoarr(inp):
    idx = 0
    num = []
    for c in range(len(inp)):
        if inp[c] == '{':
            continue
        elif inp[c] == '}':
            if idx != 0:
                num.append(int(inp[c - idx:c]))
                idx = 0
            if len(num) != 0:
                arr.append(num)
                num = []
        elif inp[c] == ',':
            if idx != 0:
                num.append(int(inp[c - idx:c]))
                idx = 0
        else:
            idx += 1


arr = []


def solution(s):
    stringtoarr(s)
    arr.sort(key=len)
    answer = []
    isfind = [0 for _ in range(100001)]
    for numarr in arr:
        for num in numarr:
            if isfind[num] == 0:
                isfind[num] = 1
                answer.append(num)

    return answer

불량 사용자

• 걸린 시간 : 1시간~1시간 30분

문제

이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.

DFS 응용 버전인 것 같다. DFS의 문자열 버전 같은 느낌..
그래도 이거 보고 바로 DFS를 떠올린 걸 보니 1년동안 알고리즘 공부를 헛으로 하진 않은 것 같다.

먼저 불량 사용자와 응모자를 어떻게 매칭 시킬건지에 대한 고민이 있었는데, 별이 아닌 부분을 기록하여 그 부분만 비교하는 방식으로 했다. 별이 들어가 있는 부분은 어떤 문자가 들어가도 상관 없으니까!

그 다음에 오류가 났던 부분은, 이런 방식으로 매칭을 하면 문제가 생기는 부분이 있다.

쉽게 극단적인 예를 들면 불량 사용자 아이디가 ["******", "******"] 이고, 응모자 아이디가 ["frodo", "fradi", "crodo", "abc123", "frodoc"] 이라고 해보자.
첫 번째 불량 사용자 아이디를 id1, 두 번째를 id2 라고 했을 때, abc123이 DFS를 순회하면

• id1 에 매칭 되는 경우 : frodoc 이 id2 에 매칭 됨
• id2 에 매칭 되는 경우 : frodoc 이 id1 에 매칭 됨

하지만 이 둘은 같은 경우 이므로, 중복이 발생해 버린다.
이런 경우를 판별하는 방법은 여러가지가 있을 것인데, 나는 판별한 경우를 튜플과 집합을 이용하여 중복을 제거하여 카운트 해주었다.

그리고 내 함수에서 처음부터 불량 사용자 아이디가 ******인 경우를 고려하지 않아서 계속 테스트케이스 4개정도가 오류가 났다. 이 부분을 해결해주니까 해결이 됐다.

정답 코드

# 테스트케이스 1,5,6,9 통과 못함
# 마지막에 중복 없애주면서 처리 했는데, 왜 안되지?
# 처음부터 ******인 경우를 고려안했음. 해결.

banned_star = []
ans = []

def solution(user_id, banned_id):
    # *이 아닌 idx를 담아 두어서, 아이디랑 비교하려고 함.
    for ban in banned_id:
        num = []
        for idx in range(len(ban)):

            if ban[idx] != '*':
                num.append(idx)

        banned_star.append(num)

    # 0번 BAN_ID를 둘러본다.
    usr_idx = 0
    isfound = [0 for _ in range(len(user_id))]
    for usr in user_id:  # User 아이디 순회 하면서
        if len(usr) == len(banned_id[0]):  # 길이가 같으면 대조해본다.
            flag = False
            if len(banned_star[0]) == 0:  # *로만 되어있는 불량 아이디
                flag = True
            else:
                for num in banned_star[0]:
                    if usr[num] != banned_id[0][num]:  # 대조하는 중에 다른 아이디면 멈춤
                        flag = False
                        break
                    else:
                        flag = True

            if isfound[usr_idx] == 0 and flag:
                isfound[usr_idx] = 1
                count(banned_id, user_id, 1, isfound, 1)  # 다음 아이디를 찾는다.
                isfound[usr_idx] = 0

        usr_idx += 1

    # 똑같이 생긴 Ban ID가 존재하는 경우, 중복 되는 경우를 체크 하기 때문에 중복 처리를 해준다. Set으로.
    answer = len(set(list(map(tuple, ans))))
    return answer


def count(banned_id, user_id, banidx, isfound, cnt):
    # 종료 조건(끝까지 탐색한 경우)
    if banidx == len(banned_star):
        if cnt == len(banned_star):
            answer = isfound[:]
            ans.append(answer)
        return

    usr_idx = 0

    for usr in user_id:  # User 아이디 순회 하면서
        if len(usr) == len(banned_id[banidx]):  # 길이가 같으면 대조해본다.
            flag = False
            if len(banned_star[banidx]) == 0:  # *로만 되어있는 불량 아이디
                flag = True
            else:
                for num in banned_star[banidx]:
                    if usr[num] != banned_id[banidx][num]:  # 대조하는 중에 다른 아이디면 멈춤
                        flag = False
                        break
                    else:
                        flag = True

            if isfound[usr_idx] == 0 and flag:
                isfound[usr_idx] = 1
                count(banned_id, user_id, banidx + 1, isfound, cnt + 1)  # 다음 아이디를 찾는다.
                isfound[usr_idx] = 0

        usr_idx += 1

징검다리 건너기

• 걸린 시간 : 1시간
• 효율성 테스트 통과 못함

문제

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

문제가 너무 단순하다. 근데 딱 봐도 조건을 보니 시간초과를 해결해야 하는 문제라는 게 감이 딱 왔다.
처음 생각했을 때, 돌의 개수를 하나씩 카운트하기 보다, 돌의 개수를 최소로 정렬을 하고 그 배열의 앞쪽부터 대입해가며 되는 지 안되는 지 판단해보았다.
그래도 이 방법도 배열이 다 하나씩 차이가 난다면 시간 초과가 날 것 같은게 뻔해보였다.
결과는 역시 정확성만 통과하고 효율성 테스트는 하나도 통과하지 못했다.
뭔가 이분 탐색 같은데, 이분 탐색을 어떻게 구현해야 할지 감을 잡지 못했다.

정확성만 통과한 코드 (0.5솔)

def solution(stones, k):

    if len(stones) == k:
        answer = max(stones)
        return answer
    if k == 1:
        answer = min(stones)
        return answer
    arr = []
    for idx in range(len(stones)):
        num = [stones[idx], idx]
        arr.append(num)

    arr.sort()  # 정렬은 한번만 하면 된다.
    before = 0
    answer = 0
    idxarr = [0 for _ in range(len(arr))]

    for num in arr:
        if before != num[0]:    # 숫자가 커졌음
            cont = 1
            for i in range(len(arr) - 1):
                if idxarr[i] != 0 and idxarr[i+1] != 0:
                    cont += 1
                else:
                    cont = 1
                if cont == k:
                    return answer

            before = num[0]
            answer = num[0]

        idxarr[num[1]] = 1

정답 코드

이분 탐색을 이용한 코드이다. 이 부분은 혼자 생각하지 못해서 0.5솔로 하고 질문을 좀 찾아보았다. (정답 코드를 보진 않았다.)

• 건널 수 있는 최소값을 0
• 최대를 돌의 max값으로 둔다.
• 중간값일 때 건널 수 있는지 없는지를 판별한다.

어떻게 보면 내처음 코드와 크게 다르지 않지만, 이분 탐색으로 경우를 nlog(n)으로 줄인다는 게 큰 차이이다.
조금만 생각을 바꾸면 풀었을 수도 있을텐데, 쉽지 않았다.

# 이분 탐색 이용해야 풀리는 문제
# 어렵다.

def solution(stones, k):
   answer = 0
   left = 0
   right = max(stones)
   while left <= right:
       mid = int( (left+right) / 2)
       arr = []
       count = 0
       for stone in stones:
           arr.append(stone - mid)
       print(arr)

       for num in arr:
           if count < k:
               if num <= 0:
                   count += 1
               else:
                   count = 0

       if count < k:  # 가능
           left = mid+1
       else: # 불가능
           right = mid-1
           answer = mid

   return answer

코드는 간단하다. 생각이 간단하지 않을 뿐.

호텔 방 배정

문제

전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

이 문제 또한 너무 단순하다. 딱 봐도 시간초과 줄이는 게 핵심인 것 같은 문제다. 학교에서 비슷한 문제를 알고리즘 수업 때 배운 기억이 있었다. 기억을 더듬어 문제를 풀어보았다.

정확성만 통과한 코드 (0.5솔)

# 시간 초과 날 것 같았음..
# 정확성 만점, 효율성 0점. -> 0.5점 짜리.

def solution(k, room_number):
    rooms = [i for i  in range(k+2)]    # 1번 부터 k번 방까지 가장 작은 번호를 가리키도록. 
    #k값이 뭐든 런타임 에러가 안나기 위해 k+1까지 초기화.
    answer = []
    for num in room_number:
        if num == rooms[num]:
            answer.append(num)
            rooms[num] = rooms[num+1]
        else:
            while num != rooms[num]:
                rooms[num] = rooms[num+1]
                num = rooms[num+1]
            answer.append(rooms[num])
            rooms[num] = rooms[num+1]
    return answer

시간초과가 날 것 같았다. 왜냐면 방 번호를 노드라고 치고, 부모 노드를 찾는 데에 노가다를 하기 때문이다.
도저히 모르겠어서 정답을 찾아보았다.
나랑 거의 알고리즘이 비슷한데, 나처럼 배열을 선언해놓는 것이 아니라 딕셔너리에 하나씩 추가하면서 딕셔너리를 탐색하는 게 가장 핵심이었다.
visit 쓰는 느낌을 이 코드에 추가해보았더니 테스트 케이스 5,6,7에서 시간초과가 났다. 이런 문제는 배열을 쓰면 안되는 구나

정답 코드

# 정답 코드
# 내 코드랑 조금 느낌이 같은 듯 다른데, 딕셔너리를 써서 바로 보내주는게 핵심이다.
# 그리고 쫓아가는게 아니라, 정답을 갖고 다 업데이트 해주는 것.
def solution(k, room_number):
    rooms = {}
    answer = []
    for num in room_number:
        n = num
        visit = [n]
        while n in rooms:
            n = rooms[n]
            visit.append(n)
        answer.append(n)
        for v in visit:
            rooms[v] = n+1
    return answer

레벨 4치고는 좀 쉬운 문제..? 오래 된 문제라 그런것 같기도 하다. 당장 다음주가 기대되는 하루다.