[Python] Baekjoon - 11497. 통나무 건너뛰기

백준 11497번 통나무 건너뛰기는 원형으로 세워진 통나무를 건너뛰어 다닐 때 각 인접한 통나무의 높이 차가 최소가 되게 하는 문제다. 그리디 알고리즘을 통해 해결할 수 있으며 난이도는 실버 1이다.

 

백준 11497번 통나무 건너뛰기 문제 정보

알고리즘 분류

• 그리디 알고리즘

난이도

• 실버 1

 

통나무 건너뛰기 문제 요약

• input: 숫자 배열(각 통나무의 높이)
• output: 가능한 최소 난이도
• 난이도: 인접한 두 통나무 간의 높이의 차의 최댓값(첫 통나무와 마지막 통나무도 인접한 것으로 여김)

 

문제 풀이 방법

과정

• 오랜만에 푼 문제라서 어떤 알고리즘으로 풀어야 될지 감이 안 왔었다. 한참 고민하다가 알고리즘 분류 눌러서 그리디 알고리즘인걸 보고 나서야 풀 수 있었다.
• 처음엔 모든 통나무를 그래프 정점으로 생각하고 모든 정점 간의 거리를 구해볼까 했는데 N이 10000 이하라서 기각.
• '최소'만 생각하고 최단경로 생각했다가 바로 기각.
• '그리디'인걸 알고는 이렇게 저렇게 배치해보다가 그냥 diff가 작은 순으로 나열하되, 순환적인 구조인걸 감안해서 왼쪽 오른쪽 번갈아가며 통나무를 배치하도록 함
  • [9, 7, 5, 4, 2] 일 때 9를 기준으로 좌우에 번갈아가며 배치 9 -> 9,7 -> 5,9,7 -> 5,9,7,4 -> 2,5,9,7,4

풀이

1. 통나무의 높이 배열을 내림차순으로 정렬
2. 제일 높은 통나무 기준 오른쪽에 배치될 통나무들에 대한 높이차 모두 구하기
3. 왼쪽에 배치될 통나무들 높이차 모두 구하기
4. 높이 차의 최댓값(난이도) 반환

 

코드

import sys


# 배열의 최소 난이도를 구하는 함수
def getDifficulty(arr):
    # 배열을 내림차순으로 정렬
    arr.sort(reverse=True)
    max_diff = 0

    # 오른쪽 통나무들 높이 차 계속 구하며 최대값과 비교
    idx, prev = 0, arr[0]
    while idx < len(arr):
        crnt = arr[idx]
        max_diff = max(max_diff, abs(prev - crnt))
        prev = crnt
        idx += 2

    # 배열 길이 짝수면 마지막 통나무도 검사 해야함(홀수면 이미 검사 함)
    if len(arr) % 2 == 0:
        idx = len(arr) - 1
    else:
        idx = len(arr) - 2

    # 왼쪽 통나무들 높이 차 계속 구하며 최대값과 비교
    while idx > 0:
        crnt = arr[idx]
        max_diff = max(max_diff, abs(prev-crnt))
        prev = crnt
        idx -= 2

    max_diff = max(max_diff, abs(prev - arr[0]))

    return max_diff


if __name__ == '__main__':
    TC = int(input())
    for T in range(1, TC+1):
        N = int(input())
        L = list(map(int, sys.stdin.readline().split()))

        res = getDifficulty(L)
        print(res)