문제 설명
큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다. 진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다. 진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다. 높이는 임의로 선택한다. 화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다. 화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다. 화살은 계속해서 가던길을 가는데 높이는 1 줄어든다. 그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다.
우리의 목표는 모든 풍선을 터트리되 가능한한 적은 화살을 사용하는 것이다.
입력 조건
첫 번째 줄에는 정수 N(1 ≤ N ≤ 1 000 000)이 들어온다.
두 번째 줄에는 배열 Hi가 N개 들어온다.
각각의 Hi(1 ≤ Hi ≤ 1 000 000)는 i번째 풍선의 높이에 해당하며 왼쪽에서 오른쪽으로 나열되는 순서이다.
출력 조건
첫 번째 줄 한줄에 최소한 필요한 화살의 개수를 출력한다.
틀린 코드 1 (틀렸습니다.)
import sys
import heapq
n = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().split()))
heap = []
for i, elem in enumerate(arr):
# (arr[i],i) 형태로 힙에 넣는다.
heapq.heappush(heap, (-elem, i))
answer = 0
while heap:
# 기준이 되는, 가장 높은 것을 뽑는다.
standard_height, standard_index = heapq.heappop(heap)
standard_height = -standard_height
# 조건에 맞지 않은 것들을 다시 담는 리스트를 선언한다.
discarded = []
while heap:
height, index = heapq.heappop(heap)
height = -height
# 뽑은 게 기준 -1 이라면
if height == standard_height - 1:
# 그리고 더 오른쪽에 있는 것이였다면, 기준을 갱신한다.
if standard_index < index:
standard_height = height
standard_index = index
else:
discarded.append((height, index))
else:
discarded.append((height, index))
break
answer += 1
# 조건에 안 맞아서 버려진 것들은 다시 봐야할 필요가 있으므로, 다시 힙에 담아준다.
for h, i in discarded:
heapq.heappush(heap, (-h, i))
print(answer)반례
8
4 3 2 1 4 3 2 1하면, 맨 처음 4 뽑고 그 다음 4 뽑은 다음 break가 걸린다.
따라서 올바른 답은 2임에도 불구하고 답이 3으로 나온다.
틀린 코드 2 (시간 초과)
import sys
import heapq
n = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().split()))
heap = []
for i, elem in enumerate(arr):
# (arr[i],i) 형태로 힙에 넣는다.
heapq.heappush(heap, (-elem, i))
answer = 0
while heap:
# 기준이 되는, 가장 높은 것을 뽑는다.
standard_height, standard_index = heapq.heappop(heap)
standard_height = -standard_height
# 조건에 맞지 않은 것들을 다시 담는 리스트를 선언한다.
discarded = []
while heap:
height, index = heapq.heappop(heap)
height = -height
# 뽑은 게 기준 -1 이라면
if height == standard_height - 1:
# 그리고 더 오른쪽에 있는 것이였다면, 기준을 갱신한다.
if standard_index < index:
standard_height = height
standard_index = index
else:
discarded.append((height, index))
else:
discarded.append((height, index))
answer += 1
# 조건에 안 맞아서 버려진 것들은 다시 봐야할 필요가 있으므로, 다시 힙에 담아준다.
for h, i in discarded:
heapq.heappush(heap, (-h, i))
print(answer)
위에서 break를 없앤 코드다. 그러나 힙으로 풀면 시간 초과가 난다. 반례를 들면 다음과 같다.
2,2,2,2,2,2,.........1여기서 2가 100만-1개 있다고 하자. 그리고 맨 마지막에 단 하나의 1이 있다고 하자.
위 로직에 의하면 처음에 2와 1을 뽑을 때, 나머지 2를 100만-2개 pop해봐야 한다. 그리고 다시 넣어야 하므로 100만-2개 넣는다.
두 번째 2부터는 1이 없음에도 불구하고 계속 100만-x개의 pop과 push를 해야 한다... 따라서 비효율적이다.
즉, 최악의 시간 복잡도는 O(n x (nlogn+nlogn)) = o(n^2 logn)이다.
정답 코드
import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
# 현재 떠있는 화살의 개수를 나타낸다. 공간 복잡도는 O(n), O(100만)
# floating[height]=arrow_count. 즉, 높이 height의 떠있는 중인 화살의 현재 개수를 뜻한다.
# [0]*(n+1)인 경우, 인덱스 에러가 난다. 당연하게도 높이는 최대 1000000까지이기 때문이다.
# 만약 n = 5이고 그 중 높이가 1000000이라면 floating[1000000]에 의해 인덱스 에러가 난다.
floating = [0] * 1000001
# O(n) 풀이
for height in arr:
# 해당 높이에서 떠 있는 화살이 있다면,
if floating[height] > 0:
# 그 화살 중 하나를 바로 아래 높이로 이동시킨다.
floating[height] -= 1
floating[height - 1] += 1
# 해당 높이에서 떠 있는 화살이 없다면, 화살을 쏜다. 일단, 맞췄으니까 바로 높이를 -1한다.
else:
floating[height - 1] += 1
# 남아 있는 화살의 총합이 답이다. o(n)
print(sum(floating))
다른 해설들을 참고하니, 화살의 떠있는 개수를 일차원 배열로 관리하고 있었다.
배열로 상태 관리를 하면서 그리디하게 푸는 유형도 있군...
