99클럽 코테 스터디
스터디에 참여한 첫 날(저번 주 목요일)보단 문제가 평이했다. 저번주만 유독 어려웠던 건가 싶다.
덕분에 1번만 겨우 푼 저번주와 달리 2문제 다 코드에 주석도 달고 TIL도 발표 전에 미리미리 작성할 수 있었다.
1번 문제 부대복귀 : https://school.programmers.co.kr/learn/courses/30/lessons/132266
2번 문제 풍선 터뜨리기 : https://school.programmers.co.kr/learn/courses/30/lessons/68646
출처 : 프로그래머스
1번 문제 부대복귀
풀이 접근
부대원이 최대 500명, 각자 다른 위치에 있고 먼 길을 온다면 n≤100,000, roads≤500,000이기 때문에 어떤 방식으로든 시간초과를 걱정해야 한다.
이럴 때는 문제의 조건에 유의하면, 거리는 왕복이 똑같고 도착지는 한 곳이라는 점에 착안하여 역으로 도착지에서 출발하면 road의 개수 r 기준 O(r)에 끝낼 수 있다.
도착지에서 출발하면 단순 bfs로 문제가 매우 간단해진다. depth가 곧 거리이므로 각 점까지의 거리를 다 재고, source에 있는 번호들이 각각 거리 몇인지만 체크하면 끝.
코드 (Python3, 통과, 최대 780ms, 112MB)
나는 특이하게 bfs를 set 자료구조를 이용해서 한다. 출발하는 점을 다 set에 몰아넣고, 각 점에서 한 번 이동해서 갈 수 있는 점도 다 set에 넣고, 이를 반복하는 식이다.
def solution(n, roads, sources, destination):
# 풀이의 요지 : destination를 역으로 출발점으로 삼고 거리를 bfs로 다 재면 O(n)에 끝난다
answer = []
dfd = [-1] * (n+1) # distance from destination
connected = [[] for _ in range(n + 1)] # connecte[a]에 b가 있으면 a와 b가 연결된 길이 있음
for r in range(len(roads)):
road = roads[r]
a,b = road[0],road[1]
connected[a].append(b)
connected[b].append(a)
visited = [False] * (n + 1)
now = {destination} # set으로 bfs하기
distance = 0
while now: # while문이 한번 돌때마다 destination에서 거리가 1씩 멀어지는 모든 점을 now에 넣는다
the_next = set()
for point in now: # 방문처리를 미리 싹 하지 않고 돌면서 하면 이미 now에 있는 점들도 next에 넣어버리는 문제가 있음
visited[point] = True
for point in now:
dfd[point] = distance
for p in connected[point]:
if not visited[p]:
the_next.add(p)
distance += 1
now = the_next
for point in sources:
answer.append(dfd[point])
return answer2번 문제 풍선 터뜨리기
풀이 접근 - 1
특정 기법을 적용하면 되는 유형이 아닌, 아이디어가 필요한 유형이다. 문제의 조건을 정확히 이해하고 분석할 필요가 있다.
인접한 두 풍선을 고르고, 둘 중 번호가 높은 것만 터뜨릴 수 있다. 이 행위는 풍선이 단 한 개 남을 때까지 계속된다.
문제의 조건에서 '딱 한 번 둘 중 번호가 낮은 것을 터뜨릴 수 있다'는 조건만 제외하면 위와 같다. 그러면 어떻게 될까? 여기선 직관과 통찰, 아니면 여러 번 시뮬레이션을 돌려봐서라도 결과를 알 필요성이 있다.
결과는 '어떤 걸 고르던지 간에 항상 가장 번호가 낮은 풍선 한 개가 남는다'이다. 어찌 보면 당연한 결과이나, 이를 알고 가야 문제의 풀이에 접근하기 쉽다.
그렇다면 문제로 돌아와서, 어떤 풍선을 살릴 수 없을까? 이를 바로 생각해내기 어렵다면, 어떤 풍선을 살릴 수 없을까?
풀이 접근 - 2
어떤 풍선을 끝까지 살리려면, 그 풍선을 기준으로 왼쪽과 오른쪽에 있는 풍선들은 두 그룹으로 완전히 분리된다.
이 점에 착안해야 한다. 항상 인접한 두 풍선을 고르기 때문에, 끝까지 살려 둘 풍선의 양옆 반대편에 있는 풍선들은 끝날때까지 같이 선택될 수 없다.
인접한 두 풍선을 고른 뒤에, 둘 중 번호가 낮은 풍선을 터뜨리는 기회를 '찬스'라고 하자. 이 '찬스'는 끝까지 살릴 풍선의 왼쪽에 쓸 수도 있고, 오른쪽에 쓸 수도 있다. 어느 한 쪽에 쓰면, 반대쪽에는 찬스를 쓸 수 없다. 그러면 반대쪽에는 무조건 '가장 번호가 작은 풍선이 살아남는다'가 적용되고, 이는 끝까지 살리려는 풍선을 포함해서 적용된다.
즉, 어느 한 풍선이 끝까지 살아남을 수 있으려면 해당 풍선의 왼쪽 모두, 또는 오른쪽 모두보다 그 풍선의 번호가 작아야 하는 것이다. (둘 모두에 해당되면 모든 풍선 중 최소번호이므로 찬스를 안 써도 무조건 살아남을 수 있다.)
반대로, 찬스를 쓰는 쪽은 어떤가? 찬스를 딱 한 번 쓸 수 있다고 해서, 원하는 풍선을 남길 수 있는가? 이 쪽도 검증이 필요하지만, 정답은 '있다'이다.
방법은 간단하다. 살려둘 풍선을 제외한 모든 풍선을 아무 순서로나 찬스 없이 한 개 남을 때까지 터뜨린다. 그러면 아까 얻은 결론과 같이, 가장 번호가 낮은 풍선 한 개가 남는다. 그러면 그 풍선과 살려둘 풍선 둘을 선택하고 찬스를 써서 그 풍선을 터뜨리면 끝난다.
아래는 하나의 예시이다. 9개의 풍선 중 정가운데(5번째)에 있는 15번 풍선은 최후의 한 개로 살아남을 수 있는 풍선이다. 왼쪽의 풍선 중 가장 낮은 -1번 빼고 다 터뜨린 후 -1을 찬스를 써서 터뜨리고, 오른쪽 풍선은 어떤 순서대로 해도 15번 풍선이 남는다.
풀이 접근 - 3
방법론은 논리적 검증이 끝났으니, 시간초과가 나지 않게 적절히 구현해야 한다. 풍선은 무려 100만개나 되기 때문에, 각각의 풍선에 대해 그 풍선을 살릴 수 있는지 없는지 일일히 검사하면 O(n^2)으로 무조건 시간이 터진다.
따라서, O(n)의 풀이가 필요하고, 구체적으로는 왼쪽으로부터 순회 한 번, 오른쪽에서부터 순회 한 번 해서 순회 두 번으로 끝낼 수 있다.
왼쪽에서부터 순회하는 경우, 순회하면서 '현재까지 풍선 번호 중 최저'를 기록하고, 그게 갱신될 때마다 해당 풍선을 살릴 수 있다고 표시한다. (해당 풍선은 그보다 왼쪽에 있는 모든 풍선보다 번호가 작을 테니까)
오른쪽에서 순회하는 경우도 마찬가지로 최저번호가 갱신될 때마다 표시한다. 각각의 개수를 세서 더해도 되지만, 이 경우엔 모든 풍선 중 최저번호인 풍선은 왼쪽 오른쪽에 둘다 해당되므로 한 개를 빼야 함에 유의한다.
코드 (Python3, 통과, 최대 300ms, 56MB)
def solution(a):
# 풀이의 요지 : 최후까지 남을 수 있는 풍선은, 그 풍선의 왼쪽 모두(또는 오른쪽 모두)보다 작아야 한다.
# 어떤 풍선의 양 쪽 모두에 해당 풍선보다 번호가 작은 풍선이 존재하면, 둘 모두를 터뜨릴 방법이 없기 때문
answer = 0
n = len(a)
sfas = [False]*n # smallest from any side, 이게 True인 순번의 풍선만이 문제의 조건을 만족할 것
snfl = 10**9 + 1 # smallest number from left
for i in range(n): # 왼쪽->오른쪽으로 순회하면서, 나온 풍선 중 제일 작은 번호인 것들은 조건을 만족한다.
if a[i] < snfl: # 해당 풍선의 왼쪽에는 해당 풍선보다 큰 번호밖에 없기 때문
sfas[i] = True
snfl = a[i]
snfr = 10**9 + 1 # smallest number from right
for i in range(n-1, -1, -1): # 마찬가지로 오른쪽->왼쪽으로도 순회한다.
if a[i] < snfr:
sfas[i] = True
snfr = a[i]
for i in range(n):
if sfas[i]:
answer += 1
return answer