1114 통나무 자르기

 

처음에는 우선순위 큐를 이용해서 풀어보려고 했다.

 

아래와 같은 예시가 있을 때,

5 5 3
4 2 5 3 1

 

1) 우선순위 큐에 (나무 시작 위치, 나무 끝 위치, 나무 길이) 값을 넣는다.

- 맨 처음 우선순위 큐 : (0,5,5)

 

2) 우선순위 큐를 나무 길이 내림차순 정렬한다.

 

3) 우선순위 큐에서 제일 첫번째 값을 꺼낸다.

 

4) 즉, 제일 길이가 긴 나무를 잘라나간다고 생각하면 된다.

꺼낸 나무의 중간부분을 자른다. (중간을 잘라야 제일 긴 나무의 길이를 최대한 짧게 할 수 있다.)

0,5 의 중간은 2또는 3인데,

4 2 5 3 1 중

2 또는 3이 있으므로

우선 2로 자른다면,

 

우선순위 큐에,

(0,2,2)

(2,5,3) 

을 넣어주면 된다..

 

 

이런 식으로 풀어나가려고 했으나

시간초과 

 

while 문을 이용했고,

자를 수 있는 위치가 있는지 확인해야 하므로 리스트를 이용해서

contains, indexOf 메서드를 사용하려 했으나,

각 O(N)의 시간 복잡도를 가지기에,

시간 초과가 날 수 밖에 없었다.

 

그래서 이분탐색 방법을 사용해야 했다.