카카오 2019 겨울 인턴십 코딩테스트 풀이입니다
1. 크레인 인형 뽑기 게임
def solution(board, moves):
stack = []
answer = 0
for move in moves:
for b in board:
if b[move - 1] != 0:
stack.append(b[move - 1])
b[move - 1] = 0
break
if len(stack) >= 2 and stack[-2] == stack[-1]:
stack.pop()
stack.pop()
answer += 2
return answer- 5 <= len(board) <= 30, 1 <= moves <= 1000개
- 최대 30 x 30 x 1000(900000) 만큼의 시간이 소요되므로 위 풀이로 충분히 커버가 가능하다
- board의 모든 층의 move - 1번째 숫자를 확인하여 0이 아닐 경우(인형이 존재할 경우)에는 해당 숫자를 stack에 push 해주고 해당 부분을 0으로 바꿔줌(인형이 뽑힘)
- 0일 경우에는 앞의 과정이 나올 때 까지 반복
- stack에 2개 이상의 숫자가 있을 경우 맨 위 숫자와 바로 다음 숫자를 비교해서 둘이 같을 경우에는 두 숫자를 stack에서 pop(그리고 answer += 2)
- answer은 삭제된 인형의 갯수를 뜻한다
2. 튜플
from collections import Counter
def solution(s):
s = s.replace("{", '').replace("}", '')
s_l = list(map(int, s.split(',')))
count = Counter(s_l).most_common()
answer = [k for (k, v) in count]
return answer- {{a1}, {a1, a2}, {a1, a2, a3}, ... ,{a1, ... , an}} 일 경우 (a1, a2 ... an)와 같다
- 즉 {} 내부의 갯수가 적을 때 먼저 나온 원소가 앞에 있다는 것을 말한다
{2} <- {2, 1}에 비해 내부 갯수가 더 적음
이 때 2가 1보다 먼저 등장했으므로 (2, 1) 과 같다 - 많이 나온 숫자일수록 튜플의 앞쪽에 있다는 것을 말한다
- {{a1}, ..., {a1, a2, ... an}}과 같은 형태로 되어 있는 문자열의 {} 부분을 없앰(replace)
- , 기준으로 원소를 나누어(split) 리스트로 만듦
- Counter 라이브러리를 이용해 리스트 원소의 갯수를 세고, most_common() 함수를 이용해 원소 갯수 순서대로 k, v를 정렬
- k 값만 모아서 return
3. 불량 사용자
from itertools import permutations
def solution(user_id, banned_id):
answer = []
p_l = list(permutations(user_id, len(banned_id)))
for p in p_l:
t = True
for (u, b) in zip(p, banned_id):
if len(u) != len(b):
t = False
break
for (u_c, u_b) in zip(u, b):
if u_b == '*':
continue
if u_c != u_b:
t = False
break
if t:
p = set(p)
if p not in answer:
answer.append(p)
return len(answer)- 1 <= user_id <= 8 이므로 모든 경우에 대한 완전 탐색 가능
- user_id 에서 len(banned_id) 개를 뽑은 순열을 만듭니다
각 순열의 원소 (p1, p2..., pn) 는 (ban1, ban2..., ban n)과 대응됩니다 - (p1, ban1), (p2, ban2) ... (pn, ban n)을 각각 비교를 하게 됩니다
- pn, ban n의 길이가 같을 경우만 비교합니다
- pn, ban n의 문자열을 하나하나 비교를 해서 대응하는 지를 확인합니다
- (p1, ban1).....(pn, ban n) 까지 모두 대응할 경우에 그 순열을 집합으로 만듭니다
- 기존에 해당 집합이 있었는지를 확인해서 없었다면 answer list에 push 합니다
- answer list의 길이를 return 합니다
4. 호텔 방 배정
from collections import defaultdict
def solution(k, room_number):
r = set()
p = defaultdict(int)
answer = []
for room in room_number:
now = room
visit = [room]
while now in r:
now = p[now]
visit.append(now)
for v in visit:
p[v] = now + 1
r.add(now)
answer.append(now)
return answer- 집합 r(방문한 room), dict p(현재 room이 비지 않았을 경우 다음에 방문할 수 있는 room)을 선언
- room_number에 있는 room을 돌게 되고 방문한 room들을 visit 리스트에 append 합니다
- 만일 현재 방을 방문한 적이 있다면, 다음 방으로 이동을 하고 이 과정을 빈 방이 나올 때 까지 반복합니다
- 빈 방이 나올 경우 현재 방을 방문 처리 하고, 그 과정에서 방문한 모든 방들의 다음 방(p)를 현재 방의 다음 방으로 갱신해줍니다
- 방문 처리한 순서를 담은 리스트를 반환합니다
5. 징검 다리 건너기
def solution(stones, k):
start, end = 0, max(stones)
answer = 0
while start <= end:
temp = []
mid = (start + end) // 2
cnt = 0
pos = True
for s in stones:
if s - mid + 1 <= 0:
cnt += 1
if cnt >= k:
pos = False
break
else:
cnt = 0
if pos:
start = mid + 1
if answer < mid:
answer = mid
else:
end = mid - 1
return answer- 모든 경우에 대해 순차적으로 접근할 경우 많은 시간 소요(최대 200,000,000 stones 길이)
- 이분탐색을 이용해서 진행
- start(최소 0번), end(최대 max(stones)번)을 선언하고, 중간 값인 mid를 선언합니다
- 여기서 mid는 징검다리를 건널 수 있는 인원수
- 징검다리를 돌면서 mid의 값들을 빼주고, 0 이하의 값이 연속되는 cnt를 세어줍니다
- cnt >= k 일 경우 그만큼의 인원수는 건널 수 없다는 것을 뜻하기 때문에 값을 줄여줍니다(end = mid - 1)
- cnt < k일 경우에는 건너는 것이 가능하기 때문에 answer 값과 mid 값을 비교해서 큰 값으로 mid 값을 갱신해주고, 더 많은 인원수를 옮길 수 있는지를 확인합니다(start = mid + 1)
이상하게 카카오 문제는 2단계도 4단계처럼 느껴지는 난이도인 것 같아요 하하...
언젠가는 가볍게 재미로 올쏠을 하는 날이 올 수 있도록 노력해보겠습니다
나는야 누워있는 개발머신