(Python) - BOJ(11497번) : 통나무 건너뛰기

https://www.acmicpc.net/problem/11497

11497번: 통나무 건너뛰기

---

• 해설 : 

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2, 4, 5, 7, 9}인 통나무들을 세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면, 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 [2, 9, 7, 4, 5]의 난이도는 |2-9| = 7이다. 우리는 더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9| = 4이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.

 

 

 

---

• 풀이 :

그리디한 방법을 사용하였다. 통나무의 높이를 오름차순으로 정렬한 후 양쪽 끝을 가르키는 포인터 rear, front를 만들어주었다. 이 두 포인터를 번갈아가면서 선택하여 차이를 최소로 만들어주었다.

 

 

 

---

• 소스코드 : 

 

from collections import deque
 
def leastCnt(nums,log):
    answer = 0
    sol = [0 for _ in range(nums)]
    log.sort()
    queue = deque(log)
    rear = -1
    front = 1
    sol[0] = queue.popleft()
    flag = 0
    while queue:
        X = queue.popleft()
        if flag == 0:
            flag = 1
            sol[rear] = X
            rear -= 1
        else:
            flag = 0
            sol[front] = X
            front +=1
    for i in range(len(sol)-1):
        if abs(sol[i+1]-sol[i]) > answer:
            answer = abs(sol[i+1]-sol[i])
    if abs(sol[-1]-sol[0]) > answer:
        answer = abs(sol[-1]-sol[0])
    return answer
 
 
if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        nums = int(input())
        log = list(map(int,input().split()))
        print(leastCnt(nums,log))