백준 1966번
https://www.acmicpc.net/problem/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 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.
생각하기
Queue자료구조를 이해하는데 가장 기본적인 문제 였으므로, 너무 좋은 문제라고 생각했다
솔직히 어려운 문제도 아님, 근데 나는 뒤지게 어려웠음;;
문제를 처음에 읽고 나서 우선순위가 높은 거 부터 출력한다고 생각하고 바로 떠오른게
Deque(덱)이었다. 문제에서 Queue를 사용하라는 팁도 줬다.
코드를 한번 따져보면 Deque에서 현재 가장 높은 우선순위 max를 찾고 max와 일치 하지 않는 값들은 우선순위가 낮기 때문에 출력 될 수 없기 때문에 Deque.pop()후 바로 다시 Deque.addLast() 로 가장 뒤로 다시 삽입한다.
이 과정을 계속 해서 반복하다가 max와 일치하는 중요도의 문서가 나오게 되면, 해당 문서는 Deque.pop()을 해서 Deque에서 바로 삭제하고, 이후 몇 번째로 출력되는지 답을 찾아야 하기 때문에 삭제 될 때만 turn을 증가시켜 순서를 계산한다. 그리고 Deque사이즈를 수정해야 하기 때문에 size = size - 1로 값을 수정해준다. 또한, 내가 찾는 문서의 index 값을 계속 파악하면서 계산한다.
마지막에 찾는 문서의 중요도와 현재 Deque에서 가장 높은 우선순위가 같아 졌을 때, 찾는 문서의 index 까지만 for문을 통해 반복해서 Deque.pop()을 실행해서 같은 중요도의 문서가 나올 때만 turn을 증가시켜 마지막turn값이 최종 결과 값이 된다.
결국, 내가 원하는 문서의 위치index와 문서가 빠져나간 수turn의 계산이 핵심이었다.
TMI
진짜 어려운 문제는 아니라는 생각이 들었는데, 첫 번째 완성한 코드로 Testcase 값이 정답이 나와서 제출했는데 틀렸다고 나왔을 때 1차 멘붕
Testcase로 돌려서 정답이었는데, 틀렸다고 나올 때 나의 심정
다른 Testcase를 찾고 돌려서 오답이 나온걸 보고 수정하는 과정에서
60개의 문서를 일일이 손으로 썼다.. 2차 멘붕
이 짓을 반복하고 나서야 뭐가 문제인지 인지함.
그 다음, 머리로는 이해를 했지만 내 손은 그렇지 못했다
(사실 머리도 이해못한게 아닐까)
결국 하나씩 돌려보면서 이해하고 코딩하는 방법을 선택..
진짜 별것 도 아닌거에 하루 이상의 시간을 투자한 끝에 풀기는 했지만 속이 후련하지 않다..
겨우 Queue 문제 하나에 박살이 나버린 나였다.. (아직 갈 길이 멀다 포기만 하지말자)
코드
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; int i, j; int loop = Integer.parseInt(br.readLine()); Deque<Integer> deque = new LinkedList<>(); for(i=0; i<loop; i++) { st = new StringTokenizer(br.readLine()); // 문서의 갯수 int paper = Integer.parseInt(st.nextToken()); // 찾는 문서의 위치 0부터 시작 int important = Integer.parseInt(st.nextToken()); // 찾는 문서의 중요도. int find_paper= 0; st = new StringTokenizer(br.readLine()); // 처음 덱 생성 for(j=0; j<paper; j++) { int temp = Integer.parseInt(st.nextToken()); if(j == important) { find_paper = temp; } deque.add(temp); } // 찾는 문서의 위치(index) int index = important; // 현재 가장 높은 우선순위. int max = Collections.max(deque); // 덱사이즈. 인덱스를 활용하기 위해(0기준) -1 을 해줌. int size = deque.size() - 1; // 덱에서 꺼낸 값이 최대 중요도 인지 확인함 // 아닐 경우 앞의 값을 덱 가장 뒤로 넘기면서 앞으로 하나씩 당겨서 최고 우선순위를 가져옴. while(deque.peek() != max) { deque.addLast(deque.pop()); // 인덱스 값이 0일 경우 즉 가장 앞일 때, if(index <= 0) { index = size; } else { index --; } } int turn = 0; for(;;) { // 찾는 문서의 중요도와 현재 차례의 문서 중요도가 같을 경우 if(max == find_paper) { int temp = 0; for(int k=0; k<=index; k++) { temp = deque.pop(); // 찾는 문서의 중요도는 일치 했고 현재 문서가 위치한 인덱스 만큼 pop() 하고 // 앞에 있는 우선 순위 먼저 turn 함 // 첫번째로 출력 할 경우 1이 출력됨 if(temp == find_paper) { turn ++; } } System.out.println(turn); break; } // 찾는 문서의 중요도와 현재 차례의 문서 중요도가 불일치 할 경우 else if(max != find_paper) { // 최고 우선순위가 가장 앞에 있는 상황에서 찾는 문서와 일치하지 않는 경우 덱에서 삭제. // 삭제 후 인덱스 감소, 사이즈 다시 계산, 문서 빠져나가는 turn 증가 deque.pop(); index --; turn ++; size --; max = Collections.max(deque); // 최고 우선 순위문서가 나올 때 까지 회전 while(deque.peek() != max) { // 앞에 있는 값을 뒤로 넘김 deque.addLast(deque.pop()); if(index <= 0) { index = size; } else { index --; } } } } // for(;;) End deque.clear(); } // for(i) End } // main End } // Class End
