23.07.21 (금) 10:40am ~ 15:40am 모의 테스트 진행
| 문제 | 난이도 | 풀이여부 |
|---|---|---|
| 실패율 | Lv. 1 | ⭕️ |
| 오픈채팅방 | Lv. 2 | ⭕️ |
| 후보키 | Lv. 2 | ⭕️ |
| 길 찾기 게임 | Lv. 3 | ⭕️ |
| 무지의 먹방 라이브 | Lv. 4 | ❌ |
| 매칭 점수 | Lv. 3 | ❌ |
| 블록 게임 | Lv. 4 | ❌ |
2023 KAKAO BLIND RECRUITMENT보다는 상대적으로 쉬웠다.
이번이 정기 기출문제를 푼지 4회차쯤 되는 것 같은데, 처음에는 시간이 정말 안가고 문제를 거의 풀지 못했는데 이제는 좀 익숙해진 것인지 푼 문제 수도 꽤 된다.
실력이 늘었다기 보다는 상대적으로 이전 문제들보다 쉬워서 그럴지도..?실력이 늘은거였으면 좋겠다!
문제 풀이
실패율
코드
# 실패율 : 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
# 실패율이 높은 스테이지부터 내림차순 정렬
from collections import defaultdict
def solution(N, stages):
fail = defaultdict(int) # 각 스테이지 별 실패율
total = len(stages) # 스테이지에 도달한 플레이어 수
# 스테이지는 1부터 N + 1까지
for stage in range(1, N + 1):
not_clear = stages.count(stage) # 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수
if not_clear == 0: # 스테이지에 도달한 유저가 없는 경우
fail[stage] = 0 # 실패율은 0으로 정의
else:
fail[stage] = not_clear / total # 실패율 계산
total -= not_clear # 스테이지에 도달한 플레이어 수 갱신
answer = list(zip(*sorted(fail.items(), key=lambda x: -x[1])))[0]
return answer아이디어 및 풀이
문제의 목표
- 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호 배열을 return 하기
실패율은 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수로 정의 된다.
처음에 스테이지에 도달한 플레이어 수를 어떻게 초기화하고 갱신해야 하는지 고민을 좀 했다.
제한사항과 예시를 보면, stages에는 1 이상의 자연수가 담긴다. 즉, 처음에는 스테이지에 도달한 플레이어 수가 stages의 길이가 된다.
그러면 다음 스테이지로 갈 때 마다 갱신은 어떻게 할까?
현재 값에서 이전 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수를 빼면 된다.
예시로, N=5, stages=[2, 1, 2, 6, 2, 4, 3, 3]라고 하자.
- 1번 스테이지 실패율은
1/8- 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수: 1명(스테이지 번호와 같은 숫자의 개수를 의미)
- 스테이지에 도달한 플레이어 수: 8명(초기 stages의 길이는 8이기 때문)
- 2번 스테이지 실패율은
3/7- 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수: 3명
- 스테이지에 도달한 플레이어 수: 8 - 1(1번 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수) = 7
- 나머지 스테이지의 실패율도 동일하게 계산...
위 코드에서 실패율은 딕셔너리로 저장했으므로, items()를 기준으로 정렬한 뒤 Key만 배열로 만들어서 return하면 된다.
아니면, 스테이지 번호가 정수이므로 딕셔너리가 아닌 배열로 접근해도 될 것 같음.
오픈채팅방
코드
from collections import defaultdict
# 채팅방에 입장할 때 이전에 입장한 기록이 있는 id인데 닉네임이 다른 경우 -> Change로 간주
# 닉네임 변경을 모두 처리한 후, (입장,퇴장) 메시지를 생성하면 된다.
# 입장, 퇴장 시 일일히 닉네임을 처리하면 복잡해진다.
def solution(record):
answer = []
user_info = defaultdict(str) # id : name
# 닉네임 변경 확인
for r in record:
if "Enter" in r or "Change" in r:
_type, _id, name = r.split()
user_info[_id] = name
# 입장, 퇴장 메시지 생성
for r in record:
_type, _id = r.split()[0], r.split()[1] # (입장, 퇴장), 아이디
name = user_info[_id]
if _type == "Enter": # 입장
answer.append(name + "님이 들어왔습니다.")
elif _type == "Leave": # 퇴장
answer.append(name + "님이 나갔습니다.")
return answer아이디어 및 풀이
문제의 목표
- 닉네임 변경 기록을 모두 처리한 후 최종적으로 방을 개설한 사람이 보게 되는 메시지를 문자열 배열 형태로 return 하기.
record의 첫 단어는 Enter, Leave, Change 중 하나로 시작한다.
여기서 주의해야 하는 것은 Enter이다. 문제의 예시를 보면, 이전에 입장한 사람도 다른 닉네임으로 다시 Enter가 가능하다.
즉, 닉네임 변경이 Change만이 아니라 Enter도 가능하다는 것이다.
문제를 보고, 로직을 2가지로 나눠보면 되겠다고 생각했다.
- 먼저 record를 탐색하면서 닉네임 변경 여부부터 살펴보고, 변경됐다면 id에 맞게 닉네임을 재설정한다.
- 다시 record를 탐색하면서, 입장과 퇴장 메시지를 생성한다.
이때, id에 name을 매칭시켜야하고 id는 str타입이므로 딕셔너리를 사용하여 id를 Key, name을 Value로 설정했다.
후보키
코드
# 후보 키의 최대 개수를 구해야 한다. → 후보 키가 될 수 있는 모든 조합을 구하면 된다.
# 유일성을 만족해야 한다. → 중복되는 값이 있다면 해당 키는 유일성 만족하지 못함.
# 최소성을 만족해야 한다. → 유일성의 조합에서 하나를 제외했을 때 유일성이 깨지면 만족 못한다. → 유일성의 조합으로만 이루어져야 한다?
# 최소성이란? 예시에서 학번으로 모든 학생을 구별할 수 있다. 그렇다면 [학번, 이름]으로 구별할 필요가 있을까? → 굳이 이름을 끼지 않아도 된다. 학번 자체만으로도 구별이 가능하기 때문이다.
# 즉, 최소성은 굳이 넣지 않아도 될 속성을 넣지 않은 것을 말한다.
from itertools import combinations
def solution(relation):
row_len = len(relation) # 행 길이
col_len = len(relation[0]) # 열 길이
# 유일성 판단
def get_unique():
unique_keys = []
for candidate_key in candidate_keys:
key_set = set([tuple(r[key] for key in candidate_key) for r in relation])
if len(key_set) == row_len: # 중복이 없을 경우
unique_keys.append(candidate_key)
return unique_keys
# 최소성 판단
def get_minimal():
minimal_keys = set(unique_keys)
for i in range(len(unique_keys) - 1):
for j in range(i + 1, len(unique_keys)):
if len(unique_keys[i]) == len(set(unique_keys[i]) & set(unique_keys[j])):
# minimal_keys를 list로 선언하면 list index out of range 오류 발생..
# 근데 set은 왜 되지?
if unique_keys[j] in minimal_keys:
minimal_keys.remove(unique_keys[j])
return minimal_keys
# 키의 조합 찾기
candidate_keys = []
for pick_size in range(1, col_len + 1):
candidate_keys.extend(combinations(range(col_len), pick_size))
unique_keys = get_unique() # 유일성
minimal_keys = get_minimal() # 최소성
return len(minimal_keys)아이디어 및 풀이
문제의 목표
- 후보 키의 최대 개수를 구하기
문제를 보고, 로직을 3가지로 나눠보면 되겠다고 생각했다.
- 먼저, 각 컬럼으로 가능한 조합을 구한다.(키의 조합 구하기)
- 위에서 구한 조합으로 유일성을 판단하고, 유일성을 만족하는 키들을 다시 구성한다.
- 유일성을 만족하는 키들의 최소성을 판단한다.
각 컬럼으로 가능한 조합은, itertools 모듈의 combinations를 사용했다.
어떤 기준으로 조합을 구할까?
문제의 예시에서 [학번, 이름, 전공, 학년]에 다음과 같이 인덱스를 부여해서 조합을 구했다.(인덱스가 있다고 생각했다.)
- 학번의 인덱스는 0
- 이름의 인덱스는 1
- 전공의 인덱스는 2
- 학년의 인덱스는 3
유일성은 어떻게 판단할까?
위에서 구한 조합(인덱스 조합)을 가지고 실제 relation의 각 행에서 인덱스에 맞는 값들로 튜플을 만든다.
각 행에 대한 튜플을 모두 구성했다면, 이를 모두 모아 배열로 만들어 다시 집합으로 만든다. (set([tuple()])같은 형태)
왜 집합으로 다시 만들까?
✅ 중복되는 값들을 확인하기 위해서이다.
문제의 예시에서 이름만으로 조합을 구성했다고 해보자.
key_set = [(ryan), (apeach), (tube), (con), (muzi), (apeach)] 에서 보면, apeach가 중복이 발생한다. 중복이 발생한다는 의미는, 유일성을 만족하지 못한다는 의미이다.
그럼 중복은 어떻게 판별하는게 좋을까?
유일성을 만족한다면, key_set의 길이가 row의 길이와 같을 것이다.
즉, key_set을 집합으로 변환하고 이때의 길이를 row의 길이와 비교하면 되는 것이다.
유일성을 만족한다면, 해당 키의 조합을 따로 배열에 저장한다.
unique_keys = []
if len(set(key_set)) == row_len: # 중복이 없을 경우
unique_keys.append(candidate_key)마지막으로 최소성을 판단한다.
문제에서 설명하는 최소성의 개념이 와닿지 않아서 찾아보니,
최소성이란, 최소한의 컬럼으로 모든 튜플을 식별할 수 있는 속성이다.
만약, [이름, 전공]으로 모든 튜플을 식별할 수 있다고 가정해보자.
그럼 여기에 학년을 껴보면 어떨까?
[이름, 전공, 학년]으로도 모든 튜플을 식별할 수 있다. 근데, 굳이 학년을 껴야하는가를 고민해보자. 위에서 이미 [이름, 전공]으로 모든 튜플을 식별할 수 있는데 굳이 학년을 낄 필요는 없다. 끼지 않아도 이미 식별이 가능하기 때문이다.
즉, 내가 생각하기에 최소성이란 굳이 넣지 않아도 될 속성을 넣지 않은 것이라고 생각했다.
또한, [이름, 전공]과 [이름, 전공, 학년]을 보면 교집합으로 [이름, 전공]을 가진다. 이 말은, 교집합이 있다면 [이름, 전공, 학년]은 최소성을 만족하지 못한다는 것으로 볼 수 있다.
최소성은 다음과 같이 판별했다.
def get_minimal():
minimal_keys = set(unique_keys)
for i in range(len(unique_keys) - 1):
for j in range(i + 1, len(unique_keys)):
if len(unique_keys[i]) == len(set(unique_keys[i]) & set(unique_keys[j])):
# minimal_keys를 list로 선언하면 list index out of range 오류 발생..
# 근데 set은 왜 되지?
if unique_keys[j] in minimal_keys:
minimal_keys.remove(unique_keys[j])
return minimal_keys길 찾기 게임
코드
import sys
sys.setrecursionlimit(10**6)
# y를 내림차순, x를 오름차순으로 정렬하면 Level 순서 순회 결과를 얻을 수 있음.
# Level order로 별다른 로직 추가 없이 전위, 후위 순회를 구할 수 있을까?
# 안된다면, Level order로 어떠한 로직을 추가해야 할까?
# 다른 방법도 존재.
# → 트리를 만들지 않고, x좌표를 기준으로 정렬한 뒤 순회 시작
def solution(nodeinfo):
class Node(object):
def __init__(self, info):
self.idx = info[2]
self.coord = info[:2]
self.left = None
self.right = None
# 전위 순회
def preorder(v):
order = [v.idx]
if v.left:
order += preorder(v.left)
if v.right:
order += preorder(v.right)
return order
# 후위 순회
def postorder(v):
order = []
if v.left:
order += postorder(v.left)
if v.right:
order += postorder(v.right)
order.append(v.idx)
return order
# 레벨 순서 순회(Level order traversal)로 트리 만들기
def build(parent, cur):
if parent.coord[0] > cur[0]:
if parent.left:
build(parent.left, cur)
else:
parent.left = Node(cur)
else:
if parent.right:
build(parent.right, cur)
else:
parent.right = Node(cur)
for i in range(len(nodeinfo)):
nodeinfo[i].append(i + 1)
nodeinfo.sort(key=lambda x: (-x[1], x[0])) # y좌표 내림차순
tree = Node(nodeinfo[0])
for i in range(1, len(nodeinfo)):
build(tree, nodeinfo[i])
pre, post = preorder(tree), postorder(tree)
return [pre, post]아이디어 및 풀이
처음에는 예전에 전위 순회, 후위 순회 결과로만 중위 순회 결과를 만들어 낼 수 있다(?)는게 생각이 나서, 레벨 순서 순회로도 전위, 후위 순회 결과를 만들어 낼 수 있지 않을까 생각해서 열심히 삽질을 했다.
그러다 다른 방식을 생각해봤는데, 주어진 nodeinfo를 y좌표 기준 내림차순, x좌표 기준 오름차순으로 정렬을 하면 nodeinfo가 Level order로 변한다.
이를 가지고, 문제의 제한사항을 토대로 트리를 구성해서 중위 순회, 후위 순회를 수행한 결과를 만들었다.
트리 만드는 함수가 재귀로 동작하는데, 재귀가 많이 약해 어려웠다.
전위 순회: 루트 → 왼쪽 자식 → 오른쪽 자식
중위 순회: 왼쪽 자식 → 루트 → 오른쪽 자식
후위 순회: 왼쪽 자식 → 오른쪽 자식 → 루트
무지의 먹방 라이브
코드
import heapq
# 어렵당
def solution(food_times, k):
if sum(food_times) <= k:
return -1
q = []
turnTable_size = len(food_times) # 회전판의 크기
total_spent_time, prev_spent_time = 0, 0 # 이제까지 음식을 먹는데 소요된 총 시간, 이전에 음식을 먹는데 소요된 시간
for i, food_time in enumerate(food_times):
heapq.heappush(q, (food_time, i + 1))
# 이제까지 소요된 시간과 현재 음식의 남은 양을 모두 먹는데 걸리는 시간의 합이 k보다 작거나 같을 때
# 즉, 회전판 한 바퀴를 돌았을 때 음식을 먹을 수 있는 시간이 남아있을 때
while total_spent_time + (q[0][0] - prev_spent_time) * turnTable_size <= k:
cur_spent_time = heapq.heappop(q)[0] # 현재 음식을 모두 먹는데 소요되는 시간
total_spent_time += (cur_spent_time - prev_spent_time) * turnTable_size # 실질적으로는 회전판의 형태이므로, 회전판에 있는 음식의 개수만큼 곱해준다.
turnTable_size -= 1 # 현재 음식은 다 먹었다고 가정한다.
prev_spent_time = cur_spent_time # 다음 음식을 비교하게 되므로, 현재 음식에 소요된 시간이 이전 음식에 소요된 시간이 된다.
# 기존 food_times는 음식 번호 순이었으므로,
# 음식 번호를 기준으로 정렬한다.(원위치 시켜준다.)
answer = sorted(q, key=lambda x:x[1])
return answer[(k - total_spent_time) % turnTable_size][1]아이디어 및 풀이
이 문제 또한, 여러번 풀어봤지만서도 이번에도 풀지 못했다. 다른 사람의 코드를 참고했다.
설명 또한 다른 사람의 설명을 참고해보자.
내가 푼 코드가 아니기도 하고, 위 코드는 나 또한 아직 이해 중이기 때문에, 완전히 이해가 되면 풀이를 작성하겠다.
매칭 점수
코드
# 1. 각 페이지의 <meta> 안에서 url을 찾는다.
# 2. <body> 안에서 검색어를 찾는다. = 기본점수를 찾는다.
# 3. 외부 링크 수를 찾는다.
# 4. 링크 점수를 찾는다(이 단계를 위해 url을 찾아야 한다.(과정#1))
# 5. 모든 페이지에 대해서 1~3을 수행한다.
# 6. 다 찾았다면, 각 페이지의 링크 점수를 찾는다.
# 정규표현식 활용법을 묻는 문제이다.
from collections import defaultdict
import re
def solution(word, pages):
total_score = []
basic_score = {}
exlink_cnt = {}
to_me_link = {}
for page in pages:
title = re.search('<meta property="og:url" content="(https://\S+)"', page).group(1)
basic_score[title] = 0
exlink_cnt[title] = 0
for find in re.findall('[a-zA-Z]+', page):
if find.upper() == word.upper():
basic_score[title] += 1
for link in re.findall('<a href="(https://\S+)"', page):
exlink_cnt[title] += 1
if link in to_me_link:
to_me_link[link].append(title)
else:
to_me_link[link] = [title]
for curr in basic_score:
link_score = 0
if curr in to_me_link:
for ex in to_me_link[curr]:
link_score += basic_score[ex] / exlink_cnt[ex]
total_score.append(basic_score[curr] + link_score)
return total_score.index(max(total_score))아이디어 및 풀이
처음에 보고 단순히 문자열 함수를 사용해서 풀 수 있지 않을까 고민했는데, 생각대로 풀리지 않았다. 자세히보니 정규식을 사용할 수 있는가를 묻는 문제였다.
정규식은 사용할 줄 전혀 모른다고 할 수 있어서, 다른 사람의 코드를 참고했다.
블록 게임
코드
문제를 보지 못했다.아이디어 및 풀이
항상 카카오 문제를 풀 때, 다 풀지 말고 풀 수 있는 것부터 확실하게 풀자는 마인드로 임하기 때문에, Lv. 4는 버린다.
나중에 다시 풀어보자.
