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

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

300x250

SMALL

https://www.acmicpc.net/problem/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) { 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

300x250

LIST

from http://youngest-programming.tistory.com/650 by ccl(S) rewrite - 2021-12-03 06:28:19