99클럽 코테 스터디
월요일보다는 조금 어려운 편이었다. 두 문제 다 실전 코테에서 마주쳤다면 충분히 당황할 만한 정도? 그래도 발표하기 전에 TIL은 딱 써서 완성할 수 있었다.
1번 문제 섬 연결하기 : https://school.programmers.co.kr/learn/courses/30/lessons/42861
2번 문제 인사고과 : https://school.programmers.co.kr/learn/courses/30/lessons/152995
출처 : 프로그래머스
1번 문제 섬 연결하기
풀이 접근 - 1
섬이 100개, 다리는 최대 5050개, 다리 개수 n을 기준으로 O(n^2)도 통과할 수 있는 사이즈이지만, 더 간단하게 할 수 있을 거라는 생각이 들었다.
유니온 파인드 기법으로 효율성을 챙긴, Greedy한 해법을 찾아내었다. 그 풀이를 찾아낸 의식의 흐름을 적어보았다.
풀이 접근 - 2
섬이 n개이므로 그걸 모두 잇는 다리는 반드시 n-1개여야 한다. (그보다 많으면 반드시 다리 하나를 지우고도 모든 섬이 연결된 상태를 유지할 수 있다.)
n-1개의 다리를 선정하는 기준은 무엇인가? 가장 Greedy하게 생각하면 비용이 가장 싼 것 n-1개를 고르면 된다. 하지만 그렇게 골랐는데 모든 섬이 이어져 있을 거란 보장이 없다. 여기서 두 단계에 걸친 발상을 했는데,
가장 값이 싼 다리 1개는 반드시 포함될까?
-> 답은 Yes이다. 이 다리가 a번 섬과 b번 섬을 잇는 c코스트의 다리라고 하자.
이 다리를 포함하지 않고 n-1개의 다리로 모든 섬을 이으면, 그 다리들 중에 하나를 제거해서 a섬과 b섬이 분리되도록 할 수 있고, c코스트의 다리를 추가해서 다시 이어지도록 하면 모든 섬이 연결된 상태가 유지되면서 비용이 줄거나 같게 되기 때문이다.
값이 싼것부터 정렬해두고 하나씩 넣을지 말지 결정하면서 순회할 수 있을까? (O(n), n≤5050)
-> 앞서 살펴봤듯, 가장 값이 싼 다리는 포함된다. 아직 섬이 다 이어지지 않았다면(n>2일 경우), 2번째로 값이 싼 다리(가장 싼것과 같은 값일 수도 있다)도 포함되어도 될 것 같다.
근데 3번째는? 이렇게 고른 다리 3개가 삼각형을 이루면 배제되어야 한다. 이걸 어떻게 구현할 수 있을까?
풀이 접근 - 3
값이 싼 다리부터 순회하면서 이걸 선택할지 말지 결정한다. 결정되면, 다리는 반드시 두 개의 원래 이어지지 않았던 섬을 잇게 된다(그렇지 않은 것은 선택할 수 없다).
이 두 섬을 a와 b라고 하면, 크게 볼 때 a섬과 이어져있던 섬들의 그룹과 b섬의 그룹을 잇는 결과라고 볼 수 있다. 이걸 다른 말로 하면...
다리를 하나 선택할 때마다, 섬의 그룹의 수가 1씩 줄고, 그룹이 1개 남을 때까지 (= 모든 섬이 이어질 때까지) 계속된다.
즉, 그룹마다 대표 번호를 매기고(처음엔 각 섬의 번호 1~n이 될 것이다), 다리를 하나 선택할 때마다 유니온 파인드 기법으로 그룹의 대표를 통일시킨다. (여기선 유니온 함수)
선택할지 말지의 기준은, 두 섬의 대표가 서로 다르면 선택, 그렇지 않으면 고르지 않는다. (대표를 파인드 함수로 찾는다)
깔끔한 Greedy 풀이 완성!
코드 (Python3, 통과, 최대 0.05ms, 10.4MB)
rn[n]은 n번 섬이 속한 그룹의 대표 번호(대표 번호는 해당 그룹의 섬 중 가장 낮은 번호로 한다)를 나타낸다.
주어진 costs 리스트를 가격순으로 오름차순 정렬해서 그대로 사용했다.
밑에 while문에서 bridges는 현재까지 선택한 다리 개수, cost는 현재까지 누적 비용, now는 지금 몇번째 다리를 보고 있는지이다.
수정 2: 1번 문제도 주석 마구마구 추가
def solution(n, costs):
answer = 0
rn = [i for i in range(n + 1)] # representative number
costs.sort(key=lambda bridge: bridge[2])
def union(a, b): # a번 섬과 b번 섬을 연결하고 대표자를 더 작은 숫자로 통일, a와 b 모두 대표여야함
rn[max(a,b)] = min(a,b)
return
def find(a): # a번 섬이 속한 그룹의 대표 번호 찾기
if rn[a] == a:
return a
b = find(rn[a])
rn[a] = b # find 함수의 재귀 횟수가 계속 늘어나는 걸 방지하기 위해 중간에 바뀐 번호가 있으면 최신화한다
return b
bridges = 0 # 선택된 다리 개수
cost = 0 # 누적 비용
now = 0 # 현재 다리 번호
while bridges < n - 1:
a, b, c = costs[now]
ra, rb = find(a), find(b) # a섬과 b섬의 대표 번호 찾기
if ra != rb: # 대표가 다르면 = 서로 다른 그룹에 속해있으면
union(ra, rb) # 대표끼리 union해서 대표 통일
bridges += 1 # 다리 선택했음
cost += c # 비용 추가
now += 1 # 다음 다리
answer = cost
return answer2번 문제 인사고과
풀이 접근 - 1
굉장히 세그먼트 트리 냄새가 나는 문제이다.
하지만 점수의 종류가 2개뿐이고, 사람 수도 10만에 불과해서 그냥 빡구현으로 풀었다.
세그먼트 트리에 약해서 자꾸 피해서 풀려고 하는 습관은 좋지 않은데 고쳐봐야겠다...
풀이 접근 - 2
인센티브를 못 받는 것을 '탈락'이라고 하겠다.
한 가지 점수 기준으로 내림차순 정렬하면, 그 점수가 본인보다 낮거나 같은 사람에게는 절대 '탈락'하지 않는다. 반대로, 그 점수가 본인보다 높은 사람들은 전부 자기보다 다른 점수가 낮거나 같아야 '탈락'을 면할 수 있다.
즉, 근무태도 점수 기준으로 내림차순 정렬하고, 같은 점수인 사람끼리 묶고(묶어야 구현하기 편하한 부분이 있다), 묶은 점수 단위로 순회하면서, 동료평가점수 역대 최고점을 기록하면서 탈락 여부를 결정해서 등수를 매기면 된다.
등수를 매기는 것도, 1등부터 꼴지까지 비탈락자 전부를 매기는 게 아니라, 주인공인 완호보다 점수가 높은 사람 수만 세면 된다.
지금까지 말한 것을 구현하는 게 전부다. 물론 오래 걸리고 실수하기 쉬우므로 땡구현도 해봐야 는다.
코드 (Python3, 통과, 최대 169ms, 33.4MB)
sido[k]는 근무태도점수가 k점인 사람들의 동료평가점수를 내림차순으로 정렬한 것이다.
while문을 두 단계로 쪼개 놓은 이유는, 완호의 위치를 특정해서 완호가 탈락이면 그 뒤를 할 필요가 없기 때문이다.
hprs(동료 평가 점수 최고점)은 업무태도점수가 같은 사람들 모두 검사를 끝낸 뒤에 갱신한다. (업무태도점수가 같은 사람끼리는 동료평가점수가 더 낮아도 탈락 안하니까)
수정 : 코드가 알아보기 힘들다고 판단해서 주석 마구마구 추가
def solution(scores):
n = len(scores)
wanho = [scores[0][i] for i in range(2)]
ws = sum(wanho)
sido = [[] for _ in range(100001)] # scores in descending order
for i in range(n):
was, prs = scores[i][0], scores[i][1] # working attitude score, peer review score
sido[was].append(prs)
for j in range(100001):
sido[j].sort(reverse = True)
hprs = 0 # highest peer review score
was = 100000
rank = 1
while was > wanho[0]: # 완호보다 근무태도점수가 높은 사람들 (점수 내림차순)
if sido[was]: # 해당 근무태도점수에 사람이 없으면 건너뜀
temp_hprs = sido[was][0] # 해당 근무태도점수인 사람 중 동료평가점수 1위
for prs in sido[was]:
if prs >= hprs: # 동료평가점수가 역대 최고점보다 높거나 같아야 탈락을 면함
if prs + was > ws: # 완호보다 점수 높은 사람만 세서 등수 기록
rank += 1
else: # 동료평가점수를 내림차순 정렬해놨으므로 탈락인 사람보다 더 낮은 점수는 볼필요 없음
break
if temp_hprs > hprs: # 동료평가점수 역대 최고점 갱신 (근무태도점수 같은사람끼리는 비교할필요 없으므로 한 점수대 끝나고 갱신하기)
hprs = temp_hprs
was -= 1
if wanho[1] < hprs: # 완호가 탈락이면 뒤는 볼필요 없음
rank = -1
else:
while was > -1: # 완호보다 동료평가점수가 낮거나 같아도 근무태도점수가 높으면 순위가 높을 수 있으므로 끝까지 돌아야 함
if sido[was]:
temp_hprs = sido[was][0]
for prs in sido[was]:
if prs >= hprs:
if prs + was > ws:
rank += 1
else:
break
if temp_hprs > hprs:
hprs = temp_hprs
was -= 1
answer = rank
return answer