[BOJ 백준] 큐(10845) C++, Java

 

링크 : https://www.acmicpc.net/problem/10845

10845번: 큐

 

문제 설명 : 

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

 

입력 : 

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력 : 

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

예제 입력 : 

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

예제 출력 : 

1
2
2
0
1
2
-1
0
1
-1
0
3

 

 

접근법 : 

1) 어떻게 풀 것인가?

주어진 조건을 그대로 구현할 수 있는지에 대한 문제이다.

 

2) 시간복잡도

(실행시간 : C 340ms)

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

Java 코드 : 

import java.io.*;
import java.util.*;

// 큐
public class Main {

	static int N;
	
	static class queue{
		int lp, rp;
		int [] queue;
		
		public queue(int size) {
			this.lp = this.rp = 0;
			this.queue = new int [size+1];
		}
		
		public void push(int x) {
			queue[rp] = x;
			rp++;
		}
		
		public int pop() {
			if (lp == rp) return -1;
			return queue[lp++];
		}
		
		public int size() {
			return rp-lp;
		}
		
		public int empty() {
			if (rp-lp == 0) return 1;
			return 0;
		}

		public int front() {
			if(rp-lp==0) return -1;
			return queue[lp];
		}
		
		public int back() {
			if(rp-lp == 0) return -1;
			return queue[rp-1];
		}
		
	}

	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();

		N = Integer.parseInt(br.readLine());
		queue que = new queue(N); 
		
		for (int i = 0; i<N; i++) {
			
			
			String[] inStrList = br.readLine().split(" ");
			
			if (inStrList[0].equals("push")) {
				que.push( Integer.parseInt(inStrList[1] ));
			}
			else if (inStrList[0].equals("pop")) {
				sb.append(que.pop()+"\n");
			}
			else if (inStrList[0].equals("size")) {
				sb.append(que.size()+"\n");
			}
			else if (inStrList[0].equals("empty")) {
				sb.append(que.empty()+"\n");
			}
			else if (inStrList[0].equals("front")) {
				sb.append(que.front()+"\n");
			}			
			else if (inStrList[0].equals("back")) {
				sb.append(que.back()+"\n");
			}
		}


		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}

}

 

C++ 코드 : 

// 큐 10845 C++
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <vector>
#include <iostream>
#include <string>

#define MAX (10000 + 3)

using namespace std;

int N;

void push(int x);
void pop();
void size();
void empty();
void top();
void front();
void back();

int queue[MAX];
int sp;  // 출구
int ep;  // 입구

int main() {
	// 1. 입력받는다
	freopen("input.txt", "r", stdin);
	scanf("%d", &N);

	// 2. 명령어 입력에 따라 수행한다.
	string inputString;
	int inputInt;
	for (int i = 1; i <= N; i++) {
		cin >> inputString;

		if (inputString.compare("push") == 0) {
			scanf("%d", &inputInt);
			push(inputInt);
		}
		else if (inputString.compare("pop") == 0) {
			pop();
		}
		else if (inputString.compare("size") == 0) {
			size();
		}
		else if (inputString.compare("empty") == 0) {
			empty();
		}
		else if (inputString.compare("front") == 0) {
			front();
		}
		else if (inputString.compare("back") == 0) {
			back();
		}
	}
	return 0;
}


void push(int x) {
	queue[ep] = x;
	ep++;
}

void pop() {
	if (sp == ep) {
		printf("%d\n", -1);
	}
	else {
		printf("%d\n", queue[sp]);
		sp++;
	}
}

void size() {
	printf("%d\n", ep-sp);
}

void empty() {
	if (sp == ep) {
		printf("%d\n", 1);
	}
	else {
		printf("%d\n", 0);
	}
}

void front() {
	if (sp == ep) {
		printf("%d\n", -1);
	}
	else {
		printf("%d\n", queue[sp]);
	}
}

void back() {
	if (sp == ep) {
		printf("%d\n", -1);
	}
	else {
		printf("%d\n", queue[ep-1]);
	}
}
#endif