목표
99클럽 스터디가 끝난후에 하루에 한개씩 꾸준히 풀고싶다는 생각이 들어서 하루에 한개씩 꾸준히 푸는게 목표이다.
문제
내가 생각했을때 문제에서 원하는부분
N개의 통나무를 원형으로 세워 놓고 뛰어 놀려고 한다.
각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.
통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다.
입력은 T개의 테스트 케이스로 이루어져 있다. 첫 줄에 T가 주어진다.
이어지는 각 줄마다 첫 줄에 통나무의 개수를 나타내는 정수 N(5 ≤ N ≤ 10,000),
둘째 줄에 각 통나무의 높이를 나타내는 정수 Li가 주어진다.
테스트 케이스마다 한 줄에 주어진 통나무들로 만들 수 있는 최소 난이도를 출력내가 이 문제를 보고 생각해본 부분
T을 정의해주고 T만큼 for문을 돌려준다.
for문 안에서 N개의 테스트 케이스를 입력받는다.
2 4 5 7 9를 입력받을때
2 5 9 7 4에서 9-5를 해서 난이도가 4가 나온다.
입력받은 배열을 가장 큰수가 중앙에오고 다음으로 큰 수가
중앙의 오른쪽, 그다음으로 큰수가 왼쪽으로 오게 만들면된다.
우선순위 큐를 활용해서 가장 큰 순서대로 정렬받은 배열을 먼저 만들어준다.
새로 정렬할 배열을 생성해준 후 왼쪽과 오른쪽 인덱스를 만들어주고
while 문으로 2개씩 poll해서 삽입해주면 된다.
그러면 배열의 순서상으론 맨 처음값과 맨 끝 값이 원래의 오름차순으로 데이터가 들어가있을건데,
이 두개를 뺀 값의 절대값을 max 변수에 대입해주고 배열을 처음부터 비교해서 더 큰 값이 나온다면 max를 바꿔주는 식으로 풀이하면 된다.코드로 구현
package baekjoon.baekjoon_18;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
// 백준 11497번 문제
public class Main648 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
PriorityQueue<Integer> queue = new PriorityQueue<>(((o1, o2) -> o2-o1));
int[] arr = new int[N];
for(int j = 0; j < N; j++) {
queue.add(Integer.valueOf(st.nextToken()));
}
arr[N/2] = queue.poll();
int left = N / 2 - 1;
int right = N / 2 + 1;
while(!queue.isEmpty()) {
if(right < N) {
arr[right++] = queue.poll();
}
if(!queue.isEmpty()) {
arr[left--] = queue.poll();
}
}
int max = Math.abs(arr[0] - arr[N-1]);
for(int j = 1; j < N; j++) {
max = Math.max(max, Math.abs(arr[j] - arr[j-1]));
}
System.out.println(max);
}
br.close();
}
}시간복잡도 O(NlogN)
장점
PriorityQueue를 사용하여 중간값을 빠르게 찾을 수 있다.
원소의 정렬이 필요없어 정렬에 걸리는 시간이 절약된다.
단점
PriorityQueue의 logN 시간이 추가적으로 소요된다.
일반적인 정렬 알고리즘(퀵정렬 등)과 비교했을 때 약간 비효율적일 수 있다.
마무리
99클럽 스터디 끝난후에 스스로 문제를 풀어봤다. 전에는 문제를 두 문제정도를 줘서 풀게했는데 나같이 아직 알고리즘에 익숙히 않는사람은 그 문제를 해석하는데 엄청난 시간을 걸렸다. 맨날 하루에 한번씩 블로그에 문제 풀이와 어떤식으로 문제를 풀었는지 과정을 작성하는게 스터디 취지였다. 하루 정도 곰곰히 생가해보면서 어떤 알고리즘의 효율적인지 어떤 알고리즘을 사용해야할지 고민해보면서 문제를 계속 생각한후에 문제가 막히면 다른사람의 풀이를 봤다. 전에 99클럽에서 클럽장이 문제를 읽었는데 계속 안풀리면 절대 안풀린다고 그럴경우에는 다른사람이 어떤식으로 문제를 풀어봤는지 어떤생각을 가지고 이 문제에 접근했는지 등을 보면서 생각해보라고 했던것같다.
Junior backend developer