백준 1966번 - 프린터 큐

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

---

문제분석

문제 풀이를 위한 입력을 받는 게 더 귀찮았다..;

 

테스트 케이스의 개수 n 이 주어지면

문서의 개수, 출력 순서를 확인하고자 하는 문서의 인덱스를 차례로 입력받고

프린트 하고자 하는 문서가 순서대로 입력된다. (대기열 개념)

각각의 문서는 중요도로 표시되며

대기열에 현재 문서보다 중요도가 큰 문서가 있을 경우 현재 문서를 대기열로 넣고

없을 경우는 출력한다.

이런 흐름으로 문서들을 출력하게 될 때 출력 순서를 확인하고자 하는 인덱스의 문서는 몇 번째로 출력되는지 구하면 된다.

---

풀이

초기 상태의 문서 인덱스 정보도 저장해두어야 하기 때문에

Task란 클래스를 정의하여 큐의 제네릭으로 사용하였다.

코드 가독성을 위해 따로 solution 메소드를 정의하여 사용했고, 여기서 반환되는 값들을

StringBuffer에 담아 최종적으로 toString()을 통해 출력

 

1. 큐의 요소를 출력해나가면서(poll()) 없앨 것이므로
   while문을 큐에 값이 없을 때 까지로 두고 순회

2. current 변수에 큐 값을 poll() 하여 꺼내둔다.
    3에서 다시 current가 큐에 삽입될 경우가 있기 때문에 완전히 값이 출력되는지 여부 확인을 위한 변수 size에 
    큐의 현재 크기(요소 하나가 poll() 된 상태) 담기

3. 남은 큐를 순회하며 current 보다 중요도가 큰 값이 있다면 current를 다시 큐에 넣고 종료

4. 큐 사이즈의 변동이 있을 경우(current가 완전히 출력 되었을 경우)
    출력 순서 저장용 변수 answer 값을 1 증가.
    이번에 출력된 current가 idx(출력 순서를 확인하고자 하는 인덱스) 와 일치할 경우 바로 answer을 반환

---

코드

public class Exam1966 {
    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ) {
            StringBuffer sb = new StringBuffer();
            int n = Integer.parseInt(br.readLine());

            for (int i = 0; i < n; i++) {
                String[] input = br.readLine().split(" ");
                int docCnt = Integer.parseInt(input[0]);
                int idx = Integer.parseInt(input[1]);
                Queue<Task> queue = new LinkedList<>();

                input = br.readLine().split(" ");
                for (int j = 0; j < docCnt; j++) {
                    queue.offer(new Task(j, Integer.parseInt(input[j])));
                }
                sb.append((solution(idx, queue) + "\n"));
            }
            System.out.println(sb.toString());
        } catch (IOException e) {
            System.out.println(e);
        }
    }

    public static int solution(int idx, Queue<Task> queue) {
        int answer = 0;
        while (!queue.isEmpty()) {
            Task current = queue.poll();
            int size = queue.size();
            for (Task t : queue) {
                if (current.value < t.value) {
                    queue.offer(current);
                    break;
                }
            }
            if (size == queue.size()) {
                answer++;
                if (current.idx == idx) return answer;
            }
        }
        return answer;
    }

    static class Task {
        public int idx, value;
        public Task(int idx, int value) {
            this.idx = idx;
            this.value = value;
        }
    }
}

---

댓글 피드백은 언제나 환영합니다!