[백준] BOJ 11497, 통나무 건너뛰기 파이썬 Python

서론

이번 포스팅에서는 백준 11497번 통나무 건너뛰기 문제를 파이썬 언어로 풀겠다. 이번 포스팅 역시 어떻게 풀이 과정에 도달했는지에 설명하고 이어서 코드를 작성하는것으로 마무리할 예정이다. 백준 11497 문제를 보려면 여기로 가면 된다. 통나무 건너뛰기 문제를 보면 아래 그림이 보이는데, 보자마자 뭔가 어려워 보여서 겁먹기 쉽다. 하지만 그냥 숫자로 접근한다면 저 그림을 처음 볼때 느꼇던 난이도가 아니라는것을 쉽게 알 수 있을 것이다.

 

 

---

백준 11497 풀이과정 1

문제를 읽다보면 첫번째 포인트가 있는데, 입력 값은 리스트로 주지만, 통나무는 위에 그림과 같이 원형으로 이어져 있다는 사실이다. 처음 보면 뭐야 '걍 오름차순 내지 내림차순으로 정렬 하면 되잖슴~' 하겠지만 이렇게 된다면 첫번째 통나무와 마지막 통나무의 차가 극대화돼서 최악의 결과가 나타나게 된다. 그리고 예시를 보면 [2,4,5,7,9]를 입력 받았을 때(참고로 이건 우연히 정렬된 상태라 풀이를 할 땐 정렬해줘야된다.) 정답이 [2,5,9,7,4]이다. 이걸 처음에 봤을때 가장 큰 값이 가운데 로 나온 걸 캐치했다.

---

백준 11497 풀이과정 2

큰값이 가운데 오는 걸 안 이상 큰 값과 가장 차이가 적은걸 큰 값 양단에 배치해야 된다는 것은 자연스럽게 떠올릴 수 있었다. 그래서 가령 오름차순 순서가 [a,b,c,d,e] 면 [a,c,e,d,b] 이렇게 되어야 한다. 그럼 이걸 어떻게 구현할 수 있을까? 첫번째로 생각했던 것은 a라는 배열을 만들고, b라는 배열을 만들어서 순서대로 집어 넣는 것이다. arr1에 a넣고, arr2에 b넣고 arr1에 c넣고 arr2에 d 넣고 arr1에 e 넣은 다음(arr1=[a,c,e], arr2=[b,d]) arr2를 다시 내림차순으로 정렬해서 두 배열을 합치는 것이다. 물론 이렇게 해도 풀리긴한다. 백준이 요구하는 초에는 안전하게 들어갈 수 있다. 그런데 이거보다 더 효율적인 방법이 있었는데, 바로 slicing이다.  arr1에는 arr를 2씩 띄면서 넣고, arr2에는 역순서로 넣으면 됐다. arr1 = arr[::2] , arr2 = arr[1::2][::-1] 이렇게 말이다. 이후에 이 배열을 합친 다음, 합쳐진 배열을 돌아가며 두 차이가 가장 큰 값을 출력하면 된다. 첫번째로 생각했던 방식으로 진행하면 메모리가 35024KB, 시간이 232ms지만, 두번째 방식인 slicing을 이용하면 33432KB, 204ms가 소요된다. 

---

 

백준 11497 파이썬 코드

slicing을 이용한 코드는 아래와 같다.

import sys
input = sys.stdin.readline
t = int(input())

for _ in range(t):
    n = int(input())
    arr = sorted(map(int,input().split()))
    
    a_arr = arr[::2]
    b_arr = arr[1::2][::-1] # b_arr는 역순으로
    ans = a_arr + b_arr # 두 배열 합치기 -> 올바른 배열
    
    res = ans[-1] - ans[0] # ans 배열 중 돌면서 차이 가장 큰거 찾는 과정
    for i in range(n):
        res = max(res, abs(ans[i]-ans[i-1]))
    print(res)

 

만약에 다른 문제 풀이를 보고 싶다면 아래 링크로 가서 원하는 부분을 보면 된다.

코딩 테스트 준비 계획