[백준] 1966 : 프린터 큐

아무리 생각해도 논리는 맞는 것 같은데 자꾸 오류가 떠서 이 문제만 하루는 잡고 있었다..

논리오류가 아닌 코드오류였던 것에 반성하자

풀이과정

가장 큰 중요도를 기준으로 맨 앞의 문서의 중요도가 낮으면 빼낸 후 뒤로 보내기

중요한 것은 같은 중요도를 가진 문서도 많을 수 있다는 것. >> 원하는 문서의 위치를 저장하여 위치가 맨 앞일 때가 답임

가장 큰 중요도도 계속해서 바뀌기 때문에 중요도를 넣을 배열도 생성.

문제를 풀고 얻어낸 점

BufferedReader와 StringTokenizer에 대한 이해

if-else문의 논리구조

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Queue_Q1966 {
	static int answerImportance; // 구해야 할 문서의 중요도
	static int answerIndex; //구해야 할 문서의 위치
	static int Top; //현재 가장 큰 중요도
	static int indexOfTop; // 현재 가장 큰 중요도의 배열리스트 내의 위치
	static int result; // 해당 문서가 처리되는 순서 (답)

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine()); //테스트케이스 입력
		
		for(int t = 1; t <= T; t++) { //테스트케이스만큼 반복
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int N = Integer.parseInt(st.nextToken()); //queue의 크기 입력
			int M = Integer.parseInt(st.nextToken()); //찾아야 하는 문서의 위치 (인덱스)
			
			ArrayList<Integer> arrList = new ArrayList<>(); // 중요도 넣을 배열리스트 생성
			
			Queue<Integer> queue = new LinkedList<>(); //큐 선언
			st = new StringTokenizer(br.readLine()); //왜 또 선언해줘야 하는지?
			
			int importance;
			for(int n = 0; n < N; n++) {
				importance = Integer.parseInt(st.nextToken()); //중요도 입력
				queue.offer(importance); // 큐 삽입
				arrList.add(n, importance);

				if(n == M) {
					answerImportance = importance; //구해야 할 문서의 중요도
					answerIndex = n; //구해야 할 문서의 위치
				}
			}
			
			arrList.sort(Comparator.naturalOrder()); //배열리스트 오름차순 정리
			
			indexOfTop = N - 1; // 가장 큰 중요도의 위치 초기화 (오름차순이니까 맨 끝)
			Top = arrList.get(indexOfTop); // 현재 가장 큰 중요도
			result = 0;
			
			//System.out.println(queue);
			//System.out.println("가장 큰 중요도" + Top);
			//System.out.println("구해야 하는 중요도 " + answerImportance);
			while(!queue.isEmpty()) { // 큐가 비어있지 않는 동안
				int num;
				if(answerImportance < Top) { //구해야 하는 중요도가 가장 큰 중요도가 아닐 때
					if(queue.peek() == Top) {
						queue.remove();
						Top = arrList.get(--indexOfTop); // 가장 큰 중요도 바꿔줌. indexOfTop--은 안됨 왜?
						//System.out.println("삭제 후 가장 큰 중요도는 " + Top);
						if(answerIndex == 0)
							answerIndex = queue.size() - 1;
						else
							answerIndex--;
						
						result++; //삭제된 개수
						//System.out.println(queue);
						//System.out.println("궁금한 문서의 현재 위치" + answerIndex);
						//System.out.println("삭제 된 개수 " + result);
					}
					else {
						num = queue.poll();
						queue.offer(num);
						if(answerIndex == 0)
							answerIndex = queue.size() - 1;
						else
							answerIndex--;
						//System.out.println("가장 큰 중요도는 " + Top);
						//System.out.println(queue);
					}
				}
				
				else if(answerImportance == Top) { //구해야 하는 중요도가 가장 큰 중요도일 때
					//System.out.println("넘어옴");
					if( Top != queue.peek()) {
						num = queue.poll();
						queue.offer(num);
						--answerIndex;
						//System.out.println("작은 애들은 뒤로 보내기");
					}
					else if(Top == queue.peek()) {
						if(answerIndex != 0) {
							queue.remove();
							result++;
							--answerIndex;
							//System.out.println("같은 중요도지만 원하는 문서가 아니니까 삭제\n현재 위치" + answerIndex);
						}
						else {
							queue.remove();
							result++;
							
							sb.append(result).append('\n');
							//System.out.println("최종 삭제 된 순서 " + result);

							break;
						}
					}
				}
			}
		}
		
		System.out.println(sb);
	}
}

계속된 오류로 순서를 확인하려고 System.out.println을 많이 사용하였다.

확인용으로 넣은 것 뿐. 실제 코드에는 BufferedWriter나 StringBuilder가 더 효율적임.

 

같은 언어로 문제를 해결한 사람들은 80ms 정도의 시간복잡도를 가짐.

내 코드는 143ms로 거의 2배가 걸림.

시간복잡도를 줄일 코드를 생각해보자.