문제 설명
문제 링크는 여기.
큐에 순서대로 담겨져있는 요소를 출력한다.
이때 요소는 우선순위를 갖고 있으며, 자신보다 우선순위가 높은 요소가 큐에 있는 경우 이를 우선 출력한다.
요소의 초기 위치 값을 주었을 때, 해당 요소의 출력 순서를 반환하면 된다.
접근
처음에는 문제를 잘못 이해해서 입력 순서대로 큐에 삽입하다가, 현재 상단 큐에 있는 것보다 우선순위 높은게 들어오면 먼저 출력하는 식으로 구현했다.
int result = 1;
char[] arr = br.readLine().replaceAll(" ", "").toCharArray();
// 입력을 큐에 삽입
for(int i=0; i<N; i++) {
// 큐가 비어있거나, 큐의 최상단 요소보다 우선순위 높은 경우 삽입
if(queue.isEmpty() || queue.peek()[1]>arr[i]-'0') {
queue.add(new int[] {i, arr[i]-'0'});
}
// 아니면 우선 출력, 이때 원하는 요소였을 경우 나가서 result 출력
else {
if(i==M) break;
result++;
}
}
// ? 이거 왜 이렇게 짰을까...?
while(queue.isEmpty()) {
if(queue.poll()[0]==M) break;
result++;
}
bw.append(result+"\n");지금보니까 그 로직도 틀렸다… 하지만 의도대로 동작 했다고 해도 이 접근은 잘못되었다. 전체에서 가장 우선순위가 높은 요소부터 순서대로 출력해야하는데 현재 큐보다 우선순위가 높으면 바로 출력되기 때문이다.
틀리는 예시는 다음과 같다.
1 2 3 4
// 출력 순서 : 2 3 4 1
이후 아주 단순히 뒤의 대기열 중에 자신보다 큰 수가 있으면 그 수가 앞으로 나올때까지 pop + add 반복하여 출력하는 방식으로 코드를 고쳤다.
String[] input = br.readLine().split(" ");
int N = Integer.parseInt(input[0]);
int M = Integer.parseInt(input[1]);
int result = 1;
char[] arr = br.readLine().replaceAll(" ", "").toCharArray();
// 일단 큐에 다 넣기
for(int i=0; i<N; i++) {
queue.add(new int[] {i, arr[i]-'0'});
}
// 큐가 빌 때까지 반복
while(!queue.isEmpty()) {
// 우선순위 가장 높은 것 탐색
int max = queue.peek()[1];
for(int[] temp : queue) {
max = Math.max(max, temp[1]);
}
// 가장 높은 것을 최상단으로 만들기
while(queue.peek()[1]!=max)
queue.add(queue.poll());
// 출력 후 찾던 원소면 반복 나가기
if(queue.poll()[0]==M) break;
result++;
}
queue.clear();
bw.append(result+"\n");소스코드
최종 소스코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Queue<int[]> queue = new LinkedList<>();
int T = Integer.parseInt(br.readLine());
for(int t=1; t<=T; t++) {
String[] input = br.readLine().split(" ");
int N = Integer.parseInt(input[0]);
int M = Integer.parseInt(input[1]);
int result = 1;
char[] arr = br.readLine().replaceAll(" ", "").toCharArray();
for(int i=0; i<N; i++) {
queue.add(new int[] {i, arr[i]-'0'});
}
while(!queue.isEmpty()) {
int max = queue.peek()[1];
for(int[] temp : queue) {
max = Math.max(max, temp[1]);
}
while(queue.peek()[1]!=max)
queue.add(queue.poll());
if(queue.poll()[0]==M) break;
result++;
}
queue.clear();
bw.append(result+"\n");
}
bw.flush();
}
}결과
제출 결과는 다음과 같다.
상단의 두 제출은 같은 코드이다.(Java11과 Java8의 차이를 보고 싶었음)
고찰
중간에 최고 우선순위 요소 찾는 과정 대신 정렬된 배열을 이용해도 될것 같다. 가령 이렇게?
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Queue<int[]> queue = new LinkedList<>();
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
String[] input = br.readLine().split(" ");
int N = Integer.parseInt(input[0]);
int M = Integer.parseInt(input[1]);
int result = 1;
char[] arr = br.readLine().replaceAll(" ", "").toCharArray();
for (int i = 0; i < N; i++) {
queue.add(new int[] { i, arr[i] - '0' });
}
//배열 정렬하여 사용
Arrays.sort(arr);
int max = arr.length - 1;
while (!queue.isEmpty()) {
while (queue.peek()[1] != arr[max] - '0') {
queue.add(queue.poll());
}
max--;
if (queue.poll()[0] == M) {
break;
}
result++;
}
queue.clear();
bw.append(result + "\n");
}
bw.flush();
}
}결과는 다음과 같았다.
시간복잡도는 유의미하게 달라지지는 않았다.
오엥