[백준] 11497번: 통나무 건너뛰기 (Python, 파이썬)

문제 링크: https://www.acmicpc.net/problem/11497

11497번: 통나무 건너뛰기

 

내가 푼 방법

: 인접한 통나무 간의 높이 차이를 최소화하기 위해서는, 높이 순서대로 오름차순 정렬해서 아래 그림과 같이 만드는 것이다. 

짝수 index들 + 홀수 index의 reverse를 더해주면, 최소 난이도를 갖게 된다. 

그다음에 인접한 통나무들 간의 난이도를 저장한 다음에 max 값을 취해주면 된다. 

import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    n = int(input())
    logs = list(map(int, input().split()))
    logs = sorted(logs)
    even = []
    odd = []
    for i in range(n):
        if i % 2 == 0:
            even.append(logs[i])
        else:
            odd.append(logs[i])
    logs = even + odd[::-1]
    levels = []
    for i in range(n):
        if i == 0:
            levels.append(abs(logs[n-1]-logs[i]))
        else:
            levels.append(abs(logs[i]- logs[i-1]))
        
    
    print(max(levels))

코테를 통과하긴 했는데 뭔가 찝찝해서 (너무나 최적의 코드가 아닌 느낌 낭낭) 다른 분의 코드를 참고해서 다시 공부!

 

Key point:

결과적으로, logs = even + odd[::-1] 배열은 만들 필요가 없었다!

그냥 난이도만 계산하면 되기 때문에, index가 2차이 나는 것들끼리 빼서 가장 큰 값을 return 하면 되는 것

import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    n = int(input())
    logs = list(map(int, input().split()))
    logs = sorted(logs)

    res = 0
    for i in range(2, n):
        res = max(res, abs(logs[i]-logs[i-2]))

    print(res)