[Python/Java] 통나무 건너뛰기 (백준 11497번 파이썬/자바)

백준 11497번 통나무 건너뛰기

문제 바로가기

🙄 문제 이해

단순한 정렬문제로 접근하였으나, 통나무가 원형으로 놓아져있기 때문에 이를 고려해야 합니다.

아래 그림처럼 정렬할 경우 원형 배치로 인해서 |9-2| 인 7의 차이가 발생합니다. 이 경우 의도한 결과가 아니기에 다른 방법을 찾아야 합니다.

📝 문제 풀이

핵심은 가장 큰 통나무를 기준으로 큰 순서대로 양옆에 번갈아가며 배치하는 것입니다.

위의 그림에서 9(idx 0)를 기준으로 양 옆을 살폈을 때 더 작은 것은 7(idx 1)와 5(idx2) 중 5 입니다.

마찬가지로 7(idx 1)을 기준으로 할 때도 idx 3인 4와의 차이를 고려하게 되고, 이를 바탕으로 진행합니다.

💻 파이썬 코드

#백준 11497 통나무 건너뛰기

t = int(input())
for _ in range(t):
    n = int(input())

    arr = list(map(int, input().split()))

    arr.sort(reverse=True)

    gap = 0
    for i in range(n-2):
        if abs(arr[i]-arr[i+2]) > gap:
            gap = abs(arr[i]-arr[i+2])
    print(gap)

💻 자바 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class boj11497 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int t = Integer.parseInt(br.readLine());
		for (int i=0; i<t;i++) { //테케 반복
			int n = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			
			Integer[] arr = new Integer[n];
			for (int j=0;j<n;j++) {
				arr[j]= Integer.parseInt(st.nextToken());
			}
			
			Arrays.sort(arr, Collections.reverseOrder());
			
			int gap = 0;
			for (int k=0; k<n-2;k++) {
				gap =  Math.max(gap, Math.abs(arr[k]-arr[k+2]));
			}
			System.out.println(gap);
		}
	}
}