[C++] 백준 24511. queuestack

문제

문제 이해하는 데 한참 걸림;

입력이 아주 크다..

시간초과1

아니나 다를까 시간 초과다.
근데 내일 풀거다
왜냐면 너무 피곤해서..
뭐했다고 피곤하냐면
.. 이거저거 했다

#include <iostream>
#include <deque>
using namespace std;

int N, M, tmp;
deque<int> A;
deque<int> B;
deque<int> C;

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		A.push_back(tmp);
	}
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		B.push_back(tmp);
	}

	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> tmp;
		C.push_back(tmp);
	}
}

void solution() {
	for (int i = 0; i < M; i++) {
		int ret = C[i];
		for (int j = 0; j < N; j++) {
			if (A[j] == 0) {
				B.insert(B.begin() + j, ret);
				ret = B[j + 1];
				B.erase(B.begin() + j + 1);
			}
		}
		cout << ret;
		if (i < M - 1) cout << " ";
	}

	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	input();
	solution();
	
	return 0;
}

시간초과2

위 코드에서

1. 삽입 삭제 부분을 swap 함수로 대체
2. queue인 경우(A[i] == 0)만 계산하도록
3. 삽입할 수 (C) 입력 받자마자 계산하도록

바꿔봤다. 여전히 시간 초과인ㅠ

#include <iostream>
#include <vector>
using namespace std;

int N, M, tmp;
vector<int> A, B, C;

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		A.push_back(tmp);
	}
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		if (A[i] == 0) B.push_back(tmp);
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> tmp;
		for (int j = 0; j < B.size(); j++) {
			swap(tmp, B[j]);
		}
		cout << tmp;
		if (i < M - 1) cout << " ";
	}

	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solution();
	return 0;
}

풀이

queue인 경우만 계산해도 되겠군 하고
예시 입력과 출력 과정을 손으로 써보다가 큐는 선입선출이라는 걸 깨달았다.
그러니까 삽입 원소는 앞으로 들어가고 기존 원소는 뒤로 빠지는 것이다.

정리, 이 문제를 풀려면

1. 값을 넣었을 때 stack에선 튕겨나오고 queue에선 자리를 바꾼다
2. 그러면 stack은 고려할 필요가 없다
3. 결과적으로 B라는 deque의 front에 C의 원소를 삽입한 뒤,
   B의 back에서 기존 원소를 pop하는 과정과 같다

는 점을 순서대로 깨달으면 된다.

코드

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int N, M, tmp;
vector<int> A, C;
deque<int> B;

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		A.push_back(tmp);
	}
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		if (A[i] == 0) {
			B.push_back(tmp);
		}
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> tmp;
		B.push_front(tmp);
		cout << B.back() << " ";
		B.pop_back();
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solution();
	return 0;
}

채점

원래 같으면 시간 초과 세 개 정도 보고 바로 구글링 했을텐데
오기 생겨서 열심히 감자굴리기
맷집이 생겼나보다