안녕하세요
인포돈 입니다.
백준 알고리즘 1966번 풀이입니다.
* 참고사항
- 개발환경은 eclipse을 기준으로 작성되었습니다.
- java언어를 이용하여 문제를 풀이합니다.
- 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
- 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.
백준 1966 (프린터 큐)
문제
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치한다.. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.
입력
첫 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다.
테스트 케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.
출력
각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.
입력 예제
3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1출력 예제
1
2
5성공 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
static int tc;
static int N, M;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
tc = Integer.parseInt(br.readLine());
for(int i = 0 ; i < tc ; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
StringTokenizer str = new StringTokenizer(br.readLine());
LinkedList<int[]> q = new LinkedList<>();
for(int j = 0;str.hasMoreTokens() ; j++) {
q.add(new int[] {j,Integer.parseInt(str.nextToken())});
}
int count = 0;
while(!q.isEmpty()) {
int[] temp = q.poll();
boolean check = true;
//자기보다 큰 값이 있다면 뒤로 넘겨라
for(int j = 0 ; j < q.size() ; j++) {
if(temp[1] < q.get(j)[1]) {
q.add(temp);
for(int k = 0 ; k < j ; k++)
q.add(q.poll());
check = false;
break;
}
}
//만약에 front가 가장 큰 값이 아니라면 다시 반복해라
if(check == false)
continue;
//만약 최고값이라면 poll했으니 count를 세줘라
count++;
//만약 그값이 우리가 원하는 답이라면 이만 멈추고 저장하자.
if(temp[0] == M)
break;
}
sb.append(count).append("\n");
}
System.out.println(sb);
}
}프리터 큐 알고리즘에서는 고민해야 될 점이 한 가지 있습니다. 어떠한 방식으로 중요도를 판별할 것인가? 딱 이것만 기억하시면 쉽게 푸실 수 있는 문제입니다. 그 핵심은 STEP2로!!!
알고리즘 흐름도
입력받기 -> q초기화 하기 -> q 첫 번째 값 저장하기 -> 나머지 값들 비교하기 -> 자신보다 크면 뒤로 넘기기 -> 맨 앞이 가자 큰 중요도일 시 count 하기 -> 출력하기
STEP1q초기화 하기
뭐 일단 받은 입력으로 q를 초기화해줍니다. 순서와 중요도를 기억할 수 있게 1차원 배열로 선언해 줍니다. 물론 크기는 2고요
LinkedList<int[]> q = new LinkedList<>();
for(int j = 0;str.hasMoreTokens() ; j++) {
q.add(new int[] {j,Integer.parseInt(str.nextToken())});
}이런 식으로 제네릭을 사용해 int배열을 저장해 줍니다. 들어온 순서대로 중요도를 측정합니다.
STEP2 어떠한 방법으로 구현할지 생각하기
이제 바로 이문제의 핵심인 어떻게 중요도를 판별할 것인지입니다. 뭐 저 같은 경우에는 2가지 경우가 떠올랐습니다. 중요도 순으로 정렬하기 // q를 탐색하여 가장 큰 중요도 찾아내기입니다. 뭐 다른 방법이 있을 수 있겠지만, 현재 제게 떠오른 방법은 2가지였습니다.
그러나 전자의 방법은 이용할 수가 없죠... 바로 큐를 활용해야 하기 때문이죠. 따라서 저는 후자의 방법으로 해결해보기로 생각했습니다. 기본적으로 저희는 큐를 LinkedList로 선언하였으니 인덱스로 찾아갈 수 있습니다.
이에 따라서 저희는 큐에서 하나의 값을 꺼내거나 가져옵니다. (poll 또는 get을 통해서 가져올 수 있겠죠?)
그 후 이제 반복문과 get을 통해서 큐를 쭉 탐색해 줍니다. 만약 큐에서 하나의 값을 꺼내온 값보다 중요도가 큰 값이 있다면?
지금까지 찾았던 앞의 값들을 모두 차례대로 뒤로 넘겨줘야 합니다!
이러한 반복을 끊임없이 한다면 결국 마지막에는 큐 맨 앞에 가장 큰 중요도가 오게 되겠죠.
역시 말로 하니 잘 이해가 가시지 않을 겁니다. 다음 STEP을 따라서 확실히 이해해보죠
STEP 3 q 구현하기
간단히 해봅시다. 일단은 가장 큰 틀을 생각해야 합니다. 언제까지 반복해야 하나?
바로 큐가 빌 때까지죠 (가장 마지막 값을 원할 때가 있으니깐요)
while(!q.isEmpty()) {
}그다음이 앞서 말했듯이 큐에서 가장 앞의 값을 꺼내옵니다.
while(!q.isEmpty()) {
int[] temp = q.poll();
}
이제 바로 핵심인 탐색을 시작해 봅니다.
while(!q.isEmpty()) {
int[] temp = q.poll();
boolean check = true;
//자기보다 큰 값이 있다면 뒤로 넘겨라
for(int j = 0 ; j < q.size() ; j++) {
if(temp[1] < q.get(j)[1]) {
}
}
}어렵지 않습니다. q의 크기만큼을 반복해 주면서 해당 값을 get으로 알아낸 뒤 저희가 끄내 온 temp의 중요도와 비교해 줍니다.!!
여기서 if에 걸리게 된다면, 저희가 해야 될 것은 이제까지 넘겨왔던 값들을 모두 차례로 다시 q뒤쪽으로 넘겨줘야 합니다.
while(!q.isEmpty()) {
int[] temp = q.poll();
boolean check = true;
//자기보다 큰 값이 있다면 뒤로 넘겨라
for(int j = 0 ; j < q.size() ; j++) {
if(temp[1] < q.get(j)[1]) {
q.add(temp);
for(int k = 0 ; k < j ; k++)
q.add(q.poll());
}
}
}자 간단하죠??
여기서 한 가지 고려해야 될 것이 바로 temp을 변경해야 된다는 점입니다. 왜냐하면 저희가 처음에 판단한 값은 가장 먼저 가저온 값인데 그 값과 계속해서 비교하며 안되기 때문이죠.
1 6 1 9 7 1 6
이런 식으로 들어있다면 9를 만나는 순간 다 뒤로 가겠죠?
9 7 1 6 1 6 1
이때 j는 4를 가리키게 되며 temp에는 1이 들어있죠? 그렇게 되면 가장 큰 수인 9도 뒤로 가게 되죠
때문에 break를 통해 이를 방지해 줍니다.
while(!q.isEmpty()) {
int[] temp = q.poll();
//자기보다 큰 값이 있다면 뒤로 넘겨라
for(int j = 0 ; j < q.size() ; j++) {
if(temp[1] < q.get(j)[1]) {
q.add(temp);
for(int k = 0 ; k < j ; k++)
q.add(q.poll());
break;
}
}
}이제 큐의 맨 앞의 값이 가장 큰 값인지 판별해 줘야 합니다. 앞선 예시처럼
1 6 1 9 7 1 6이라면 현재의 식으로 대입해보면
6 1 9 7 1 6 1 이 되어 for문을 빠져나오게 되죠 그러나 6이 가장 큰 수가 아니겠죠?
그러면 가장 큰 수가 되려면 어떻게 해야 할까요?
바로 boolean flag를 활용해야 합니다. 하나의 변수를 통해서 이를 가볍게 해결
만약에 for문안의 if문이 실행되었다면, temp변수에 들어있는 값보다 큐에 들어있는 값 중어 어느 한 값이 더 큰 중요도를 가졌단 뜻이 되므로, 이를 방지해주면 끝
while(!q.isEmpty()) {
int[] temp = q.poll();
boolean check = true;
//자기보다 큰 값이 있다면 뒤로 넘겨라
for(int j = 0 ; j < q.size() ; j++) {
if(temp[1] < q.get(j)[1]) {
q.add(temp);
for(int k = 0 ; k < j ; k++)
q.add(q.poll());
check = false;
break;
}
}
}이런 식으로 check로 이러한 상황을 고려해 줍니다.
마지막으로 그냥 이러한 상황들을 걸러주면 끝
while(!q.isEmpty()) {
int[] temp = q.poll();
boolean check = true;
//자기보다 큰 값이 있다면 뒤로 넘겨라
for(int j = 0 ; j < q.size() ; j++) {
if(temp[1] < q.get(j)[1]) {
q.add(temp);
for(int k = 0 ; k < j ; k++)
q.add(q.poll());
check = false;
break;
}
}
//만약에 front가 가장 큰 값이 아니라면 다시 반복해라
if(check == false)
continue;
//만약 최고값이라면 poll했으니 count를 세줘라
count++;
//만약 그값이 우리가 원하는 답이라면 이만 멈추고 저장하자.
if(temp[0] == M)
break;
}continue를 통해 다시 한번 poll을 진행하여 다시 반복 아니라면 count를 증가시켜 주고 우리가 원하던 순서의 값이라면 break 아니라면 다시 while문이 반복되면서 다음 큐 순서로 간다.
이번 알고리즘의 핵심은 어디까지나 어떤 방법으로 우선순위를 표현해야 될까입니다. 저 같은 경우 정렬/ 탐색을 떠올렸지만, 아무런 아이디어가 떠오르지 않으셨을 수도 있습니다. 저도 처음에 그랬었으니까요. 그렇다면 과감히 다른 풀이들을 이해하고 따라 하는 것부터 시작하셔도 좋습니다. 그런 식으로 하나씩 해결하다 보면, 어느샌가 다른 문제를 풀이할 때 아이디어가 번뜩일 겁니다.
'알고리즘 > 백준알고리즘' 카테고리의 다른 글
| [백준알고리즘-JAVA]5430번 풀이(AC) - 초보도 이해하는 풀이 (0) | 2021.09.15 |
|---|---|
| [백준알고리즘-JAVA]1021번 풀이(회전하는 큐) - 초보도 이해하는 풀이 (0) | 2021.09.14 |
| [백준알고리즘-JAVA]11866번 풀이(요세푸스 문제) - 초보도 이해하는 풀이 (0) | 2021.09.12 |
| [백준알고리즘-JAVA]18258번 풀이(큐2) - 초보도 이해하는 풀이 (0) | 2021.09.10 |
| [백준알고리즘-JAVA]1931번 풀이(회의실 배정) - 초보도 이해하는 풀이 (0) | 2021.09.09 |
