2021 공채 코딩테스트 python 풀이
오늘은 카카오 2021 공채 코테를 풀어보았다. 5시간동안 총 5솔을 했고 6번은 1시간 40분이나 도전했는데 비트마스킹으로 풀어도 5개가 시간초과가 났다. 아마 뭔가 로직을 더 다듬었어야 했을 것같은데 그 부분도 살펴봐야겠다.
1번 신규 아이디 추천
이 문제는 순서대로 잘 풀면 되는 문제였다. 문자열 조작이었고 차근차근 풀어주면 무리없이 풀 수 이쓴 문제다. 단계마다 조금씩 아이디어를 잘 쓰면 더욱 쉽게 풀 수 있긴하지만 그냥 막 풀어도 머리가 조금 아플 뿐 큰 차이는 없는 문제다.
특히 3단계는 ".."가 없을 때까지 모든 ".."를 "."로 바꿔주면서 풀면 "..."같은 것들도 복잡하게 생각할 필요없이 풀 수 있다.
또한 4단계는 인덱싱하는 부분이 나오는데 앞에서 범위체크를 하고 접근해야한다.
chars = ("-", "_", ".")
def solution(new_id):
# 1단계
new_id = new_id.lower()
# 2단계
i = 0
while i < len(new_id):
if not new_id[i].isalpha() and not new_id[i].isdigit() and new_id[i] not in chars:
new_id = new_id[:i] + new_id[i+1:]
else:
i += 1
# 3단계
while ".." in new_id:
new_id = new_id.replace("..",".")
# 4단계
if new_id and new_id[0] == ".":
new_id = new_id[1:]
if new_id and new_id[-1] == ".":
new_id = new_id[:-1]
# 5단계
if not new_id:
new_id = "a"
# 6단계
if len(new_id) >= 16:
new_id = new_id[:15]
if new_id[-1] == ".":
new_id = new_id[:-1]
# 7단계
if len(new_id) <= 2:
while len(new_id) < 3:
new_id += new_id[-1]
return new_id2. 메뉴 리뉴얼
이 문제는 조건을 잘 체크해줘야하는 문제이다.
- 최소 2가지 이상의 구성
- 최소 2명이상 주문했던 구성
- 메뉴조합은 오름차순으로 작성
- 그 중 가장 많은 것
먼저 범위가 다 작다. 즉 모든 주문에 대해서 course에 들어있는 만큼의 조합을 만들어 딕셔너리에 저장해주고 나중에 코스구성개수마다 처리해주면 되는 문제이다.
위에 조건들 중 첫번째는 손님들도 2개이상씩 시키고 course도 2이상의 수가 주어지니까 자동해결이다. 두번째는 나중에 주문 수가 1인 구성은 제외시켜줘야한다. 그리고 메뉴조합이 오름차순이어야하기때문에 메뉴조합을 저장할 때 오름차순으로 만들고 저장해줘야함을 기억하자.
풀이 순서
모든 orders에 대해 반복 : o
- 모든 course 반복 : c
- combination(o, c) -> 여기서 정렬해서 딕셔너리에 key = c에 넣어주기
모든 course 반복 : c
- 딕셔너리에서 key를 통해서 c개의 조합 메뉴가져오기
- Counter로 빈도알아내기 -> 여기서 max뽑기
- max가 1이면 넘어가기
- max가 1이상이면 Counter돌면서 빈도가 max인 메뉴들만 정답에 담기
정답 정렬해서 출력
import itertools
import collections
def solution(orders, course):
answer = []
menu = collections.defaultdict(list)
# 각 개수별로 조합 정리
for c in course:
for order in orders:
for combi in itertools.combinations(sorted(order),c):
menu[c].append("".join(combi))
# 개수별로 최대 빈도 메뉴구성 구하기
for n in menu.keys():
freqs = dict(collections.Counter(menu[n]))
max_cnt = max(freqs.values())
if max_cnt == 1:
continue
for food in freqs.keys():
if freqs[food] == max_cnt:
answer.append(food)
return sorted(answer)3. 합승 택시 요금
이 문제는 그래프문제도 최단거리를 구하는 정석적인 문제이다. 보니까 플로이드와 다익스트라 두가지 모두 풀이가 가능하다. 나는 다익스트라로 풀었다.
결국 이문제는 분기가 나뉘는데 출발점에서 같이 출발해 중간지점까지 간다. 그리고 여기서 A, B로 각자 나뉘어서 간다. 이렇게 3개의 구간을 모두 최소 비용으로 가면 된다. 여기서 중간지점은 문제를 읽어보면 알겠지만 문제의 모든 노드가 가능하다. 심지어 A에서 내려도되고 B에서 내려도되고 아예 합승을 안해도(S)된다.
따라서 나는 다익스트라로 모든 노드에서 모든 노드까지의 최소거리를 구했다.
import heapq
import collections
def solution(n, s, a, b, fares):
answer = float('inf')
costs = [[float('inf')] * (n+1) for _ in range(n+1)]
paths = collections.defaultdict(list)
# 길 기록
for c,d,f in fares:
paths[c].append([d,f])
paths[d].append([c,f])
# start부터 최단거리 찾기
def shortcut(start):
pq = [[0, start]]
costs[start][start] = 0
while pq:
cost, node = heapq.heappop(pq)
for nnode, c in paths[node]:
if costs[start][nnode] > cost + c:
costs[start][nnode] = cost + c
heapq.heappush(pq, [cost+c, nnode])
for i in range(n):
shortcut(i+1)
for i in range(n):
answer = min(answer, costs[s][i+1] + costs[i+1][a] + costs[i+1][b])
return answer아래은 플로이드로 푼 방법이다. 결국 모든 노드에서 모든 노드까지의 최단거리를 구하는 방법만 다를 뿐 그 뒤로는 같다.
def solution(n, s, a, b, fares):
answer = float("inf")
costs = [[float('inf')] * (n+1) for _ in range(n+1)]
for c,d,f in fares:
costs[c][d] = f
costs[d][c] = f
for i in range(1,n+1):
costs[i][i] = 0
for i in range(1,n+1):
for h in range(1,n+1):
for t in range(1,n+1):
if costs[h][i] + costs[i][t] < costs[h][t]:
costs[h][t] = costs[h][i] + costs[i][t]
for i in range(n):
answer = min(answer, costs[s][i + 1] + costs[i + 1][a] + costs[i + 1][b])
return answer
4. 순위 검색
이 문제는 잘 생각하고 구현을 잘해야하는 문제이다. 그리고 여러가지를 고려해야 시간초과를 하지 않을 수 있다. 그렇다고 엄청 어려운 문제는 아니다. 어떤 자료구조로 저장할지가 어렵고 그게 정해지면 그뒤로는 할만한 문제이다.
일단 조건 + 점수로 분류를 할 수 있는데 조건은 매칭이고 점수는 범위이다. 지원자를 분류하는 방법은 두가지이다.
-
지원자는 언어 + 직군 + 경력 + 음식 -> 3 x 2 x 2 x 2 = 24가지의 조합 중 하나에 해당할 텐데 이것을 key로 하고 여기에 점수를 넣어주는 것이다.
-
쿼리는 언어 + 직군 + 경력 + 음식 -> 4 x 3 x 3 x 3 = 108가지의 조합 중 하나에 해당할 텐데 이것을 key로 하고 지원자의 점수를 넣어주는 것이다.
첫번째는 지원자를 넣기는 쉽고 쿼리에서 "-"를 처리할때는 와일드카드처럼 처리해줘야하는 불편함이 있다. 두번재는 지원자를 넣을 때 "-"까지 고려해서 넣어줘야하지만 쿼리검색은 바로 찾을 수 있다.
나는 두번째로 구현하기로 했다. 이렇게 특수한 상황을 "-"라는 또하나의 선택지로 생각하면 조금더 생각하기가 편한 것같다.
마지막으로 중요한 것 바로 이분탐색이다. 점수는 범위탐색을 해야한다. 만약 모든 점수를 하나씩 비교해서 범위안에 드는지를 판단하면 복잡도가 O(N)이다. 쿼리의 수가 많기때문에 병목지점이 될 수 있다. 따라서 "범위"라는 점에서 이분탐색을 떠올려야한다.
정말로 마지막!!! 이분탐색을 하려면 정렬을 해야하는데 query를 검색할 때마다 정렬을 하고 이분탐색을 하면 매번 정렬비용이 든다. 이러면 시간초과.. 따라서 query검색전에 전부 한번 정렬을 하고 시작하자.
import collections
import bisect
def solution(info, query):
answer = []
combis = collections.defaultdict(list)
# 가능한 모든 조합에 점수 등록
for i in info:
lang, part, career, food, score = i.split()
for l in [lang,"-"]:
for p in [part,"-"]:
for c in [career, "-"]:
for f in [food, "-"]:
combis[l+p+c+f].append(int(score))
for value in combis.values():
value.sort()
for q in query:
q = q.split()
score = q[-1]
lang, part, career, food = q[0], q[2], q[4], q[6]
scores = combis[lang+part+career+food]
idx = bisect.bisect_left(scores,int(score))
answer.append(len(scores) - idx)
return answer5. 광고 삽입
이 문제는 누적합 자료구조를 써서 빠르게 구할 수 있다. 그리고 이런 시간의 범위문제는 그 문제에서의 시간계산법, 배열을 쓸 때 인덱스에 대해서 정확히 맞추고 시작해야지 대충하다가 오류가 터지면 거기부터 지옥시작이다.
먼저 누적합 자료구조를 보자. 이는 누적 사용자 시간을 계산하는 곳에 쓸 것이다. 물론 각 구간을 다 돌아다니면서 + 연산으로 누적합을 계산해도되지만 이는 시간이 너무 오래걸린다.
따라서 1-3까지 한개씩 올려주는 것은 1번에 +1 그리고 4번에 -1을 표시하고 x[n] = x[n] + x[n-1]을 통해서 나의 전과 나를 더해서 나의 값이 되도록 한번에 계산하면 원하는 결과 즉 1-3까지 1 1 1이 쌓이는 것을 알 수 있다.
근데 우리는 지금 시간의 개념을 배열로 표현해야하기때문에 아래와 같이 상황을 정리해야한다. 일단 위가 시간인데 1초부터 3초까지 총 2초의 실행시간을 가진다. 이를 배열로 처리하면 약간의 차이가 있다. 배열은 한칸씩을 나타내는데 시간은 시각으로 쪼개져있다. 따라서 배열하나가 1초의 실행시간이라고 보면된다.
즉 인덱스 i는 i초부터 i+1초까지 총 1초동안 실행한 것이다.
그럼 1-3초는 배열에서 arr[1]에 +1 arr[3]에 -1을 해서 누적합 처리를 해줘야할 것이다. 이렇게 그림을 그리고 푸는 것을 추천한다. 중간중간 엄청 헷갈리기때문이다.
이렇게 누적합으로 실행한 사람들의 누적합을 처리해줬다면 슬라이딩 윈도우로 포인터 두개를 이용해서 광고시간안에 최대의 시청자를 보유한 시간을 찾아낸다. 포인터가 하나씩 밀리기때문에 sum은 새로추가되는 뒤에 값을 더하고 나가는 앞에 값을 빼주면 항상 모두 계산해주지 않아도 된다.
def sec_to_time(sec):
hour, mod = divmod(sec,3600)
minute, sec = divmod(mod,60)
return str(hour).zfill(2) + ":" + str(minute).zfill(2) + ":" + str(sec).zfill(2)
def time_to_sec(time):
hour, minute, second = time.split(":")
return 3600 * int(hour) + int(minute) * 60 + int(second)
def solution(play_time, adv_time, logs):
answer = 0
play_time = time_to_sec(play_time)
total_sum = [0] * (play_time + 1)
# 누적합 기록
for log in logs:
start, finish = log.split("-")
start = time_to_sec(start)
finish = time_to_sec(finish)
total_sum[start] += 1
total_sum[finish] -= 1
# 누적합 계산
for i in range(1,play_time):
total_sum[i] += total_sum[i-1]
# 최대구간찾기 : 슬라이딩 윈도우
adv_time = time_to_sec(adv_time)
prev = max_total = sum(total_sum[:adv_time])
i = 0
j = i + (adv_time-1)
while j < play_time-1:
j += 1
total = prev + total_sum[j] - total_sum[i]
prev = total
i += 1
# 최대갱신
if total > max_total:
max_total = total
answer = i
return sec_to_time(answer)6. 카드짝 맞추기
이 문제는 찾아보니 다들 삼성기출과 같은 스타일이라고 한다. 복잡한 길찾기 문제이다. 일단 길찾기문제가 나오면 아래와 같은 것들을 점검해야한다
- 매번 어디로 움직일 수 있나
- 중복은 어떻게 체크할 것인가
- BFS인지 다익스트라인지
- cost는 무엇인지
- 언제 끝나는지
보통 이중 한 두개를 까다롭게 내면 어려워진다. 3번의 합승택시는 이 5가지가 매우 명확하다. 그래서 쉽다. 이 문제는 1,2번이 까다롭다 특히 2번..
나는 결국 5개의 타임아웃을 내서 맞추지 못했다. 로직은 맞지만 더 다듬어 시간을 절약해야하는데 내가 할 수 있는 최선을 이미 다했다고 판단하여 답을 봐야했다.
먼저 내가 푼것을 설명하자면
-
매번 어디로 움직일 수 있나
상하좌우, CTRL + 상하좌우 , Enter -> 9가지 행동이 가능하다 -
중복은 어떻게 체크할 것인가
중복은 카드들의 유무와 카드들의 선택여부 그리고 커서의 위치의 조합으로 중복을 체크할 수 있다
나는 카드의 유무와 선택여부는 비트마스킹으로 커서위치는 그냥 행열값으로 처리했다 -
BFS인지 다익스트라인지
사실 이부분이 나는 좀 헷갈렸다. 일단 말하자면 BFS이다. 모든 움직임이 비용이 1이기 때문에 먼저 방문한 것이 제일 비용이 적다. 따라서 방문여부만 따지면 된다 -
cost는 무엇인지
비용은 키보드를 누른 횟수이다 -
언제 끝나는지
카드들이 모두 빠지면 끝난다.
일단 다른 사람들의 풀이를 봤을 때 내가 visited조건을 너무 잘게 잡아서 빼먹은 것이 있는 것같다. 또다른 방법은 카드 순서를 미리 정하고 들리는 방식도 있었다. 이부분은 나중에 보충을 해야겠다..
import heapq
# 중복체크 -> 카드의 상태, 뒤집은 상태
# 상하좌우, CRTL + 상하좌우, Enter -> 9개
# 카드가 다 없어진 상태의 처음 키조작횟수
def solution(board, r, c):
drc = [[0, 1], [0, -1], [1, 0], [-1, 0]]
def is_valid(x, y):
if 0 <= x <= 3 and 0 <= y <= 3:
return True
return False
# 카드기록
cards = []
for i in range(4):
for j in range(4):
if board[i][j]:
cards.append([i, j])
# 최소조작횟수
q = [[0, r, c, (1 << len(cards)) - 1, 0, ""]]
# 카드유무/선택유무/r/c
visited = [[[[float(False)] * 4 for _ in range(4)] for _ in range((1 << len(cards)))] for _ in
range((1 << len(cards)))]
# 모든카드가 있고/ 선택되지 않았고
visited[(1 << len(cards)) - 1][0][r][c] = True
while q:
cost, rr, cc, card, select, s_card = heapq.heappop(q)
if card == 0:
return cost
# 상하좌우
for i in range(4):
nr = rr + drc[i][0]
nc = cc + drc[i][1]
if is_valid(nr, nc) and not visited[card][select][nr][nc]:
visited[card][select][nr][nc] = True
heapq.heappush(q, [cost + 1, nr, nc, card, select, s_card])
# CTRL + 상하좌우
for i in range(4):
nr = rr
nc = cc
# 가능한 곳 까지 이동
while is_valid(nr + drc[i][0], nc + drc[i][1]):
nr = nr + drc[i][0]
nc = nc + drc[i][1]
if [nr,nc] in cards and card & 1 << cards.index([nr,nc]):
break
if not visited[card][select][nr][nc]:
visited[card][select][nr][nc] = True
heapq.heappush(q, [cost + 1, nr, nc, card, select, s_card])
# Enter
if [rr, cc] in cards and card & 1 << cards.index([rr, cc]) and not select & 1 << cards.index([rr, cc]):
# 카드선택
s_card += str(cards.index([rr,cc]))
select ^= 1 << cards.index([rr,cc])
# 두장선택됐으면
if len(s_card) == 2:
c1 = board[cards[int(s_card[0])][0]][cards[int(s_card[0])][1]]
c2 = board[cards[int(s_card[1])][0]][cards[int(s_card[1])][1]]
# 같은 카드면 카드 빼기
if c1 == c2:
card ^= 1 << int(s_card[0])
card ^= 1 << int(s_card[1])
if card == 0:
return cost + 1
select ^= 1 << int(s_card[0])
select ^= 1 << int(s_card[1])
s_card = ""
if not visited[card][select][rr][cc]:
visited[card][select][rr][cc] = True
heapq.heappush(q, [cost + 1, rr, cc, card, select, s_card])비트마스킹 기본연산
이번에 비트마스킹을 쓰면서 자주 쓰였던 기본연산들을 정리해보고자한다.
left shift
시프트는 비트마스킹에 가장많이 쓰이는 연산이다 옆으로 옮겨주는 것인데 배열의 인덱스처럼 0부터 시작한다고 생각하면 좋다
1 << 0
> 1
1 << 3
> 1000비트세팅
먼저 카드 5장의 상태를 저장하는 비트를 세팅해본다고하면 아래와 같다.
(1 << 5) - 1
> 11111하지만 이런 인덱스를 가진 배열을 선언하려면 하나 크게 사이즈를 잡아줘야하니까 -1만 빼주면 된다.
arr = [True] * (1 << 5)비트토글
만약 S를 10011이라고 할 때 뒤에서 두번째를 바꾸고싶다면
S ^= (1 << (2-1))
> 10011 xor 00010 = 10001비트확인
특정 비트를 체크하고 싶을때 쓰면 되는 연산이다. S를 10011이라고할 때 뒤에서 두번째를 체크하고싶다면 아래처럼 연산하면 해당자리가 1이면 1 0이면 0이 나온다.
S & (1 << (2-1))
> 10011 AND 00010 = 1후기
7번은 손댈 생각도 안해봤다.. ㅎ 역시 카카오 공채는 쉽지않다. 이 시험은 3.5에서 4솔이 합격선이었던 것 같다. 역시 정확하게 앞문제를 얼마나 안정적이게 맞추느냐가 시험에서는 훨씬 중요한 것 같다. 그래야 뒷 문제도 편하게 도전해볼 수 있다!
