이게 왜 새 문제겠어요.....
동기
카카오 윈터 당일에 풀었지만 1.5솔로 문제를 다시 한번 보고싶었다.
Programmers 에 풀렸다는 소식을 듣고 빠르게 가서 시간을 넉넉히 주고 풀어보았다
난이도 측정은 L1~L3 이였고 막상 L4는 없었다.
코테볼때 번호가 뒤에 나온다고 쫄지말자 인간이 측정한 레벨일뿐....
산모양 타일링은 해설을 참고했다.
https://tech.kakao.com/2023/12/27/2024-coding-test-winter-internship/
1번 가장 많이 받은 선물
from collections import defaultdict
def solution(friends, gifts):
k = len(friends)
answer_list = [0 for _ in range(k)]
# 선물 지수만 계산
rate = defaultdict(int)
# 인덱스랑 벨류값
idx_record = dict()
value_record = dict()
# 표를 만들자
chart = [[0] *k for _ in range(k)]
for i in range(k):
for j in range(k):
if i == j:
chart[i][j] = -1
# 순서를 정해주자
for idx, value in enumerate(friends):
idx_record[value] = idx
value_record[idx] = value
for gift in gifts:
giver, receiver = gift.split()
# 선물 지수 계산
rate[giver] += 1
rate[receiver] -= 1
# 표 제작
idx_giver = idx_record[giver]
idx_receiver = idx_record[receiver]
chart[idx_giver][idx_receiver] +=1
chart[idx_receiver][idx_giver] -=1
for c in range(k):
for i in range(k):
if chart[c][i] >0 :
answer_list[c] += 1
if chart[c][i] == 0:
a = value_record[c]
b = value_record[i]
if rate[a] > rate[b]:
answer_list[c] += 1
return max(answer_list)선물지수를 사람들 별로 계산을 해주고 표를 만들어주었다.
표를 만들때는 양쪽에 +-를 동시해주어서 만약 받은게 많다면 음수이고 준게 많다면 양수가 나와서 해당 사람과 비교를 할 수 있게 하였다.
총 이차원 표를 완성한 뒤에는 완전탐색을 돌며 많이 준사람을 찾고 선물지수와 비교를 해주었다.
- 코테 당시에도 같은 방법으로 풀었다.
1번 본받을 만한 코드
def solution(friends, gifts):
g_record = {}
for f1 in friends:
g_record[f1] = [0,{}]
for f2 in friends:
if f1 != f2:
g_record[f1][1][f2] = 0
for gift in gifts:
a,b = gift.split()
g_record[a][0] += 1
g_record[a][1][b] += 1
g_record[b][0] -= 1
g_record[b][1][a] -= 1
answer = [0] * len(friends)
for a, values in g_record.items():
idx1 = friends.index(a)
exponent_a = values[0]
for b, cnt in values[1].items():
if cnt > 0:
answer[idx1] += 1
elif cnt == 0:
if exponent_a > g_record[b][0]:
answer[idx1] += 1
return max(answer)3차원 배열을 쓸까했지만 안쓰고 배열을 하나 더 만들었는데
해당 풀이처럼 배열을 [선물지수]{선물 주고받은 딕셔너리}로해서 초기화를 진행해주었다.
선물지수를 업데이트와 동시에 딕셔너리에서 찾아서 값을 조정해주었다.
깔끔한것 같아서 올려본다.
2번 도넛과 막대 그래프
def solution(edges):
answer = [0,0,0,0]
# 진출차수와 진입 차수 초기화 및 카운팅
indegree = {}
for a,b in edges:
if not indegree.get(a):
indegree[a] = [0,0]
if not indegree.get(b):
indegree[b] = [0,0]
indegree[a][0] += 1
indegree[b][1] += 1
# 최초 점: 진입차수가 없고 진출 차수가 2이상
# 막대 : 진입차수 있고 진출 차수 없음
# 8자 그래프 : 진입차수 진출차수 각각 2개이상
# 도넛: 나머지 그래프
for key, i in indegree.items():
# 최초점
if i[0] >= 2 and i[1] == 0:
answer[0] = key
# 막대
elif i[0] == 0 and i[1] > 0:
answer[2] +=1
# 8자
elif i[0] >= 2 and i[1] >=2:
answer[3] += 1
answer[1] = (indegree[answer[0]][0] - answer[2] - answer[3])
return answer진입차수와 진출차수를 비교해서 푸는 문제였다.
마지막에 전체에서 8과 막대를 빼주면 순환이 나온다는 것을 직접 구하려고해서 코테를 풀 때 1.5솔이 나왔다.
여집합을 잊지말자....
전체에서 되는걸 빼면 마지막 남은것이다.. 기본이다....
최초점은 진입차수가 없고 진출 차수가 2이상이다.(그래프가 2개)
막대는 진입차수가 있고 진출 차수가 없다.
8자는 진입차수 진출차수가 각각 2개이상이다.
도넛은 남은것
3번 주사위 고르기
from collections import defaultdict
from itertools import combinations
def solution(dice):
answer = []
k = len(dice) //2
idice = []
for d in range(len(dice)):
dic = defaultdict(int)
for value in dice[d]:
dic[value] += 1
idice.append([d,dic])
ranking = {}
for com in combinations(idice,k):
rank = [[],{}]
# 주사위 뭘 뽑았는지 넣어주기
for i in range(k):
rank[0].append(com[i][0])
# 뽑은 주사위로의 조합
temp = defaultdict(int)
for c,v1 in com[i][1].items():
if i == 0:
temp[c] = v1
else:
for r,v2 in rank[1].items():
temp[c+r] += v1*v2
rank[1] = temp
# 키값 만들어주기
key = ''.join(map(str,rank[0]))
ranking[key] = rank[1]
max_win = 0
# 랭킹끼리 싸움
dice_list = set([i for i in range(len(dice))])
for i in combinations(dice_list,k):
# 뽑히지 않은 배열 만들기
non_dice = [j for j in range(len(dice)) if j not in i]
# 키를 통해서 조회하기 위해 키설정
pick_key = ''.join(map(str,i))
non_key = ''.join(map(str,non_dice))
pick = ranking[pick_key]
non = ranking[non_key]
temp = 0
for r,v1 in pick.items():
for n,v2 in non.items():
if r > n:
temp += v1*v2
if temp > max_win:
max_win = temp
answer = i
# 주사위는 1부터 시작
return [x + 1 for x in answer]시간복잡도를 생각해서 딕셔너리를 무척이나 많이 활용한 나의 풀이다.
1. 주사위 별로 나올 수 있는 수-갯수 를 표현했다.
2. 뽑아야하는 주사위를 조합을 모두 만들어 해당 주사위 들로 나올 수 있는 경우의 수를 구했다.
3. 해당 만든 경우의 수를 기반으로 1번 2번 3번 주사위를 만들었다면 key=123을 만들었다.
10도 상관이 없는이유는 1,10하면 110가 만들어지는데 우리는 뿌술 일은 없다 ^_^
4. 이제 뽑히는 주사위와 뽑히지 않는 주사위를 구해서 마치 사전을 보는것처럼 쏙쏙 key로 만들어서 비교해주면 끝이다.
사실 핵심은 사전처럼 key를 강제로 만드는 것이다.
사용했으면 좋았을 메소드는 set 자료형의 .difference()
3번 본받을만한 코드
from itertools import combinations, product
def solution(dices):
dp = {}
L = len(dices)
for A_index_combi in combinations(range(L), L//2):
B_index_combi = [i for i in range(L) if i not in A_index_combi]
A, B = [], []
for order_product in product(range(6), repeat=L//2):
A.append(sum(dices[i][j] for i, j in zip(A_index_combi, order_product)))
B.append(sum(dices[i][j] for i, j in zip(B_index_combi, order_product)))
B.sort()
wins = 0
for num in A:
left, right = 0, len(B)-1
while left <= right:
mid = (left + right)//2
if num <= B[mid]:
right = mid - 1
else:
left = mid + 1
wins += left
dp[wins] = list(A_index_combi)
max_key = max(dp.keys())
return [x+1 for x in dp[max_key]]아마 이 코드에 bisect 를 섞어서 썼다면 최적의 파이썬 코드가 아닐까싶다.
해당 코드에선 직접 이분 탐색을 구현했다.
- 뽑을 주사위 모든 조합을 구해 따라오는 안뽑는 주사위를 구한다.
- 중복조합을 통해 뽑아오는 주사위의 1~6까지의 모든 경우를 구한다.
- B로 뽑은것은 이분탐색을 진행할 것이므로 정렬을 수행한다.
- 각각 나온 경우의 수보다 작은 항목들을 승리로 넣어서 계산한다.
- 모든 경우에 대해서 구하고 그중 가장 큰 항목을 넣고 1부터 시작인 주사위로 만들어준다.
zip()을 활용하여 (1,1) (2,1) 이렇게 묶어준 것이 인상깊었다.
4번 카드게임 또졌다
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
그리디인건 눈치를 챘고 모든 경우의 수를 찾았는데 안풀렸다
그래서 도움을 조금 받았다
핵심 사항은 턴 수에 연연하지말고 턴이 진행될 수록 쌓여가는 카드가 많아진 다는 것에 집중해야한다.
예를 들면 이미 손에 N+1 을 가지고 있는 카드를 내도된다. 그리고 후보 군을 진행된 턴만큼 늘려주는 것이다. 그러면 진행되지 않은 카드를 가져갈 일도 없고 이미 턴이 진행된 카드중에서 가져가면 턴이 중요한게 아니라서 해답에는 모른다.
def solution(coin, cards):
# 타겟
T = len(cards)+1
# 카드 수
N = len(cards) //3
last_round = N +1
ans = 1
# N의 카드를 0,1 로판별
hand = [False for _ in range(T)]
# 후보군 중 이미 쓴 카드 체크
discard = [False for _ in range(T)]
# 코인을 안쓰고도 이길 수 있을 때
for i in range(N):
if hand[T -cards[i]] :
ans +=1
hand[cards[i]] = True
# 마지막 라운드 전이고 코인이 있을때
while coin > 0 and ans < last_round:
# 수행된건지 확인하는 코드
ck = False
# 위에서 진행된만큼 후보군으로 사용 가능
for i in range(N,N+ans*2):
if hand[T-cards[i]] and not discard[cards[i]]:
discard[cards[i]] = True
ans += 1
coin -= 1
ck = True
break
# 다음 1장짜리로 턴으로 조정해서 다시 구함
if ck:
continue
# 두장 뽑을 수 없음
if coin >= 2:
# 1장짜리로 못뽑았을 경우 2장짜리로 뽑아야함
for i in range(N,N+ans*2):
# 만약 뽑았다면 끝내야함
if ck :
break
for j in range(i+1, N+ans*2) :
if cards[i] + cards[j] == T and coin >= 2 and not discard[cards[i]]:
discard[cards[i]] = True
discard[cards[j]] = True
coin -= 2
ans += 1
ck = True
break
# 다시 한장짜리가 있을수 있으니 돌려보냄
if ck:
continue
# 아예없다면 그자체로 종료
break;
return ans
# 풀이의 핵심은 모든 카드를 나열해서 상태를 저장해주는 것
# (내 손에있는지 사용된 후보군인지)ck 를 사용하지 않은점과 후보군을 늘려가는 방법을 사용해서 그리디 순서를 조정하지 못했다는 점에서 패인이였다.
5번 산모양 타일링
해당은 그림을 3시간동안 그려봐서 마치 피카소가 된 느낌을 준 문제였다.
결국은 정복을 했으니....
해당 문제는 다음 삼각형과 연결되는 마지막 오른쪽 삼각형의 여부에 따라 결정이 되었다.
해당이 쓰이냐 안쓰이냐에 따라서 결정이 되었다.
해당 모양이 쓰이는 것을 a 안쓰이는 것을 b 라고한다.
a[0] = 0 // 못쓰인다.
b[0] = 1 // 그냥 삼각형 하나 가능
으로 시작을한다.
점화식은 뾰족이가 없을 경우 a[k] = a[k-1] + b[k-1] , b[k] = a[k-1] + 2*b[k-1]
a[k] 해당 모양이 사용되기 위해선 전에 어떤 모양이 쓰이든 상관이 없다.
b[k] 해당 모양만 사용하지 않아야하는데 그러기위해선 전에 쓰인것에
이렇게만 쓰일수있다.
뾰족이가 있을경우 각각 하나씩의 경우가 추가되어
b[k] = (2a[k-1] + 3b[k-1]) 로 된다.
def solution(n, tops):
MOD = 10007
a =[0] * (n+1)
b = [0] * (n+1)
a[0] = 0
b[0] = 1
for k in range(1,n+1):
# 위에 뾰족이가 있다면
if tops[k-1]:
a[k] = (a[k-1]+ b[k-1]) % MOD
b[k] = (2*a[k-1] + 3*b[k-1]) %MOD
else:
a[k] = (a[k-1]+ b[k-1]) % MOD
b[k] = (a[k-1] +2 * b[k-1]) % MOD
return (a[n] + b[n]) % MOD결론
전보다 향상된 실력을 느꼈고 대충 유형 파악이 되는 것 같다.
하지만 3차원 배열을 쓰는것, 기본기에 충실하게 복습을 해야할듯하다.
그리디 유형과 구현 유형은 어떤 문제가 나와도 1문제씩은 꼭 나오니깐 말이다.
그리고 문제가 뒤로갈수록 어렵다고 생각하기보단 같은 문제지만 어쩔수없이 순서를 지정한거라고 생각하는게 자신감에도 도움이 될듯하다. (1번 제외하고 ㅋㅋㅋ)
아무튼 L3 까지 있는 문제여서 오랜만에 집중해서 다시 풀어보니 당시 풀때보다 2문제는 더 풀어서 기분이 좋은 하루였다.
