프린터

프로그래머스에서 제공하는 문제들 중 스택과 큐를 연습하기 위한 문제를 풀었다.

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42587

코딩테스트 연습 - 프린터 | 프로그래머스

 

문제 설명

문제 설명 및 예시

---

풀이 과정

중요도에 따라 먼저 출력하는 것과 나중에 출력하는 것에 차이를 두도록 요구하는 문제다.

기본적으로 FIFO의 스택 구조를 띄고 있으나, 더 중요한 요소가 있다면 가장 뒤로 보내는 큐의 구조도 함께 포함되어야 하는 조건도 함께 가지고 있다.

중요도를 표시한 정수형 배열과 출력을 요청할 인덱스 번호를 함께 입력하면 해당 인덱스는 몇 번째로 출력할 지를 계산해 반환해야 하는데 이를 위해 큐에 입력받은 배열의 값을 전부 넣어주었으며 반복문을 돌며 조건대로 출력값을 계산하는 과정으로 구성했다.

...

Queue<Integer> waitQ = new LinkedList<>();
int count = 0;

for (int i : priorities)
    waitQ.offer(i);

int size = waitQ.size();

while (!waitQ.isEmpty()) {
    int index = waitQ.poll();
    
    for (Integer i : waitQ) {
        waitQ.offer(index);
        if (location == 0)
            location = waitQ.size();
        break;
    }
    
    ...
    
}

 

위 방식을 통해 문제를 해결하는 과정에서 count의 값이 계속 늘어나는 문제를 발견하게 되었다. 이를 해결하고자 큐의 크기를 저장하는 변수를 선언한 후 해당 값과 현재 큐의 크기를 비교해 이전에 비해 크기가 작아졌다면 출력이 정상적으로 이루어졌다는 것을 뜻하기 때문에 count의 크기를 증가시키도록 조치했다.

다음으로는 location의 값을 줄여주는 부분이 큐를 돌며 값을 비교하는 반복문보다 앞에 있어 정상적으로 원하는 인덱스값을 가리키지 못해주는 문제를 발견했다.

for (Integer i : waitQ) {
    if (i > index) {
        waitQ.offer(index);
        if (location == 0)
            location = waitQ.size();
        break;
    }
}

//location값을 뒤에 감소시키도록 조치
if (location != 0)
    location--;
    
if (location == 0)
    break;

 

이를 해결하기 위해 반복문이 끝난 후 location값을 줄여주는 방식을 통해 이 값을 정상적으로 원하는 값과 동기화시킬 수 있게 되었다.

코드를 다시 리뷰해보던 중 또 다른 오류를 발견하게 되었는데 반복문 내 원하는 값이 아직 나올때가 되지 않아 offer()메소드를 통해 다시 큐로 들어가게 될 때 location값을 size()-1로 하여 원하는 요소의 값보다 한칸 앞의 요소를 가리키는 문제가 발생하는 것이었다.

이는 1을 추가로 빼던 코드를 삭제하여 간단하게 해결하게 되었다.

마지막 문제로 [1, 1, 9, 1, 1, 1]배열의 인덱스 1의 값이 출력되는 순서를 따지고자 할 때 첫 번째로 출력된다는 결과가 나타나는 문제를 발견했다.

이에 대한 문제는 확인 결과 while문을 빠져나오는 조건이 location값을 줄이는 조건문보다 뒤에 있어 location이 0이 되자마자 반복문을 빠져나갔기 때문이었다. 이 두 조건식의 순서를 바꿔주고 나자 정상적으로 원하는 값이 출력되어 오류를 해결할 수 있었다.

 

최종 코드

package StackQueueProblem;

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

public class PrintBasedOnImportance {
	public static void main(String[] args) {
		init();
	}
	
	static void init() {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			String input = br.readLine();
			StringTokenizer st = new StringTokenizer(input);
			int[] priorities = new int[st.countTokens()];
			int index = 0;
			
			while (st.hasMoreTokens())
				priorities[index++] = Integer.parseInt(st.nextToken());
			
			int location = Integer.parseInt(br.readLine());
			if (location > priorities.length - 1)
				System.exit(1);
			
			bw.write(solution(priorities, location) + "\n");
			bw.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	static int solution(int[] priorities, int location) {
		Queue<Integer> waitQ = new LinkedList<>();
		int count = 1;
		
		for (int i : priorities)
			waitQ.offer(i);
		
		int size = waitQ.size();
		
		while (!waitQ.isEmpty()) {
			int index = waitQ.poll();
			
			for (Integer i : waitQ) {
				if (i > index) {
					waitQ.offer(index);
					if (location == 0)
						location = waitQ.size();
					break;
				}
			}
			
			if (location == 0)
				break;
			
			if (location != 0)
				location--;
		
			if (size > waitQ.size()) {
				count++;
				size = waitQ.size();
			}
		}
		
		return count;
	}
}

---

 

채점 결과