[BAEKJOON] 15828 Router

문제 요약

• 알고리즘 분류: 큐
• 난이도: Silver4
• 문제내용:
  • 큐 담을수 있는 공간 N
  • -1이면 입력 종료
  • 0이면 pop연산 나머지는 큐 저장
  • 큐 저장시 담을 수 있는 공간 꽉 차면 버린다.

문제풀이

 이번 문제 큐에 관련된 문제이다. 일반적으로 구현하면 시간 초과가 떠서 큐 이론을 적용한 상태로 풀어야 된다. 

 큐에 대한 자세한 내용은 밑에 사이트에 참조하면된다.

https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전

Code

Python

from collections import deque
import sys
input = sys.stdin.readline
queue = deque()
N = int(input())
while(1):
    value = int(input())
    if(value == -1): break
    if value:
        if len(queue) < N:
            queue.append(value)
    else:
        queue.popleft()

if queue:
    print(' '.join(map(str, queue)))
else:
    print("empty")

Java

큐 중에서 원형 큐에 대한 개념만 알면 밑에 코드 보는데 문제가 없을 것이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] queue = new int[N];
		int front = 0;
		int back = -1;
		int value;
		while((value = Integer.parseInt(br.readLine())) != -1) {
			if (value == 0) {
				queue[front % N] = 0;
				front++;
			}else {
				if(front + N - 1 > back) {
					back++;
					queue[back % N] = value;
				}
			}
		}
		
		if(front > back) {
			System.out.println("empty");
		}else {
			StringBuilder sb = new StringBuilder();
			for(int i = front; i <= back; i++) {
				sb.append(queue[i % N]).append(" ");
			}
			System.out.println(sb);
		}
		
	}
	
}