백준 11497번: 통나무 건너뛰기 (Python/Java)

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

11497번: 통나무 건너뛰기

 

 

 

접근

---

반복 for문을 돌려서 매번 두 수의 차를 구하고 최댓값을 구한 뒤 배열에 집어넣으면 무조건 시간 초과가 날 수밖에 없는 문제. 때문에 수들을 정렬시킬 규칙을 찾아야 한다. 사실 이 부분에서 조금 헷갈리긴 했으나 잘 생각해보면 어렵지 않게 규칙을 찾을 수 있다.

 

우선 숫자들을 순서대로 정렬한다. 그 뒤 첫 번째에 가장 작은 수, 마지막에 다음 수, 두 번째에 다음 수, 뒤에서 두 번째에 다음수... 이렇게 정렬하면 두 수들의 차가 가장 작은 배열을 만들 수 있게 된다. 원리는 간단하다. 이렇게 정렬하면 오름차 순으로 가장 큰 수까지 갔다가 다시 내림차순으로 배열의 마지막까지 가기 때문이다. 내림차순으로 배열의 마지막에 가기 때문에 배열의 첫 번째 수와 배열의 마지막 수 또한 사실상 정렬된 원 배열의 바로 옆의 수이기 때문에 차이가 적을 수밖에 없다.

 

예시를 통해 살펴보자. 주어진 배열은 [2, 4, 5, 7, 9]다. 굳이 두 번 타자 칠 필요 없이 오름차순으로 정렬되어있다. 그것 참 다행이다. 이제 이 배열을 앞서 말한 방법으로 정렬해보도록 하자.

 

첫 번째 숫자를 가장 앞에 넣기, [2, 0, 0, 0, 0]. 다음 숫자를 마지막에 넣기, [2, 0, 0, 0, 4]. 다시 앞으로 돌아와서 다음 숫자를 넣기, [2, 5, 0, 0, 4]. 또다시 뒤로 돌아가 다음 숫자 넣기, [2, 5, 0, 7, 4]. 이제 마지막 숫자 넣기, [2, 5, 9, 7, 4].

 

이렇게 완성된 배열 [2, 5, 9, 7, 4]는 양 옆 숫자 차이가 가장 작은 배열이다. 규칙은 여기서 끝나지 않는다. 숫자들을 순서대로 앞 뒤 번갈아 가면서 넣기 때문에 생기는 규칙이 하나 있다. 원 배열 [2, 4, 5, 7, 9]의 인덱스 번호 [0, 1, 2, 3, 4]를 살펴보자. 마지막 만들어진 배열 [2, 5, 9, 7, 4]의 원래 인덱스 번호를 생각해보면 [0, 2, 4, 3, 1]이다. 즉, 새로 만들어진 배열은 원 배열의 짝수 인덱스 번호 순서대로 원소가 들어가고, 그 뒤 홀수 인덱스 번호가 역순으로 들어간다. 이제 이를 구현만 하면 된다.

 

 

 

풀이

---

Python

roundNum = int(input())

for i in range(roundNum):
    listNum = int(input())

    board = list(map(int, input().split()))
    board = sorted(board)

    evenList = []
    oddList = []
    for j in range(listNum):
        if j%2 == 0:
            evenList.append(j)
        else:
            oddList.insert(0, j)
    
    resultOrder = (evenList + oddList)
    resultBoard = [0 for i in range(listNum)]
    for j in range(listNum):
        resultBoard[j] = board[resultOrder[j]]

    result = 0
    for j in range(listNum):
        result = max(result, (abs(resultBoard[j%listNum] - resultBoard[(j+1)%listNum])))
    
    print(result)

 

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        int roundNum = Integer.parseInt(scan.nextLine());
        
        for(int i = 0 ; i < roundNum ; i++){
            int listNum = Integer.parseInt(scan.nextLine());

            int[] board = new int[listNum];
            String[] firstLine = (scan.nextLine()).split(" ");
            for(int j = 0 ; j < listNum ; j++){
                board[j] = Integer.parseInt(firstLine[j]);
            }

            Arrays.sort(board);

            ArrayList<Integer> evenList = new ArrayList<>();
            ArrayList<Integer> oddList = new ArrayList<>();
            for(int j = 0 ; j < listNum ; j++){
                if(j%2 == 0){
                    evenList.add(j);
                }else{
                    oddList.add(0, j);
                }
            }

            ArrayList<Integer> resultOrder = new ArrayList<>();
            resultOrder.addAll(evenList);
            resultOrder.addAll(oddList);
            int[] resultBoard = new int[listNum];
            for(int j = 0 ; j < listNum ; j++){
                resultBoard[j] = board[resultOrder.get(j)];
            }

            int result = 0;
            for(int j = 0 ; j < listNum ; j++){
                result = Math.max(result, Math.abs(resultBoard[j%listNum] - resultBoard[(j+1)%listNum]));
            }

            System.out.println(result);
        }

    }

}