입국심사
https://programmers.co.kr/learn/courses/30/lessons/43238
내 아이디어
각 심사관들의 배수들을 모두 저장해서 n 번째 값 return
ex) n = 6 | times = [7, 10] | return = 28
7 의 배수 => [7, 14, 21, 28, 35, ...]
10 의 배수 => [10, 20, 30, 40, ...]
모두 합치면 [7, 10, 14, 20, 21, 28, 30, ...]
=> 7 분에 끝나는 것 하나, 10 분에 끝나는 것 하나, 14 분에 끝나는 것 하나, ...
n 번째는 28 분에 끝남
하지만 범위가 너무 크고... 배수의 제한을 잡기 힘듦...
제한사항
- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
다른 사람의 풀이
def solution(n, times):
answer = 0
start, end, mid = 1, times[-1] * n, 0
while start < end:
mid = (start + end) // 2
total = 0
for time in times:
total += mid // time
if total >= n:
end = mid
else:
start = mid + 1
answer = start
return answerstart : 최소 1 분
end : 최대 times[-1] * n 분
로 잡고 이분탐색을 돌리기
total : 몇명의 인원을 심사할 수 있는지 세줌
ex) n = 6 | times = [7, 10] | return = 28
start = 1 mid = 30 end = 60 => 7 명 & end 변경
start = 1 mid = 15 end = 30 => 3 명 & start 변경
start = 15 mid = 27 end = 30 => 5 명 & start 변경
start = 27 mid = 28 end = 30 => 6 명 & end 변경
start = 27 mid = 27 end = 28 => 5 명 & start 변경
start = 28 mid = 28 end = 28 => return 28
인덱스에 대한 이분탐색만 봐왔는데 값으로도 가능한게 신기했다
가장 먼 노드
https://programmers.co.kr/learn/courses/30/lessons/49189
내 풀이 - 실패
answer = 0
maxlen = 0
dp = []
def func(dic, n, cnt, path):
global answer, maxlen, dp
if dp[n] < cnt:
return
dp[n] = min(dp[n], cnt)
for i in range(len(dic[n])):
a = dic[n][i]
if a not in path:
path.add(a)
func(dic, a, dp[n]+1, path)
path.remove(a)
def solution(n, edge):
global answer, dp
dic = {i:[] for i in range(1, n+1)}
dp = [float('inf')] * (n+1)
for a, b in edge:
dic[a].append(b)
dic[b].append(a)
func(dic, 1, 0, {1})
m = 0
for d in dp:
if d != float('inf') and m < d:
m = d
answer = dp.count(m)
return answerdic 에 1 ~ n 까지의 노드들과 각 노드마다 연결 현황 저장
n 길이의 dp 도 만들어줌
재귀함수 돌려서 각 노드마다 최단 경로를 dp 에 update
cnt : 경로의 길이
최단 경로면 굳이 왔던 곳을 다시 올 필요는 없을 것 같아서
path 를 이용해서 지나간 노드들을 모두 저장
다음 재귀로 넘어갈때는 처음 보는 노드로만 이동
dp 의 최댓값을 찾아서 개수 return
다른 사람의 풀이
def solution(n, edge):
graph =[ [] for _ in range(n + 1) ]
distances = [ 0 for _ in range(n) ]
is_visit = [False for _ in range(n)]
queue = [0]
is_visit[0] = True
for (a, b) in edge:
graph[a-1].append(b-1)
graph[b-1].append(a-1)
while queue:
i = queue.pop(0)
for j in graph[i]:
if is_visit[j] == False:
is_visit[j] = True
queue.append(j)
distances[j] = distances[i] + 1
m = max(distances)
answer = distances.count(m)
return answer재귀 말고 queue 를 이용한 bfs
graph 에 연결된 노드들을 쭉 저장해준다
queue 는 0 부터 시작하고
pop(0) 한 노드 i 와 연결된 노드들은 모두 queue 에 저장
한번 본 애들은 is_visited 를 True 로 설정하고
거리 길이도 distances[i] + 1 로 update
그러면 최종적으로 모든 노드들의 거리가 계산되고
그 중에 최댓값을 찾아서 count 해준 값을 return
순위
https://programmers.co.kr/learn/courses/30/lessons/49191
내 풀이 - 실패
def solution(n, results):
answer = 0
win = {i:[] for i in range(1, n+1)}
lose = {i:[] for i in range(1, n+1)}
for a, b in results:
win[a].append(b)
lose[b].append(a)
for i in range(1, n+1):
winner = set(win[i])
for w in win[i]:
winner |= set(win[w])
win[i] = list(winner)
loser = set(lose[i])
for l in lose[i]:
loser |= set(lose[l])
lose[i] = list(loser)
for i in range(1, n+1):
if len(win[i]) + len(lose[i]) == n-1:
answer += 1
return answer각 숫자마다 이긴 사람과 진 사람을 모두 저장 => win, lose
자신이 이긴 사람과 연결된 사람들까지 모두 더해줌, 연결된 진 사람도 마찬가지
마지막에 이긴 사람과 진 사람의 수가 n-1 이라면 순위가 정해진 것이므로 answer + 1
하지만 모두 통과하진 못했다..ㅎ
다른 사람의 풀이
from collections import defaultdict
def solution(n, results):
answer = 0
win, lose = defaultdict(set), defaultdict(set)
for result in results:
lose[result[1]].add(result[0])
win[result[0]].add(result[1])
for i in range(1, n + 1):
for winner in lose[i]: win[winner].update(win[i])
for loser in win[i]: lose[loser].update(lose[i])
for i in range(1, n+1):
if len(win[i]) + len(lose[i]) == n - 1: answer += 1
return answer똑같이 win, lose 를 구해주는데 set 를 이용
win : i 가 이긴 애들
lose : i 를 이긴 애들
헷갈리지 않게 주의!!
i 를 이긴 사람들은 i 한테 진 애들도 이긴 것이므로 win[winner].update(win[i])
i 한테 진 사람들은 i 를 이긴 애들한테도 진 것이므로 lose[loser].update(lose[i])
