[백준] 18258번: 큐2

 

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

18258번: 큐 2

자꾸 시간초과가 나서 고생했다. 검색해보니 시간 초과가 꽤 나는 문제인 것 같다.

시간 초과가 나는 원인은:

1. 모든 기능을 별도의 함수로 정의하고 함수 콜을 하다보니 시간이 오버된다. 고로 main함수 안에 모든 코드를 때려넣어야 한다. 

2. 입출력이 느리다. 

* 찾아보니, endl 는 스트림을 개행문자 처리 후에 flush까지 해버리기 때문에 더 costly 하다고 한다. 그래서 시간이 부족할 때엔 endl 이 아니라 "\n"을 사용하는 것이 좋다. 

* cin과 cout이 반복적으로 일어나면 성능에 안좋다. 

* printf, scanf, puts, gets, getchar 등도 마찬가지로 안좋다. 

cin.tie(0);
cin.sync_with_stdio(0);

이 두 라인을 코드에 추가하면 입출력 스트림을 더 빠르게 사용할 수 있다고 한다. 

1. ios::sync_with_stdio(false)

ios::sync_with_stdio는 cpp의 iostream을 c의 stdio와 동기화해주는 역할을 한다.

이렇게 iostream 과 stdio를 모두 사용하게 되면 당연히 속도가 느려진다. 

이 설정을 false(0)으로 바꿔줌으로써 둘 간의 동기화를 끊어버린다.

그럼 c++만의 독립적 버퍼를 사용하게 되어, 사용하는 버퍼의 수가 줄기 때문에 더 빨라진다. 

2. cin.tie(null)

cin과 cout간의 묶음을 풀어준다. 위에서 cin과 cout이 번갈아가며 반복되면 안좋다고 했는데 cin이 입력을 받기 전에 출력 버퍼를 비우는 과정을 거치기 때문이다. 그래서 이 둘 간의 연결을 끊어주는 것이 좋은 것.

* 참고: https://starrykss.tistory.com/750

[BOJ15552][C++] 빠른 A+B

큐의 기능 자체는 흔히들 알고있는 그대로여서 구현하기는 어렵지 않다.

시간 초과문제를 잘 해결하기만 하면 쉽게 풀 수 있다. 

#include <iostream>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

// 큐의 저장을 위한 요소들
// 전역변수 아니고 main안으로 들어가도 충분하다..
int queue[2000000];
int count = 0;
int startPtr=0;
int endPtr = 0;

int main(void){
	
	// 필수! 
	cin.tie(0);
	cin.sync_with_stdio(0);
	
	int n;
	cin >> n;
	
    // 답을 저장해두었다가 마지막에 한번에 출력하기 위해 벡터를 선언
	vector<int> answer;
	
	string task;
	int num;
	for(int i = 0; i<n; i++){
		cin >> task;
		if(task == "push"){
			cin >> num;
			if(count>0){
				endPtr = (endPtr+1)%2000000;
			}
			queue[endPtr] = num;
			count++;
		}else if(task == "pop"){
			if(count!=0){
				int res =queue[startPtr];
				if(count!=1){
					startPtr = (startPtr+1)%2000000;
				}
				count--;
				answer.push_back(res);
			}else{
				answer.push_back(-1);
			}
		}else if(task == "size"){
			answer.push_back(count);
		}else if(task == "empty"){
			if(count == 0){
				answer.push_back(1);
			}else{
				answer.push_back(0) ;
			}
		}else if(task == "front"){
			if(count==0){
				answer.push_back(-1);
			}else{
				answer.push_back(queue[startPtr]);
			}
		}else if(task == "back"){
			if(count==0){
				answer.push_back(-1);
			}else{
				answer.push_back(queue[endPtr]);
			}
		}

	}
	
	for(int i = 0; i<answer.size(); i++){
		cout << answer[i] << "\n";
	}
}

• 큐는 접근 속도를 빨리 하기 위해서 그냥 array로 선언해주었다. 총 2000000개의 명령이 들어오므로, 큐에 들어갈 수 있는 최대 원소 개수도 2000000개로 해주었다.
• startPtr와 endPtr라는 index를 이용해서 front, back등을 표시하며 계속 뒤에다가 새로운 요소를 append하기 때문에 앞에 push 했다가 pop해서 남은 공간을 이어서 사용해주기 위해(circular하게) mod 연산을 넣었다. 
• vector로 해도 될지는 모르겠다. (구현은 했는데 시간 초과 떠서 중간에 array로 바꾸어버렸다)
• 다른 분들의 예시들을 보니까 deque 를 쓰는 경우도 많은 것 같았다.