2022 공채 코딩테스트 python 풀이
가장 최근 기출인 2022 공채 코테를 풀어봤습니다. 2022는 난이도가 다른 해에 비해 평이하게 나왔다는 평이 많더라고요. 하지만 마지막 문제는 정말 건들지도 못할정도로 어렵더라고요. 저는 처음풀어보는 것은 아니지만 4시간동안 6개를 풀었습니다!
1. 신고 결과 받기
이 문제는 사용자들끼리 신고를 하고 이것을 파악해서 K번 넘게 신고를 받은 사람들을 "신고한 사람"들에게 메일을 보내는 문제입니다. 구현문제고 딕셔너리를 잘 활용해서 풀면 어렵지 않게 풀립니다. 이 문제는 신고한 사람들을 역추적해야하기 때문에 신고를 당한 사람을 key로해서 value에 신고를 한 사람들을 모아주면 됩니다.
물론 이외에도 다양한 방법들이 있을 것 같습니다. 저는 defaultdict(set)을 이용해서 한 사람이 같은 사람을 여러번 신고한 것을 한번으로 처리해줬습니다.
import collections
def solution(id_list, report, k):
answer = []
mails = collections.defaultdict(int)
black_list = collections.defaultdict(set)
for r in report:
mem1, mem2 = r.split()
black_list[mem2].add(mem1)
for b in black_list.keys():
if len(black_list[b]) >= k:
for mem in black_list[b]:
mails[mem] += 1
return [ mails[i] for i in id_list ]2. k진수에서 소수 개수 구하기
이 문제는 소수인지 아닌지를 먼저 파악하지 말고 소수가 될 수 있는 후보를 먼저 수집하는 것이 훨씬 간단한 방법입니다. 그렇다면 어떻게 P의 후보를 뽑으면 될까요?
결국 규칙은 "0"으로 둘러쌓여있어야 한다는 것입니다. split이 떠오르네요! 처음 떠올렸던 방법은 모든 "00" -> "0"으로 만들어줘서 "0"으로 깔끔하게 split될 수 있게 하는 방법입니다. 근데 이 방법의 문제는 이렇게 깔끔하게 처리하기 힘들다는 점입니다.
"0410".split("0")
> ['', '41', '']그렇다면 굳이 이렇게 할 필요가 없습니다. 그냥 "0"으로 나눠주고 공백들은 무시해주면 됩니다. 이제 나머지는 소수인지 판단하는 것과 K진수로 만들어주는 것입니다.
소수판단
소수판단에서 중요한 것은 두가지입니다. 일단 소수의 정의를 이용할 것입니다.
1과 자기자신만을 약수로 갖는 수
그럼 2부터 자기전까지 모든 수로 나눠보고 나누어 떨어지면 소수가 아닌 것입니다. 물론 이렇게 해도 맞지만 이렇게 하면 간혹 큰 수를 판단할 때 시간이 낭비가 되는 경향이 있습니다.
1. 제곱근
좀더 다듬어보면 2부터 제곱근까지만 판단해도 알 수 있습니다. 약수는 짝을 이뤄서 발견됩니다. 16 = 2 x 8 과 같이요! 따라서 대칭성이 있습니다. 이 대칭의 중간지점이 바로 제곱근이죠 16은 4를 기준으로 나뉩니다. 따라서 2-제곱급까지 나눠봤을 때 나눠떨어지지 않았다면 그 뒤로도 그럴 것임을 해보지 않고도 알 수 있습니다.
2. 예외처리
두번째로 조심해야할 점은 내가 짠 코드가 1을 잘 판단해 주고있는가 입니다. 1은 소수중에서도 특수한 케이스입니다. 따라서 1이 판단이 되는지 그렇지 않다면 예외처리를 꼭 붙여줘야합니다.
K 진수만들기
K진수를 만드는 것은 소인수분해를 이용하면 됩니다. 숫자를 K로 나눈 몫을 계속해서 K로 나눠줍니다. 그리고 나머지는 계속해서 거꾸로 붙여줍니다. 이는 흔히 우리가 10진수를 K진수로 바꿀 때 하는 과정입니다.
예외처리
여기서 또 주의해야할 점이 0에 대한 처리입니다. K진수를 구하는 것을 다양하게 구현할 수 있는데 저는 몫이 K보다 작아지면 끝내고 마지막으로 몫을 붙이고 끝냅니다. 만약 몫이 0이 될때까지 계속 붙여준다면 num이 0이 들어왔을 때 처리를 해주지 못합니다. 따라서 본인이 짠 코드에서 0에대한 처리가 잘 되는지 확인해야합니다.
def is_prime(num):
if int(num) == 1:
return False
mid = int(num ** (1/2))
for i in range(2,mid+1):
if not num % i:
return False
return True
def k_notation(num, k):
result = ""
while num >= k:
num, mod = divmod(num, k)
result = str(mod) + result
return str(num) + result
def solution(n, k):
answer = 0
k_number = k_notation(n, k) # k진수로 만들기
maybeAnswer = k_number.split("0")
for num in maybeAnswer:
if num and is_prime(int(num)):
answer += 1
return answer3. 주차 요금 계산
이 문제는 입차, 출차기록으로 요금을 계산하는 것입니다. 완전한 구현문제입니다. 여기서 주목해야할 점은 잘못된 입력이 주어지지 않는다는 것입니다. 하지만 마지막 출차기록이 찍히지 않을 수는 있습니다. 따라서 기록을 차번호 별로 차곡차곡 모으면 <입차, 출차, 입차, 출차...> 이렇게 짝을 맞춰서 기록 됩니다. 따라서 모두 짝수여야하지만 홀수인 경우는 마지막 출차기록이 빠진 것으로 23:59으로 생각해주면 됩니다.
저는 차 번호별로 기록을 모으고 차별로 요금을 계산해주었습니다. 이때 기록이 홀수개라면 뒤에 23:59를 넣어 맞춰주고 요금을 계산했습니다. 정렬조건은 차량번호에 대한 오름차순이기때문에 차량번호와 요금을 묶어서 저장하고 정렬을 한번 돌리고 반환했습니다. 매번따져주는 것보다 이렇게 한번에 모아서 정렬을 마지막에 때리는게 머리도 안아프고 좋더라고요
import collections
import math
def time_to_min(time):
hour, minute = map(int, time.split(":"))
return hour * 60 + minute
def solution(fees, records):
answer = []
basic_time, basic_fee, unit_time, unit_fee = fees
logs = collections.defaultdict(list)
for record in records:
t, num, action = record.split()
logs[num].append(time_to_min(t))
last_time = time_to_min("23:59")
for car in logs.keys():
# 홀수기록일때 뒤에 넣어주기
if len(logs[car]) % 2:
logs[car].append(last_time)
total_fee = basic_fee
total_time = 0
# 입차 출차 짝지어서
for i in range(0,len(logs[car]),2):
total_time += logs[car][i+1] - logs[car][i]
# 추가요금계산
if total_time > basic_time:
total_fee += math.ceil((total_time - basic_time) / unit_time) * unit_fee
answer.append([car, total_fee])
return [c[1] for c in sorted(answer)]4. 양궁 대회
결국 4번까지 구현이네요. 문제 번호대로 4번 구현이 가장 까다롭습니다. 조건도 많아서 조심해줘야합니다ㅎㅎ
먼저 규칙을 잘 체크해보면 모든 규칙이 어피치가 유리하게 되어있습니다. 그리고 과녁을 여러번 맞춰도 과녁에 쓰여진 점수만 가져가는 것입니다. 이부분은 카카오가 굉장히 강조해서 써놨기 때문에 문제가 안되지만 중요한 것은 정렬조건, 점수차가 가장크게, 어피치의 결과가 주어진 순서입니다.
정렬조건
마지막에 같은 점수차라면 작은 과녁을 더 많이 맞춘 것을 선택하라고 합니다. 이런식의 처리는 매번 생각하기보다 정렬을 이용하는 것이 좋습니다. 왜냐면 머리가 아프거든요ㅎㅎ
지금같은 경우는 리스트끼리 정렬해주면 됩니다.
근데 문제가 이상하게 10점 - 0점순으로 input을 주고 output도 그렇게 달라고 하네요. 이부분이 굉장히 거슬리는데 이런요소는 편하게 바꿔버리고 마지막에 반대로만 출력해주는게 정신건강에 좋습니다.
따라서 저는 0점 - 10점으로 모든 것을 처리할 것이고 이렇게 되면 오름차순으로 처리해주면 낮은점수가 큰 것이 자동으로 앞에 오게 됩니다.
점수차
이부분은 착각하기 쉬운데 어피치와의 점수차가 크게 이겨야하는 것이지 높은 점수로 이기는 것이 문제가 아니라는 것입니다. 이거 놓치면 시간 뚝딱입니다.
어피치의 결과가 주어진 순서
이건 앞에서 언급했지만 10점 - 0점으로 준것을 말하는 것입니다. 이게 또 불편한게 직관적으로 0점은 인덱스 0을 참조할 수 있는데 그렇게 못합니다. 한번꼬았죠. 이걸 한번더 꽈서 탈출해봅시다.
중복조합
위에서 주의할 점을 봤는데 핵심인 문제풀이 방식은 전체탐색입니다. 사실 점수차가 가장크게 이기는 방법을 알아내는 것은 그냥 다 해봐야압니다. 좀 생각해보면 이걸 마치 그리디처럼 어떤 식으로 처리해야한다 이런게 없습니다. 숫자도 작습니다. 따라서 다 해보라는 것이고 코테에서 실제로 이런문제들이 많습니다.
따라서 완탐을 할 건데 여기서는 중복조합을 써야합니다.(확통을 공부한게 이런데에 쓰이네요) python은 순열, 조합, 중복순열, 중복조합 모두 내장함수가 있습니다. 따라서 중복조합인 combinations_with_replacement를 써서 모든 경우를 계산해주고 여기서 하나 더 중요한 것은 매번갱신을 하기가 애매하다는 것입니다. 뭐 못하는 건 아니지만 좀 복잡하고 구현이 더러워집니다.
이럴땐 그냥 정렬을 해야할 것들을 담아서 저장해두고 한번에 정렬로 정답을 뽑는게 N이 너무 큰게 아니라면 좋습니다. 저는 따라서 [점수차, [점수 구성]]을 넣고 마지막에 reverse로 돌려버리겠습니다. 그리고 마지막으로 반대로 출력해주는 거 잊지마세요!
import itertools
import collections
def solution(n, info):
answer = []
# 어피치 뒤집기 -> 0부터 10점까지
info.reverse()
# 중복조합으로 던질 수 있는 모든 경우를 계산
for combi in itertools.combinations_with_replacement(range(11),n):
info_R = [0] * 11
for c in combi:
info_R[c] += 1
# 점수계산시작
score_A = 0
score_R = 0
for score in range(1, 11):
if info[score] == info_R[score] == 0:
continue
if info[score] >= info_R[score]:
score_A += score
else:
score_R += score
# 라이언이 이겼다면
if score_R > score_A:
answer.append([score_R - score_A, info_R])
# 라이언이 이길 수 없다면
if not len(answer):
return [-1]
return sorted(answer, reverse = True)[0][1][::-1]5. 양과 늑대
이 문제는 꽤 어려웠습니다. 처음에는 문제풀이 방법이 잘 떠오르지 않아 건너뛴 문제입니다. 나중에는 그냥 어떻게든 답을 내자는 마음으로 풀었습니다.
BFS로 전체 탐색을 했는데 중간에 늑대수가 많아지면 더이상 가지 않도록 했습니다. 매번 갈 수 있는 곳들 기록해줘야하는데 node가 추가될 때 마다 그 자식들이 갈 수 있는 곳이 됩니다. 여기서는 양방향으로 하지 않아도 되는게 돌아가는 것이긴하지만 결국 방향은 항상 부모 -> 자식으로 확장되기 때문입니다.
따라서 현재노드, 늑대수, 양수, 갈 수 있는 노드들을 기록해주면서 진행해주면 됩니다. 그리고 지금처럼 최대갱신이 if문 안에서 이뤄지기 때문에 초기값은 1로 해주면 됩니다.
매번 새로 추가되는 노드의 자식을 추가하고 새로 추가되는 노드는 갈 수 있는 노드에서 제거해줍니다. 결국 이 문제의 초점은 다음에 갈 수 있는 노드들을 가지고 다녀야한다는 것입니다.
그리고 아래는 카카오 풀이에서 가져온 방법인데 이렇게 하면 양과 늑대의 분기처리없이 수를 갱신할 수 있습니다. 갈 수 있는 노드는 리스트로 넘겨줘야하기때문에 deep copy가 되어야합니다. 그렇지 않으면 같은 주소값을 참조해서 서로 독립적이게 될 수 없습니다!
nsheep = sheep + (info[nnode] ^ 1)
nwolf = wolf + info[nnode]import collections
def solution(info, edges):
answer = 1
paths = collections.defaultdict(list)
# 길 기록
for node1, node2 in edges:
paths[node1].append(node2)
# 길찾기
q = collections.deque()
q.append([0,1,0,paths[0]])
while q:
cur, sheep, wolf, can_visit = q.popleft()
for nnode in can_visit:
nsheep = sheep + (info[nnode] ^ 1)
nwolf = wolf + info[nnode]
# 방문가능
if nsheep > nwolf:
answer = max(nsheep, answer)
new_can_visit = can_visit[:]
new_can_visit.remove(nnode)
new_can_visit += paths[nnode]
q.append([nnode, nsheep, nwolf, new_can_visit])
return answer6. 파괴되지 않은 건물
이 문제는 누적합을 구하는 문제인데 효율성은 N의 수가 매우 크고 특히 공격과 회복의 수도 크기때문에 매번 값을 갱신해주면 타임아웃이 잃어날 수 밖에 없습니다.
여기서 얻을 수 있는 아이디어가 바로 누적합. 카카오 2021 공채에 나왔던 광고삽입에서 썼던 자료구조를 2차원으로 써주면 됩니다. 어떻게 2차원으로 확장할 지는 잘 고민해보면 알 수도 있지만 모를수도 있습니다..ㅎㅎ 그래서 나는 처음 이 문제를 풀 때 해설을 봤습니다.
좀 그림이 복잡하지만 만약 3 x 3 짜리에서 2 x 2만큼 누적합을 1씩 올려주고싶다면 (0,0) (2,2)에는 +1 (2,0) (0,2)에는 -1로 해주고 행부터 자신에 자신의 전을 합쳐주는 행위를 해주고 열도 그렇게 해주면 2 x 2영역만 1로 찹니다.
이게 누적합을 2차원으로 확장한 것이다.
따라서 이 문제에 이 원리를 적용해서 board보다 1씩 행열이 큰 board를 새로 만들어서 누적합을 기록해줍니다. 그리고 board랑 하나씩 비교하면서 파괴되지 않은 건물의 수를 마지막에 카운트하면 됩니다. 이렇게 하면 매번 board에 4씩 표시하고 한번에 계산해주고 비교하기때문에 적은 시간 복잡도가 나옵니다.
이 원리를 사용할때는 지금처럼 하나 크게 리스트를 만들어주는 것이 좋습니다. 왜냐면 원하는 구간보다 하나 크게 기록을 해줘야하기 때문입니다. 대신 계산은 크기에 맞게만 해주고 사용도 크기에 맞게만 하면 됩니다!
def solution(board, skill):
answer = 0
N = len(board)
M = len(board[0])
total_board = [[0] * (M+1) for _ in range(N+1)]
# 누적합 기록
for ty, r1, c1, r2, c2, degree in skill:
if ty == 1:
total_board[r1][c1] -= degree
total_board[r1][c2+1] += degree
total_board[r2+1][c1] += degree
total_board[r2+1][c2+1] -= degree
else:
total_board[r1][c1] += degree
total_board[r1][c2+1] -= degree
total_board[r2+1][c1] -= degree
total_board[r2+1][c2+1] += degree
# 누적합 계산
for i in range(N):
for j in range(1,M):
total_board[i][j] += total_board[i][j-1]
for j in range(M):
for i in range(1,N):
total_board[i][j] += total_board[i-1][j]
# 비교
for i in range(N):
for j in range(M):
if board[i][j] + total_board[i][j] > 0:
answer += 1
return answer후기
이번에는 구현문제가 많았고 그만큼 정답률도 4번까지 굉장히 높았습니다. 그럼에도 그 뒤문제들이 쉽지 않았기 때문에 컷은 4.5정도로 형성된 것 같네요. 카카오 채용설명회를 들어보면 코테가 어렵다는 말이 많아서 계속 코테 난이도를 낮추기위해 신경을 쓰고있었는데 2022년도에 역대급으로 낮춘게 아닌가 싶습니다.
아마 2023 올해는 난이도를 높일 것으로 예상되고 모든 기업이 신입개발자 TO를 줄이고 있기 때문에 조금은 어려워지지 않을까 예상해봅니다..ㅠㅠ
