[백준 11497] 통나무 건너뛰기

문제

N개의 통나무가 원형으로 놓여져있다. 통나무 위를 건너뛰어다니려고할 때 통나무를 어떻게 놓는지에 따라 난이도가 결정된다. 난이도는 옆에 있는 통나무와의 높이차이로 결정된다. 이때 가장 큰 차이가 난이도가 되며 첫 번째 통나무와 마지막 통나무도 서로 연결되어있는 것이다.

통나무를 적절하게 놓아서 가장 최소의 난이도를 만들자.

 

입력

입력은 T개의 테스트 케이스로 이루어져 있다. 첫 줄에 T가 주어진다.

이어지는 각 줄마다 첫 줄에 통나무의 개수를 나타내는 정수 N(5 ≤ N ≤ 10,000), 둘째 줄에 각 통나무의 높이를 나타내는 정수 Li가 주어진다. (1 ≤ Li ≤ 100,000)

 

출력

각 테스트 케이스마다 한 줄에 주어진 통나무들로 만들 수 있는 최소 난이도를 출력하시오.

---

접근

통나무를 어떻게 놓을지 생각을 해봤을 때 중앙을 기준으로 높이가 큰 통나무를 놓는 것이다.

일렬로 통나무를 놓았을 때 중앙에 가장 큰 통나무를 놓고 중앙을 기준으로 양쪽에 내림차순으로 통나무를 놓는다. 

그리고 이때의 난이도를 구하면된다.

 

그렇다면 어떤 방법으로 정렬할지 생각을 했다.

먼저 오름차순으로 정렬한다음에 처음 위치에 있는 통나무부터 2칸씩 띄어서 다시 다른 리스트에 넣는다.

그리고 위의 역순으로 2칸씩 띄어서 다시 리스트에 넣고 최대 높이를 찾는다.

 

구현

info라는 리스트에는 오름차순으로 정렬된 통나무의 정보가 있다.

이를 통나무의 개수가 홀수일 때와 짝수일 때를 나눠서 새로운 answer라는 리스트에 넣는다.

처음에는 0번 인덱스부터 마지막까지 2칸씩 띄어서 넣고, 이후에 역순으로 2칸씩 띄어서 넣는다.

    if N%2:
        # 홀수
        for i in range(0, N, 2):
            answer.append(info[i])
        for i in range(N-2, 0, -2):
            answer.append(info[i])
    else:
        for i in range(0, N, 2):
            answer.append(info[i])
        for i in range(N-1, 0, -2):
            answer.append(info[i])

이제 높이 차이가 최대가 되는 것을 찾는다. result는 첫 번째 통나무와 마지막 통나무의 차이로 초기화하고

for문으로 탐색을 하여 최댓값을 찾는다.

result = abs(answer[0]-answer[N-1])
for i in range(N-1):
	result = max(result, abs(answer[i]-answer[i+1]))

 

---

전체 코드

import sys
input = sys.stdin.readline

test_case = int(input())
for _ in range(test_case):
    N = int(input())
    info = list(map(int, input().split()))
    info = sorted(info)
    answer = []
    if N%2:
        # 홀수
        for i in range(0, N, 2):
            answer.append(info[i])
        for i in range(N-2, 0, -2):
            answer.append(info[i])
    else:
        for i in range(0, N, 2):
            answer.append(info[i])
        for i in range(N-1, 0, -2):
            answer.append(info[i])

    result = abs(answer[0]-answer[N-1])
    for i in range(N-1):
        result = max(result, abs(answer[i]-answer[i+1]))
    print(result)