[알고리즘] 백준 11497 통나무 건너뛰기 -그리디- 자바, 코틀린

 

 

 

 

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

11497번: 통나무 건너뛰기

 

 

 

백준 11497 통나무 건너뛰기 문제를 풀어봤습니다.

그리디 유형의 문제였습니다.

최소의 난이도를 가진 둥근 모양의 통나무 배치를 하기 위해서는

통나무를 양 옆으로 작은것들로 시작하여 점점 가운데로 올 수록 크게 배치하면 최소의 난이도를 만들 수 있습니다.

 

 

풀이는 다음과 같습니다.

 

[Java]

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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // 테스트 케이스 수
        for (int t = 0; t < T; t++) {
            int N = sc.nextInt(); // 통나무 개수
            int[] arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i] = sc.nextInt();
            }
            Arrays.sort(arr); // 정렬
            int left = N - 1;
            int right = 0;
            int[] nums = new int[N];
            // 왼쪽 오른쪽에 하나씩 정렬된 통나무를 놓으면 가장 작은 차이를 만들 수 있음
            for (int i = 0; i < N; i++) {
                if (i % 2 == 0) {
                    nums[left--] = arr[i];
                } else {
                    nums[right++] = arr[i];
                }
            }
            // 인접한것들끼리의 크기비교
            int answer = Integer.MIN_VALUE;
            for (int i = 1; i < N; i++) {
                answer = Math.max(answer, Math.abs(nums[i] - nums[i - 1]));
            }
            // 처음과 끝 통나무도 크기비교
            answer = Math.max(answer,Math.abs(nums[0] - nums[N - 1]));
            System.out.println(answer + " ");
        }

    }
}

 

 

[kotlin]

import java.util.*
import kotlin.math.abs

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val T = sc.nextInt() // 테스트 케이스 수
    for (t in 0 until T) {
        val N = sc.nextInt() // 통나무 개수
        val arr = IntArray(N)
        for (i in 0 until N) {
            arr[i] = sc.nextInt()
        }
        Arrays.sort(arr) // 정렬
        var left = N - 1
        var right = 0
        val nums = IntArray(N)
        // 왼쪽 오른쪽에 하나씩 정렬된 통나무를 놓으면 가장 작은 차이를 만들 수 있음
        for (i in 0 until N) {
            if (i % 2 == 0) {
                nums[left--] = arr[i]
            } else {
                nums[right++] = arr[i]
            }
        }
        // 인접한것들끼리의 크기비교
        var answer = Int.MIN_VALUE
        for (i in 1 until N) {
            answer = answer.coerceAtLeast(abs(nums[i] - nums[i - 1]))
        }
        // 처음과 끝 통나무도 크기비교
        answer = answer.coerceAtLeast(abs(nums[0] - nums[N - 1]))
        println("$answer ")
    }
}

 

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!

 

 

 

https://github.com/mtjin/algorithm_practice/commit/79d3ccc066903ee71af5d537954d05cad6680999

백준 11497 풀이 · mtjin/algorithm_practice@79d3ccc