백준-프린터-큐

구해야 하는 것
주어진 자료
조건
계획
실행
반성

프린터 큐

구해야 하는 것

M 번째 문서가 몇 번째로 출력되는지

주어진 자료

문서의 개수 = N
몇 번째로 인쇄 됐는지 궁금한 문서가 큐의 몇 번째에 있는지 나타내는 정수 = M
입력
- 첫 줄: 테스트 케이스 개수
- 테스트 케이스 첫 줄: N, M
- 테스트 케이스 두 번째 줄: N개 문서의 중요도

조건

인쇄 조건
- 현재 큐의 가장 앞에 있는 문서의 중요도를 확인
- 나머지 문서들 중 현재 문서보다 중요도 높은 문서가 하나라도 있으면 큐 맨 뒤에 재배치.
- 그렇지 않다면 바로 인쇄
1 <= N <= 100
0 <= M < N
1 <= 중요도 <= 9
중요도 중복 가능

계획

입력으로 주어진 중요도를 순서대로 큐에 넣는다. 이때 M번째 문서에는 별도의 표시를 해둔다.
맨 앞의 문서보다 중요도가 높은 문서가 있는지 찾는다.
- 있으면 해당 문서의 인덱스를 구한 후 인덱스 전까지의 문서들을 뒤로 다시 넣어준다.
- 없으면 맨 앞의 문서를 제거한 후 answer를 증가시킨다.
M번째 문서를 제거할 때까지 반복한다.
M번째 문서를 제거했으면 answer를 return 한다.

실행

class Doc {
    int importance;
    boolean isM;
}

public class Main {
    // 중요도가 더 큰 문서의 인덱스 반환
    public int getBiggerIdx(Queue<Doc> queue) {
        Queue<Doc> q = new LinkedList<>(queue);
        
        Doc front = q.poll(); // 맨 앞 문서
        int idx = 1; // 1번째 문서부터 비교할거임
        
        while(!q.isEmpty()) {
            Doc cur = q.poll();

            if(front.importance < cur.importance) { // 중요도가 더 큰 문서가 있는 경우
                return idx;
            }
            else {
                idx++;
            }
        }
        return -1; // 뒤에 중요도가 더 큰 문서가 없었으면 -1 반환
    }

    // 중요도가 더 큰 문서의 앞에 있는 문서들을 뒤로 다시 넣어줌
    public void addBack(Queue<Doc> queue, int biggerIdx) {
        int curIdx = 0;
        
        while(curIdx != biggerIdx) {
            queue.add(queue.poll()); // 맨 앞 문서를 빼서 뒤로 넣어줌
            curIdx++;
        }
    }
    
    // M 번째 문서가 몇 번째에 출력됐는지 반환
    public int printTask(Queue<Doc> queue) {
        int cnt = 0;
        
        while(true) {
            Doc front = queue.peek();
            int biggerIdx = getBiggerIdx(queue);
            
            if(front.isM) { // 맨 앞 문서가 M 번째 문서인 경우
                if(biggerIdx == -1) { // 뒤에 중요도 더 큰 문서가 없으면
                    cnt++; // 현재 문서까지 출력 횟수에 반영해야 하므로 증가
                    return cnt; // 출력 횟수 반환
                } else {
                    addBack(queue, biggerIdx); // biggerIdx 전까지의 문서들을 뒤에 다시 넣어줌
                }
            } else {
                if(biggerIdx == -1) { // 뒤에 중요도 더 큰 문서가 없으면
                    queue.remove(); // 맨 앞 문서 출력
                    cnt++; // 출력 횟수 증가
                } else {
                    addBack(queue, biggerIdx);
                }
            }
        }
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int testCase = Integer.parseInt(br.readLine()); // 테스트 케이스 개수 입력

        for(int i = 0; i < testCase; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken()); // n 입력
            int m = Integer.parseInt(st.nextToken()); // m 입력

            Queue<Doc> queue = new LinkedList<>();
            st = new StringTokenizer(br.readLine());

            // 중요도 입력받고 큐에 넣기
            for(int j = 0; j < n; j++) {
                Doc inputDoc = new Doc();
                inputDoc.importance = Integer.parseInt(st.nextToken()); // 중요도 입력
                
                if(j == m) { // m번째 문서이면
                    inputDoc.isM = true;
                } else {
                    inputDoc.isM = false;
                }
                queue.add(inputDoc);
            }

            System.out.println(printTask(queue)); // 답 출력
        }
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

반성

문제에 주어진 입력 예제를 그대로 복붙했음에도 StringTokenizer가 마지막 줄을 가져오지 못했다. 엔터를 한 번 더 쳐주면 그제서야 마지막 줄이 바르게 입력됐다. 그래서 이걸 해결하는 데에만 엄청 삽질을 했다.
알고 보니 마지막 줄에 개행이 없기 때문에 StringTokenizer가 입력으로 인식을 하지 못했던 것이었고, 내가 직접 마지막 줄 이후에 개행을 해주니까 바르게 작동했다.
속도를 위해 Scanner 사용은 지양해야 하므로 BufferedReader와 StringTokenizer의 작동 방식에 대해 잘 알고 있어야겠다.
getBiggerIdx() 메서드같은 경우에는 원본 큐에 영향을 주지 않아야 한다는 생각에,
```
public int getBiggerIdx(Queue<Doc> queue) {
  Queue<Doc> q = new LinkedList<>();
  q = queue;
  ...
}
```
이렇게 메서드 내에서 큐 객체를 새로 만든 후 매개변수를 대입해줬었다. 그런데 디버깅을 해보니까 q와 queue의 주소값이 같았다.
자바에서는 배열 객체를 매개변수로 넘겨주면 그 주소값을 그대로 넘기기 때문에 q = queue 이렇게 하면 값이 아니라 주소값을 대입한 것이 된다. 새로운 객체에 값만 복사하고 싶으면 Queue<Doc> q = new LinkedList<>(queue); 이렇게 써줘야 한다는 것을 깨달았다.
그동안 자바 언어에 대한 공부를 너무 놓고 있었던 것 같다. 기초를 다시 다져야 할 것 같다.