[022] 1966. 프린터 큐

 

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

1966번: 프린터 큐

---

 

문제 풀이

1. 앞에 있는 순서대로 배열에 넣는다

2. 배열에 넣고 순서대로 비교하여, 현재 제일 앞의 순서와 나머지를 비교한다.

3. 나머지를 비교해서 현재 수가 제일 크다면 출력, 그렇지 않다면 제일 뒤로 이동시킨다.

4. 처음 m이 현재 어느 순서에 있는지를 출력한다

 

 

오답풀이

단순한 큐 호출 문제인데 이걸 틀린 이유는... 덱을 고집했기 때문이다 

덱은 map 형식을 지원하지 않기 때문에 순회를 할 때 계속해서 문제가 생긴다. 

처음에 어느 방식으로 풀었냐면, 원하는 지점을 먼저 찍어놓고, 덱에 놓은 후 검증하는 과정에서 문제가 생기면 그 위치를 다시 새로운 지점으로 지정한다. 그 지점의 차례가 되면 반복하는 형태.

근데 이 방식은 불안정하다. 올바르게 업데이트되지 않는 경우의 수가 계속 생긴다. 모든 문서가 인쇄될 때마다 검증을 해야 하고, 그렇게 하면 코드의 가독성과 능률이 처참하게 떨어진다

 

public void q1966(){
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        int point = sc.nextInt();
        Deque<Integer> deq = new ArrayDeque<>();
        int[] arr = new int[len];
        boolean ck = true;
        int code = 0;

        for(int i = 0; i < len; i++){
            deq.add(sc.nextInt());
        }

        // 덱을 순회

        int i = 0;
        int j = 0;
        while(ck){

            // 덱이 비어있을 경우
            if(deq.isEmpty()){
                ck = false;
            // 덱에 남아있는 것이 하나일 때
            }else if(deq.size() == 1){
                arr[len-1] = deq.getFirst();
                if(code == 0) code = len-1;
                ck = false;
            // 덱에 2 이상이 남아있을 때
            }else{
                int num = deq.pollFirst();
                boolean boo = false;

                for(int d : deq){
                    boo = false;
                    // 덱의 첫번째부터 순회하면서 num보다 높은 값이 있는지 확인
                    if(num < d){
                        boo = true;
                        break;
                    }
                }
                // 덱에 아직 높은 값이 존재함
                if(boo){
                    deq.add(num);
                    if(j == point){
                        point = deq.size() - 1;
                        j = 0;

                    }else{
                        j++;
                    }
                }else{
                    arr[i] = num;

                    if(j == point){
                        code = i + 1;
                    }
                    i++;
                    j++;
                }


            }

        }

 

이게 처음의 코드...

 

그리고 이제 수정

이게 대체 어디가 문제인지 모르겠다 분명 계속 테스트를 할 때는 제대로 되는데 오답이라고 나온다.

 

public void q1966_1(){
        Scanner sc = new Scanner(System.in);
        Queue<int[]> q = new ArrayDeque<>();
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];


        for(int i = 0; i <n ; i++){
            q.offer(new int[]{sc.nextInt(),i});
        }

        int i = 0;
        boolean whileloop = true;
        while(whileloop){
            int[] fst = q.poll();       // 첫번째 값 담기
            boolean ck = false;         // 인쇄여부

            // 돌아가면서 비교
            for(int[] nums : q){

                // 첫번째 값보다 클 경우
                if(nums[0] > fst[0]){
                    q.offer(new int[]{fst[0], fst[1]});
                    ck = false;
                    break;
                }else{
                    ck = true;
                }
            }

            if(ck){
                arr[i] = fst[0];
                if(fst[1] == m) whileloop = false;
                i++;
            }

        }

        System.out.println(i);
    }

 

 

그래서 내 머리로는 도저히... 도저히 답이 안 나와서 GPT를 불렀다.

여기에서 GPT에게 하는 질문은 어떻게 하는 편이냐 하면, 나같은 경우는 코드는 물어보지 않고, 코드를 주고 수정사항만 알려달라고 한다. 코드를 제외하고 알려달라고 하면 알아서 문제점만 알려준다. 

답을 아는 것보다는 풀이 과정을 이해하고 답은 내가 도출하는 게 공부가 되는 것 같아서 :D!

 

그래서 받은 답변은 다음과 같다

 

---

제공된 코드를 검토해 보았을 때, 문제를 해결하기 위한 주요 로직은 올바른 방향으로 가고 있으나, 몇 가지 문제점이 있습니다. 문제점을 지적하고, 해결 방안을 제시하겠습니다.

문제점

1. 큐가 비어 있는 경우의 처리: q.poll()을 사용하여 큐에서 요소를 꺼낼 때, 큐가 비어있는 경우를 고려하지 않았습니다. 하지만 현재 로직 구조상, 큐가 비어 있을 때 q.poll()이 호출되지 않도록 하는 다른 조건들로 인해 실제 실행에는 문제가 없을 것으로 보입니다.
2. ck 변수의 사용: ck 변수가 현재 문서를 인쇄할 것인지를 결정하는 데 사용되지만, 그 처리 방식에 문제가 있습니다. 만약 큐에 남아있는 모든 문서의 중요도가 현재 문서보다 낮다면, ck = true;가 되어야 합니다. 그러나 현재 로직에서는 큐의 마지막 문서가 현재 문서보다 중요도가 낮은 경우에만 ck = true;로 설정됩니다. 이는 중요도가 낮은 다른 문서들이 앞에 있을 때 잘못된 결과를 초래할 수 있습니다.
3. 문서 재배치의 처리: 현재 문서보다 중요도가 높은 문서가 존재할 경우, 현재 문서를 큐의 끝에 다시 추가합니다. 이 부분은 올바르게 처리되고 있으나, ck 변수가 false로 설정되는 시점이 적절하지 않습니다. ck = false;는 사실상 필요 없는 할당이며, ck 변수의 값 설정에 대한 로직이 명확하지 않습니다.
4. 인쇄 순서 계산: i 변수는 인쇄된 문서의 수를 세기 위해 사용됩니다. 그러나 현재 문서보다 중요도가 높은 문서가 없어서 현재 문서가 인쇄될 때만 i를 증가시키는 로직이 문제가 없는지 확인해야 합니다. 문제의 설명대로라면 이 부분은 기본적으로 올바르게 처리되고 있는 것으로 보입니다.

해결 방안

1. ck 변수의 처리 로직 개선: ck 변수를 사용하지 않고, 대신 큐에서 문서를 꺼낸 후 바로 중요도가 높은 문서가 있는지 확인하여, 있다면 꺼낸 문서를 큐의 끝에 추가하고, 없다면 인쇄 처리합니다. 이 때, 궁금한 문서가 인쇄되었는지 확인하여 그 순간의 반복 횟수를 출력하면 됩니다.
2. 큐가 비어 있는 경우 고려: 현재 로직에서는 큐가 비어 있을 때 poll()을 호출하지 않으므로, 이 부분은 문제가 되지 않습니다.
3. 문서 재배치 로직 확인: 현재 문서보다 중요도가 높은 문서가 있을 때, 현재 문서를 큐의 끝에 다시 추가하는 로직은 올바르게 작동합니다. 중요도가 높은 문서가 없을 경우에만 인쇄 순서(i)를 증가시키고, 궁금한 문서의 인쇄 여부를 확인합니다.
4. 인쇄 순서 계산: 인쇄 순서를 계산하는 로직은 큐에서 문서를 인쇄(제거)할 때마다 i를 증가시키고, 궁금한 문서가 인쇄될 때 그 시점의 i 값을 출력하면 됩니다. 이 로직은 현재 구현에서 기본적으로 올바르게 처리되고 있습니다.

추가 수정 제안

• ck 변수를 제거하고 로직을 단순화하여, 큐에서 문서를 꺼낸 후 바로 중요도 비교를 수행합니다. 중요도가 높은 문서가 없으면 바로 인쇄 처리하고, 있으면 큐의 끝에 다시 추가합니다.
• 문서가 인쇄될 때마다 인쇄 순서를 카운트하는 방식은 유지하되, 궁금한 문서가 인쇄될 때의 순서를 정확히 출력해야 합니다.

제공된 코드는 기본적으로 문제의 요구사항을 충족하는 방향으로 작성되었으나, ck 변수의 처리 로직과 문서 재배치 로직의 명확성을 개선할 필요가 있습니다.

 

---

 

그러니까, 결국 로직에서 문제되는 것은 ck를 사용하는 부분이고, 이 부분만 개선한다면 코드도 줄어들고 매끄럽게 동작한다는 것이다. 명확성의 문제라고 하는데... 쓰읍 모르겠다... 하지만 그냥 명확하지 않다고 하니까 고치자...

 

이제 다시... 풀이를 한다.

ck를 줄이려면 어떻게 하는가? 하다가 큐가 비워질 때까지 반복하고, 반복되다가 프린터에 들어갈 애라면 반복을 멈추고 (어차피 다음 for문이 돌아간다면 큐는 줄어든 상태니까 while문부터 다시 돌아감 ) 아래로 내려가 if문으로 이게 m인지 확인을 한다.

 

    public void q1966_1(){
        Scanner sc = new Scanner(System.in);
        Queue<int[]> q = new ArrayDeque<>();
        int n = sc.nextInt();
        int m = sc.nextInt();


        for(int i = 0; i <n ; i++){
            q.offer(new int[]{sc.nextInt(),i});
        }

        int i = 0;
        while(!q.isEmpty()){
            int[] fst = q.poll();       // 첫번째 값 담기
            boolean ck = true;         // 인쇄여부

            // 돌아가면서 비교
            for(int[] nums : q){

                // 첫번째 값보다 클 경우
                if(nums[0] > fst[0]){
                    q.offer(fst);
                    ck = false;
                    break;
                }
            }

            if(ck){
                i++;
                if(fst[1] == m) {
                    break;
                }
            }

        }

        System.out.println(i);
    }

 

 

근데 틀렸단다

아무리 반례를 넣어도 맞는다 진짜 화가 난다 하다하다 지피티에게 자문을 구했다

 

---

제공된 코드를 검토한 결과, 코드 자체에는 문제가 발생할 만한 로직의 오류는 보이지 않습니다. 주어진 문제 설명에 따르면, 이 코드는 문서의 중요도를 기준으로 인쇄 순서를 결정하고, 특정 문서가 몇 번째로 인쇄되는지를 찾는 알고리즘을 구현하고 있습니다. 코드의 로직은 다음과 같습니다:

1. 문서의 중요도와 그 문서의 초기 위치를 포함하는 int[] 배열을 큐에 추가합니다.
2. 큐가 비어있지 않은 동안, 큐에서 첫 번째 문서를 꺼내 (fst) 그 문서가 인쇄될 수 있는지 검사합니다. 인쇄 가능 여부는 해당 문서보다 중요도가 높은 다른 문서가 큐에 있는지 여부에 따라 결정됩니다.
3. 만약 현재 문서보다 중요도가 높은 문서가 큐에 있다면, 현재 문서는 큐의 끝으로 다시 추가됩니다.
4. 그렇지 않고 현재 문서가 인쇄될 수 있다면, 인쇄 순서 카운터 (i)를 증가시키고, 현재 문서가 사용자가 궁금해하는 문서 (m에 해당하는 문서)인지 확인합니다. 만약 그렇다면 반복을 종료하고 현재까지의 인쇄 순서 (i)를 출력합니다.

이 코드가 특정 테스트 케이스에서 예상과 다른 결과를 출력한다면, 입력 형식이나 특정 상황에서의 예외 처리를 다시 확인해야 할 수 있습니다. 그러나 코드 로직 자체는 문제의 요구 사항을 충족하는 올바른 접근 방식을 따르고 있습니다.

문제가 지속된다면, 다음 사항을 추가로 확인해 볼 수 있습니다:

• 입력 값의 정확성: Scanner를 통해 입력받는 값들이 정확한지 확인하세요. 예를 들어, n과 m, 그리고 각 문서의 중요도가 올바르게 입력되었는지 검토해 보세요.
• 종료 조건: if(fst[1] == m) 조건은 궁금한 문서가 인쇄될 때 반복을 종료하는 올바른 조건입니다. 이 부분에서의 로직은 문제가 없어 보입니다.
• 인쇄 순서 카운터 (i): 이 카운터는 인쇄될 때마다 증가하며, 궁금한 문서가 인쇄되면 그 순간의 값이 출력됩니다. 로직상 여기에도 문제가 없어 보입니다.

혹시 문제가 '틀렸습니다'로 판정된다면, 문제의 조건을 다시 한번 꼼꼼히 확인하거나, 다른 테스트 케이스로도 실험해 보시길 권장드립니다. 때로는 예외 사항이나 미처 고려하지 못한 입력 값의 범위 등이 문제의 정답 여부에 영향을 줄 수 있습니다.

---

 

이 코드가 맞단다. 화가 난다. 

이걸 어떻게 처리해야 하지 생각하다가... 그냥 입력방식을 바꾸기로 했다. 아니... 혹시 모르잖아....

물론 이게... 이게 시간 초과는 뜨지 않지만... (보통 int형으로 끝나는 문제에서는 Scanner를 써도 크게 문제가 되지 않는다. 그냥 지금까지 그랬다.) 그냥 호오오옥시 몰라서....

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < t; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken()); 
            int m = Integer.parseInt(st.nextToken()); 

            Queue<int[]> q = new ArrayDeque<>();
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                q.offer(new int[]{Integer.parseInt(st.nextToken()), i});
            }

            int printOrder = 0; 
            while (!q.isEmpty()) {
                int[] current = q.poll();
                boolean isPrintable = true; 
                for (int[] doc : q) {
                    if (doc[0] > current[0]) { 
                        q.offer(current); 
                        isPrintable = false;
                        break;
                    }
                }
                if (isPrintable) {
                    printOrder++; 
                    if (current[1] == m) {
                        System.out.println(printOrder);
                        break; 
                    }
                }
            }
        }
    }
}

 

 

근데 어이없게 이게 맞음 ( 이 코드는 지피티한테 코드를 그냥 Buffer 형태로 변경해달라고 한 거다. 거기까지 하기는 내가 너무 귀찮았다.)

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

대체 뭐가 문제였던 건지 몰라서... 물어봤다...

시간 초과 말고 어떤 문제가 둘의 차이를 불러왔을까? 내가 생각하지  못한 부분이 있을까?

 

---

 

Scanner와 BufferedReader 사이에 정답과 오답이 갈린 이유를 정확히 판단하기 위해서는 다양한 요소를 고려해야 합니다. 그러나 일반적으로, Scanner와 BufferedReader의 주요 차이점은 처리 속도와 메모리 사용량에 있으며, 이러한 차이가 문제의 정답 처리에 영향을 줄 수 있습니다. 아래는 몇 가지 가능한 이유를 설명합니다:

1. 입력 처리 속도

• **Scanner**는 정규 표현식을 사용하여 입력을 파싱하기 때문에 상대적으로 느릴 수 있습니다. 대량의 데이터를 처리할 때 이로 인한 시간 지연이 누적되어 시간 초과로 이어질 수 있습니다.
• **BufferedReader**는 단순한 문자열 처리 방식을 사용하여 입력을 받기 때문에, 더 빠른 입력 처리가 가능합니다. 이는 특히, 입력 데이터의 양이 많을 때 성능 차이로 크게 나타납니다.

2. 메모리 사용량

• Scanner는 내부적으로 더 많은 메모리를 사용할 수 있으며, 이는 대량의 데이터를 처리할 때 문제가 될 수 있습니다.
• BufferedReader는 더 적은 메모리를 사용하여 입력을 처리합니다.

3. 시간 제한 문제

• 온라인 코딩 테스트 플랫폼이나 프로그래밍 대회에서는 문제를 해결하는 데 있어 시간 제한이 중요한 요소입니다. Scanner를 사용했을 때 시간 초과가 발생하고, BufferedReader를 사용했을 때 시간 초과 없이 문제를 해결할 수 있는 경우가 많습니다.

4. 특정 테스트 케이스 또는 플랫폼의 특성

• 때로는 특정 온라인 저지 시스템에서 Scanner와 BufferedReader 사이의 성능 차이를 다르게 처리할 수 있습니다. 예를 들어, 입력 데이터의 양이 많거나 특정 형식의 데이터 처리에 BufferedReader가 더 적합할 수 있습니다.
• 입력 데이터가 매우 클 경우, Scanner의 처리 속도가 문제의 시간 제한을 초과하여 '시간 초과' 결과를 초래할 수 있습니다.

결론적으로, Scanner를 사용했을 때와 BufferedReader를 사용했을 때의 차이는 주로 성능(처리 속도와 메모리 사용량)에 있으며, 이러한 성능 차이가 문제를 해결하는 데 있어 시간 제한 초과 또는 메모리 초과 같은 결과를 초래할 수 있습니다. 따라서 대량의 데이터를 처리해야 하는 상황에서는 BufferedReader의 사용을 고려하는 것이 좋습니다.

 

 

---

 

음

문제가 없다

어... 저 4개의 문제라면 시간 초과나 다른 오류가 떴을 것인데, 그게 없이 그냥 틀렸습니다가 나오는 이유는 없다. 처리 속도 관련이 아니니까. 그냥 이건 미궁으로 빠지고... 앞으로 저 긴 거 쓰기 귀찮아서 Scanner를 이용했던 거... BufferedReader를 써야겠구나... 하는 생각만 난다... 어... 그렇다...