💡 문제
![](https://velog.velcdn.com/images/longbright_choi/post/12bd5664-6952-4d0f-9f35-4918d3b8437b/image.png)
![](https://velog.velcdn.com/images/longbright_choi/post/ce3fb7e8-ede2-499f-8f7a-2d8f22a215e4/image.png)
💬 입출력 예시
![](https://velog.velcdn.com/images/longbright_choi/post/4d7d44bc-ca84-4c00-8fb4-44b66438b80e/image.png)
📌 풀이(소스코드)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
int T = Integer.parseInt(br.readLine());
while (T-- > 0) {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
Queue<Document> q = new LinkedList<>();
int cnt = 0;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
q.offer(new Document(i, Integer.parseInt(st.nextToken())));
}
while (!q.isEmpty()) {
Document now = q.poll();
int size = q.size();
boolean isFirst = true;
for (int i = 0; i < size; i++) {
if (q.peek().priority > now.priority) {
isFirst = false;
}
q.offer(q.poll());
}
if (isFirst) {
cnt++;
if (now.idx == M) {
sb.append(cnt).append("\n");
break;
}
} else {
q.offer(now);
}
}
}
System.out.println(sb);
}
static class Document {
int idx;
int priority;
public Document(int idx, int priority) {
this.idx = idx;
this.priority = priority;
}
}
}
📄 해설
접근
- 문제에서 주어진 설명 대로 따라가면 되는 문제이다. 큐를 사용해야하고, 필자처럼 클래스를 만들어서 사용해도 되는데, 싫으면 그냥 길이가 2인 정수배열을 사용해도 무방하다. 아마 이 경우가 메모리나 속도 측면에서 더 빠를 것이다.
- 문제에서 주어진 설명은 다음과 같다.
- 현재 큐의 맨 앞의 문서의 중요도를 확인한다.
- 현재 문서보다 중요도가 높은 문서가 있다면, 이 문서를 뒤로 보내고, 그렇지 않다면 인쇄를 한다.
- 1 과 2 의 과정을 통해
M
번째에 해당하는 문서가 몇번째로 인쇄되는지를 구하는 문제이다.
과정
- 테스트 케이스
T
를 입력 받고, 아래의 과정들을 반복한다.
N
과 M
을 입력 받는다. 각각 문서의 개수, 몇번째로 인쇄되는지 알고 싶은 문서의 번호이다.
N
개의 문서의 중요도를 입력 받으면서 몇번째 문서인지와 중요도를 클래스에 담고 큐에 넣는다.
- 큐가 빌 때까지 다음 과정을 반복한다.
- 큐에서 원소 하나를 빼서
now
에 담고, 남은 원소들을 반복문을 통해 확인한다.
- 큐에서 꺼낸 문서보다 중요도가 높은 문서를 발견한다면,
isFirst
변수를 false
로 바꾼다. 그렇지 않다면 현재 큐의 맨앞에 있는 문서를 뒤로 보낸다. (지금 확인 중인 문서의 다음 문서이다.)
- 탐색이 끝난 후,
isFirst
변수가 true
인 경우, 현재 문서의 중요도가 가장 높은 것이므로, cnt
값을 증가시키고, 현재 문서의 번호가 M
과 같은 값인지 확인한다.
- 같은 값이면 반복을 종료하고 출력한다.
isFirst
변수의 값이 false
로 유지되고 있다면, 현재 문서를 다시 큐에 넣고 반복한다.