[백준] 11497번: 통나무 건너뛰기 - JAVA

문제 보기

 

문제 분석

[요약]

다양한 높이의 통나무를 원형으로 세웠을 때 높이 차이가 가장 적도록 배치하기.

 

[푸는 과정]

우선 숫자의 최소 혹은 최대를 구하는 문제기 때문에 '정렬'이 필요 하겠다. 정렬이 쉽도록 배열을 선택할 것이다.
각 숫자의 차이가 가장 적도록 배치하려면 우선 가장 큰수를 중간에 배치 하고 남은 숫자들을 양 옆으로 내림차순 배치를 하면 되겠다. 

input용 배열 하나(=numbers), 통나무 정렬용 배열(=logs) 하나로 총 두 개의 배열을 사용 할 것이다.

이제 나란히 놓인 두 숫자의 차 중 가장 큰 차를 구해야 한다. 혹시 모를 시간초과 방지를 위해 통나무를 정렬하면서 Math.max()함수를 이용해 두 수의 최대 차를 구할 것이다.

 

 

코드 보기

import java.io.*;
import java.util.*;

public class Greedy11497 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for(int r=0; r<N; r++){
        	//input 입력
            int inputTotal = Integer.parseInt(br.readLine());
            String[] numbersString = br.readLine().split(" ");
            int[] numbers = new int[inputTotal];
            for(int i=0; i<numbers.length; i++){
            	//input으로부터 numbers배열 생성
                numbers[i] = Integer.parseInt(numbersString[i]);
            }
            Arrays.sort(numbers); //numbers 오름차순 정렬

            int maxDiff = 0; //두 수의 최대 차
            
            int[] logs = new int[inputTotal]; //log=통나무
            int left = 0;
            int right = numbers.length - 1;

            for(int i=0; i<numbers.length; i++){
            	//배열의 양옆 끝자리 --> 배열의 가운데 방향으로
                //가장 작은 수부터 입력
                
                //배열의 왼쪽끝부터 오른쪽으로
                if(i % 2 == 0){
                    logs[left] = numbers[i];
                    if(i > 0){
                        maxDiff = Math.max(Math.abs(logs[left] - logs[left-1]), maxDiff);
                    }
                    left++;
                } else{ //배열의 오른쪽부터 왼쪽으로
                    logs[right] = numbers[i];
                    if(i > 1){
                        maxDiff = Math.max(Math.abs(logs[right+1] - logs[right]), maxDiff);
                    }
                    right--;
                }
            }
            maxDiff = Math.max(Math.abs(logs[logs.length-1] - logs[0]), maxDiff);
            System.out.println(maxDiff);
        }
    }
}

 

트러블 슈팅

상단의 코드로 정답을 맞히기 전에 두 번을 틀렸었다. 예제의 테스트 케이스를 통과했지만 특정 테스트 케이스에서 실패를 하는 것이다. 어디서 로직이 틀린걸까? 갑자기 마이너스 값이 떠오른다. 그럼 확인을 해 봐야지.

 

if(i > 0){
	maxDiff = Math.max(logs[left] - logs[left-1], maxDiff);
}

해당 부분을

 

if(i > 0){
	maxDiff = Math.max(Math.abs(logs[left] - logs[left-1]), maxDiff);
}

Math.abs()함수를 사용 해 절대값으로 바꾸어 주었더니 맞았다.