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

파이썬 백준 11497번

실버 1

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

11497번: 통나무 건너뛰기

 

 

 

 

 

문제 보기

분류: 그리디 알고리즘, 정렬

 

 

 

 

 

문제 풀기

아이디어는 위와 같다. 오름차순 또는 내림차순 정렬된 리스트에서 가장 작은 수를 기준으로 하여 왼쪽과 오른쪽을 번갈아가며 순차적으로 숫자를 채워나간다.

 

 

작성된 코드는 주어진 통나무 리스트를 오름차순 정렬한다.

리스트의 가장 작은 값을 기준으로 잡고 deque() 를 이용하여 오른쪽 append(), 왼쪽 appendleft() 번갈아가며 오름차순 정렬된 리스트의 값들을 빈 new_log_ls 에 하나씩 채워나간다.

이렇게 채워진 리스트 new_log_ls 에서 첫 번째 값 new_log_ls[0] 와 마지막 값 new_log_ls[-1] 의 차이를 초기값으로 하고 남은 항목에 대해 for loop 을 돌려 서로 인접한 것들의 차이 값을 구한다. 만약, 기존에 저장된 minimum 보다 큰 값이 나올 때에는 새로이 교체한다.

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline
from collections import deque


def fnMinimumLog(N):
    log_ls.sort()           ## 리스트 오름차순 정렬.
    # print(log_ls)           # test print
    
    new_log_ls = deque()
    for i in range(N):          ## index 홀짝에 맞춰 빈 deque 를 오른쪽&왼쪽으로 채워나감.
        if i % 2 == 0:
            new_log_ls.append(log_ls[i])
        elif i % 2 == 1:
            new_log_ls.appendleft(log_ls[i])
    # print(new_log_ls)           # test print

    minimum = abs(new_log_ls[-1] - new_log_ls[0])           ## 리스트 처음과 끝 값의 차를 초기값으로 지정.
    for i in range(N - 1):
        diff = abs(new_log_ls[i + 1] - new_log_ls[i])
        if minimum < diff:
            minimum = diff
    
    print(minimum)


if __name__ == "__main__":
    T = int(inputdata().strip())
    
    for _ in range(T):
        N = int(inputdata().strip())
        log_ls = list(map(int, inputdata().split()))
        
        fnMinimumLog(N)