문제
즐거운 컴퓨터 프로그래밍 시간! 이번 시간의 수업 내용은 정렬이었다. 학생들은 오름차순 또는 내림차순으로 입력받은 값을 정렬해보기 시작하였다. 수업이 끝나갈 무렵, 오늘도 어김없이 조교의 과제가 주어졌다. 과제 이름은 정렬 게임. 과제 내용은 다음과 같다. 처음에 임의의 수열이 있고, 처음 위치부터 지정된 위치까지 오름차순, 내림차순, 오름차순, 내림차순, ... 의 순서를 반복하여 정렬하였을 때, 어떠한 수가 나타나는지 출력하는 프로그램을 작성하는 것이었다.
예를 들어, 과제로 주어진 수열이 [4,1,2,3] 이고, 처음 위치부터 3번째 원소까지 오름차순, 그 다음 2번째 원소까지 내림차순으로 정렬한 결과를 출력하라고 할 경우를 보자. 처음 오름차순 정렬을 수행하면 [1,2,4,3] 이 되고, 여기서 2번째 원소까지 내림차순으로 정렬하면 [2,1,4,3] 이 된다. 그리고 이것이 최종 정답이 된다. 정렬 게임에서 오름차순, 내림차순을 1번씩 하는 것을 한 세트를 진행했다고 정의한다. 수열과 K개의 세트가 주어질 때, 최종 수열을 출력하는 프로그램을 작성하시오.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 수열의 개수 N이 주어진다. (1 ≤ N ≤ 100,000)
입력의 두 번째 줄에는 N개의 수열의 원소가 공백으로 구분되어 주어진다. 수열의 원소는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.
입력의 세 번째 줄에는 세트의 개수 K가 주어진다. (1 ≤ K ≤ 100,000)
입력의 네 번째 줄부터 한 줄에 한 개씩 오름차순, 내림차순을 하는 구간을 뜻하는 두 수 A, B가 주어진다. 이는 1번째 원소부터 A번째 원소까지 오름차순 정렬을 한 후, 1번째 원소부터 B번째 원소까지 내림차순 정렬을 해야함을 의미한다.
출력
출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, K개의 세트를 모두 진행하고 난 뒤 수열의 모든 원소를 출력한다.
예제 입력
4
4 1 2 3
1
3 2예제 출력
2 1 4 3코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
int[] sorted_arr = new int[N];
Deque<Integer> set = new ArrayDeque<>();
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
sorted_arr[i] = arr[i];
}
int K = Integer.parseInt(br.readLine());
int sort_max = 0; // 어디까지 정렬할 건지
for (int i = 0; i < K; i++) {
String str = br.readLine();
int A = Integer.parseInt(str.split(" ")[0]);
int B = Integer.parseInt(str.split(" ")[1]);
sort_max = Math.max(sort_max, Math.max(A, B));
while ((!set.isEmpty()) && (Math.abs(set.getLast()) <= A)) {
set.pollLast();
}
set.addLast(A);
while ((!set.isEmpty()) && (Math.abs(set.getLast()) <= B)) {
set.pollLast();
}
set.addLast(-B);
}
set.addLast(0); // 마지막 연산 위해
Arrays.sort(arr, 0, sort_max); // arr 정렬하기
int final_idx = sort_max - 1;
int ascend_idx = sort_max - 1;
int descend_idx = 0;
int cur = set.pollFirst();
while (!set.isEmpty()) {
int next = set.pollFirst();
int diff = Math.abs(cur) - Math.abs(next);
if (cur > 0) { // 오름차순
for (int i = 0; i < diff; i++) {
sorted_arr[final_idx--] = arr[ascend_idx--];
}
} else { // 내림차순
for (int i = 0; i < diff; i++) {
sorted_arr[final_idx--] = arr[descend_idx++];
}
}
cur = next;
}
for (int i = 0; i < sorted_arr.length; i++) {
bw.write(sorted_arr[i] + " ");
}
br.close();
bw.flush();
bw.close();
}
}정리
알고리즘
1. A, B를 입력받을 때 어디까지 정렬하면 될지 sort_max를 설정한다.
2. A, B와 Deque의 마지막 값을 비교하여 마지막 값보다 크다면 계속 pollLast를 해준다. (값이 같아도)
3. Deque의 마지막에 넣어준다(addLast).
4. arr를 sort_max까지 정렬한다.
5. ascend_idx는 정렬한 arr의 뒤에서부터,
descend_idx는 정렬한 arr의 앞에서부터,
final_idx는 sorted_arr(결과 배열)의 뒤에서부터 시작한다.
6. Deque이 빌 때까지 pollFirst를 하여 두 값의 차이만큼 sorted_arr에 arr 값을 복사한다.필요 없는 정렬을 제거하는 것이 핵심이었다.
Deque을 사용해야 한다는 점을 알아차리는 것이 어려웠다.
처음으로 골드 2 문제를 풀어봤는데 역시 만만치 않다.. 🥲
참고 링크
