2019 카카오 코딩 테스트 오픈채팅, 실패율, 후보키
2019 카카오 코딩 테스트 1번 오픈채팅, 2번 실패율, 3번 후보키 문제 풀이를 회고하는 포스팅입니다.
1. 오픈채팅
문제 설명
자세한 문제 설명은 아래 페이지에서 참고해주세요
문제를 요약하면 채팅방에 일어나는 입장, 퇴장, 닉네임을 변경을 할 수 있는 명령과 유저아이디, 닉네임이 기록이 된 입력값들이 주어지고 이 기록에 맞춰서 결과에 적절히 닉네임을 넣어 제출하는 문제라고 할 수 있다.
문제 풀이
보자마자 깨달은 것은 유저 아이디에 따른 닉네임을 변경사항에 맞춰서 갱신한 다음 마지막에 한번에 닉네임을 넣는 방식으로 해야겠다는 생각이 들었다.
- 딕셔너리를 이용해서 유저 아이디에 해당하는 닉네임 값을 업데이트 해준다.
- 업데이트하면서 유저가 들어온 경우와 나가는 경우에 유저 아이디 + 입장 메시지 또는 유저 아이디 + 퇴장 메시지를 결과 리스트에 저장해준다.
- 결과 리스트에 유저 아이디의 내용을 딕셔너리에 저장되어 있는 유저 닉네임으로 변경하여 제출한다.
첫 번째 제출했을 때는 결과 리스트를 만들지 않고 문자열과 replace, split을 이용해서 유저 아이디를 유저 닉네임으로 변경해주고 리스트로 나누어서 제출하려고 했더니 몇 개의 테스트 케이스에서 시간초과의 문제가 생겨 실패를 했다.
이를 해결하고자 문자열을 결과 리스트로 유저 아이디를 넣어 저장을 해두었고 유저아이디가 들어간 index 저장하는 딕셔너리를 사용하여 마지막에 한번에 바꾸었다.
코드 구현
첫 번째 시도 (실패)
def solution(record) :
users = {}
result = ""
for str in record :
if str[0] == 'E' or str[0] == 'C' :
command, uid, nick = str.split(" ")
users[uid] = nick
if command == "Enter" :
result += uid + "님이 들어왔습니다.#"
else :
command, uid = str.split(" ")
result += uid + "님이 나갔습니다.#"
for uid in users.keys() :
#print(uid, users[uid])
result = result.replace(uid, users[uid])
if result[-1] == '#' :
result = result[:-1]
#print(result.split("#"))
answer = result.split("#")
return answer
두 번째 시도 (정답)
def solution(record) :
users = {}
users_index = {}
result = []
count = 0
for str in record :
if str[0] == 'E' or str[0] == 'C' :
command, uid, nick = str.split(" ")
if uid not in users.keys() :
users_index[uid] = []
users[uid] = nick
if command == "Enter" :
users_index[uid].append(count)
count += 1
result.append(uid + "님이 들어왔습니다.")
else :
command, uid = str.split(" ")
users_index[uid].append(count)
result.append(uid + "님이 나갔습니다.")
count += 1
for uid in users.keys() :
for index in users_index[uid] :
result[index] = result[index].replace(uid, users[uid])
answer = result
return answer
2. 실패율
문제 설명
자세한 문제 설명은 아래 페이지에서 참고해주세요
사용자가 stage 단위로 클리어하는 게임에서 stage의 실패율을 조사하여 정렬하는 문제였다.
스테이지의 수와 각 플레이어의 위치에 해당하는 리스트가 주어지고 결과로 실패율을 내림차 순으로 하는 스테이지 번호 리스트 제출하면 된다.
실패율은 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의수 / 스테이지에 도달한 플레이어 수로 직관적으로는 아직 남아있는 플레이어 수 / 스테이지에 방문한 플레이어 수 을 말한다.
추가 조건으로 스테이지에 도달한 유저가 없으면 실패율은 0이며 실패율이 같을 때에는 스테이지 번호가 작은 것이 먼저 오도록 하면 된다.
문제 풀이
문제는 정말 간단했다. 각 스테이지에 몇명이 방문했는지 알아야하고 남아있는 사람이 몇명인지 파악하면 되는 문제였다.
각 스테이지에 몇명이 방문했는지 파악하기 위하여 1차 적으로 각 스테이지에 플레이어가 현재 위치해 있는 수를 세어준다. 그리고 한 플레이어가 현재 스테이지에 있기 위해서는 이전 스테이지들을 한 번씩 방문하고 온 것이므로 모든 플레이어가 현재 자신의 스테이지까지 올라오는 시뮬레이션을 해주면서 이전 스테이지에 값들을 카운팅해준다.
남아 있는 사람이 몇명인지는 현재 스테이지를 방문한 사람 수에서 다음 스테이지를 방문한 사람 수를 뺄 수도 있고 입력으로 받은 스테이지 리스트에서 스테이지에 있는 사람 수를 세어주어도 가능하다.
코드 구현
testcases = []
testcases.append((5, [2, 1, 2, 6, 2, 4, 3, 3]))
testcases.append((4, [4,4,4,4,4]))
# "현재 스테이지 방문자 수 - 다음 스테이지 방문자 수 = 남아 있는 사람" 을 이용하는 방법
def solution(N, stages) :
failure_rate = []
in_stage = [0 for _ in range(N + 2)]
for stage in stages :
in_stage[stage] += 1
for stage in stages :
for pre_stage in range(1, stage) :
in_stage[pre_stage] += 1
#print(in_stage)
for i in range(1, N + 1) :
if in_stage[i] == 0 :
failure_rate.append((0, i))
else :
failure_rate.append((float((in_stage[i] - in_stage[i + 1]) / in_stage[i]), i))
failure_rate.sort(key=lambda x:(-x[0], x[1]))
answer = []
for a, b in failure_rate :
answer.append(b)
#print(b)
return answer
for testcase in testcases :
print(solution(testcase[0], testcase[1]))
'''
# 방문과 현재 스테이지 따로 저장 해두는 방법
def solution(N, stages) :
failure_rate = []
in_stage = [0 for _ in range(N + 2)]
visit = [0 for _ in range(N + 2)]
for stage in stages :
in_stage[stage] += 1
visit[stage] += 1
for stage in stages :
for pre_stage in range(1, stage) :
visit[pre_stage] += 1
#print(in_stage)
for i in range(1, N + 1) :
if in_stage[i] == 0 :
failure_rate.append((0, i))
else :
failure_rate.append((float((in_stage[i]) / visit[i]), i))
failure_rate.sort(key=lambda x:(-x[0], x[1]))
answer = []
for a, b in failure_rate :
answer.append(b)
#print(b)
return answer
'''
3. 후보키
문제 설명
자세한 문제 설명은 아래 페이지에서 참고해주세요
문제 이름 그대로 후보키가 될 수 있는 키의 수를 구하는 문제이다.
relation이 리스트 형태로 주어지고 결과로 후보키의 수를 제출하면 된다. 후보키는 당연히 유일성과 최소성을 만족해야한다.
문제 풀이
문제를 보자마자 조합 라이브러리를 연습해볼 수 있는 문제라는 것을 알았다.
조합을 사용한 적이 없어서 구글링하여 참고하여 문제를 풀어봤다.
핵심은 모든 경우의 수를 하여 중복여부로 유일성을 판단하고 속성의 개수가 더 적은 유일성을 만족하는 키를 포함하고 있지 않는 것으로 최소성을 판단하여 후보키를 찾을 수 있다.
키가 가능한 경우를 조합하는 것은 컬럼을 한 개부터 최대 개수까지 조합하는 것을 말하므로 컬럼의 인덱스만을 이용해서 조합할 수 있다.
컬럼의 인덱스 조합을 이용하여 릴레이션에서 해당 컬럼 인덱스의 값을 뽑아 새로운 릴레이션을 만들고 집합을 이용하여 중복을 제거한 릴레이션의 행의 개수가 원래 릴레이션의 개수와 같은지 비교하여 유일성을 판단한다. 만약 유일하다면 이 인덱스 조합을 리스트에 저장한다.
위의 작업이 다 끝난 후에는 최소성을 판단을 시작한다. 하나의 키가 최소성을 만족하기 위해서는 다른 후보키를 포함하고 있지 않아야 하므로 두 인덱스 조합을 비교하여 한 쪽이 다른 한쪽의 포함 관계에 해당하는 값들을 제거해주어 유일성, 최소성 모두 만족하는 인덱스 조합들의 리스트를 완성한다.
이 리스트의 길이를 답을 제출하여 완료한다.
코드 구현
testcases = []
testcases.append([["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]])
from itertools import combinations
def solution(relation) :
row_len = len(relation)
col_len = len(relation[0])
col_list = range(col_len)
unique = []
for i in range(1, col_len + 1) :
# combinations을 이용하여 col 인덱스를 이용한 모든 조합을 시도해본다.
comb = combinations(col_list, i)
for comb_col_list in list(comb) :
# tmp에 튜플 형태로 row에 해당하는 값을 넣고
# 집합 형태로 만들어서 중복을 제거한다
# 이 집합의 길이가 릴레이션의 행의 수와 다르다면 유일성을 만족하지 못한다.
tmp = [tuple([row[idx] for idx in comb_col_list]) for row in relation]
if len(set(tmp)) == row_len :
unique.append(set(comb_col_list))
# slice를 이용하여 remove가 for loop에 영향을 미치지 않도록 한다.
for l1 in unique[:] :
for l2 in unique[:] :
# 두 개의 집합을 비트 & 연산하여
# l2가 l1을 포함하고 있는지 확인
if l1 == l1 & l2 :
# l2가 l1을 포함하고 있고 l1과 다르다면 l2는 최소성을 만족하지 못한다.
if l1 != l2 :
unique.remove(l2)
answer = len(unique)
return answer
print(solution(testcases.pop()))
—
개인적 회고
문제 1번과 2번은 정말 간단했다. 하지만 이번에 문제 1번을 풀 때 처럼 시간복잡도를 고려하지않고 바로 문제를 풀지 않도록 하는 연습이 필요한것을 느꼈다. 문제 조건을 꼼꼼히 보고 시간복잡도를 고려하여 빨리 푸는 연습을 해야할 것 같다.
문제 3번의 조합 유형을 처음 풀어봤는데 많이 도움이 되었다. kakao 2020년도 6번 외벽 점검때에는 순열을 이용한 풀이가 필요했는데 2019년도에는 조합이 나온 것을 보면 kakao 블라인드 채용 코딩테스트에서는 조합과 순열은 기본적으로 알아두어야 할 것 같다.