초급반 6주차 풀이 - 구조체, STL

1. [10845] 큐 (Silver IV)

STL 큐에 있는 6가지 연산들을 그대로 써주면 됩니다.

비어있을 때 -1을 출력하는 부분들만 잘 예외처리하면 됩니다.

 

+ STL queue에 back이 있다는 건 저도 풀이를 쓰면서 알았습니다.

queue<int> que;

void Main(){
	int q; cin >> q; while (q--){
		string typ; cin >> typ;
		if (typ == "push"){ int x; cin >> x; que.push(x); }
		if (typ == "pop"){
			if (que.empty()){ cout << -1 << endl; }
			else{ cout << que.front() << endl; que.pop(); }
		}
		if (typ == "size"){ cout << que.size() << endl; }
		if (typ == "empty"){ cout << que.empty() << endl; }
		if (typ == "front"){
			if (que.empty()){ cout << -1 << endl; }
			else{ cout << que.front() << endl; }
		}
		if (typ == "back"){
			if (que.empty()){ cout << -1 << endl; }
			else{ cout << que.back() << endl; }
		}
	}
}

2. [10828] 스택 (Silver IV)

"1. [10845] 큐" 문제의 스택 버전입니다.

역시 STL stack에 있는 연산들을 그대로 써주면 됩니다.

stack<int> stk;

void Main(){
	int q; cin >> q; while (q--){
		string typ; cin >> typ;
		if (typ == "push"){ int x; cin >> x; stk.push(x); }
		if (typ == "pop"){
			if (stk.empty()){ cout << -1 << endl; }
			else{ cout << stk.top() << endl; stk.pop(); }
		}
		if (typ == "size"){ cout << stk.size() << endl; }
		if (typ == "empty"){ cout << stk.empty() << endl; }
		if (typ == "top"){
			if (stk.empty()){ cout << -1 << endl; }
			else{ cout << stk.top() << endl; }
		}
	}
}

3. [9012] 괄호 (Silver IV)

괄호 짝을 검사하는 알고리즘은 다음과 같습니다.

• 문자열을 앞에서부터 읽으면서...
  • 여는 괄호가 나오면 이를 스택에 넣는다.
  • 닫는 괄호가 나오면 스택에서 여는 괄호를 하나 뺀다. (짝이 맞는 것들)
• 위 과정에서 "스택이 비어있는데 괄호를 빼야 하는 경우" 또는 "문자열을 끝까지 다 읽었는데 스택에 괄호가 남은 경우"가 발생하면 VPS가 아니고, 그런 경우가 없으면 VPS가 됩니다.

void Main(){
	int t; cin >> t;
	while (t--){
		string s; cin >> s;
		stack<int> stk;
		for (char ch : s){
			if (ch == '('){ stk.push(ch); }
			if (ch == ')'){
				if (stk.empty()){ cout << "NO"; goto done; }
				stk.pop();
			}
		}
		if (stk.empty()){ cout << "YES"; } else{ cout << "NO"; }
		done: cout << endl;
	}
}

만약 괄호가 여러 종류가 있다면 위의 풀이를 사용해야 하지만, 이 문제에서는 괄호가 1종류밖에 없습니다.

즉, 스택은 중요하지 않고 "스택의 크기"만 알고 있으면 됩니다.

그러니, 위 풀이에서 했던 과정을 스택의 크기만 가지고 해줄 수 있습니다.

void Main(){
	int t; cin >> t;
	while (t--){
		string s; cin >> s;
		int cnt = 0;
		for (char ch : s){
			if (ch == '('){ cnt += 1; }
			if (ch == ')'){ cnt -= 1; }
			if (cnt < 0){ cout << "NO"; goto done; }
		}
		if (cnt == 0){ cout << "YES"; } else{ cout << "NO"; }
		done: cout << endl;
	}
}

4. [15552] 빠른 A+B (Bronze II)

cin, cout을 사용할 거라면 ios_base::sync_with_stdio(0); cin.tie(0);이 필요합니다. (cout.tie(0)은 필요없습니다.)

endl을 사용할 거라면 #define endl '\n'이 필요합니다.

위의 2개가 FastIO의 기초입니다.

void Main(){
	int t; cin >> t;
	while (t--){
		int a, b; cin >> a >> b;
		cout << a+b << endl;
	}
}

5. [2164] 카드2 (Silver IV)

문제에서 나온대로 시뮬레이션을 돌려주면 됩니다.

맨 위 카드 = 큐의 맨 위, 맨 밑 카드 = 큐의 맨 뒤 로 정의하면

시뮬레이션을 돌리기 편해집니다.

void Main(){
	int n; cin >> n;
	queue<int> q; for (int i = 1; i <= n; i++){ q.push(i); }
	while (q.size() > 1){
		q.pop();
		q.push(q.front()); q.pop();
	}
	cout << q.front();
}

웰노운입니다 감사합니다

void Main(){
	int n; cin >> n;
	int m = n, bit = 0; while (m){ bit = m&-m; m ^= bit; }
	int p = (2*(n-bit)+1 + n-1) % n;
	if (p==0){ cout << n; } else{ cout << p; }
}

6. [1966] 프린터 큐 (Silver III)

큐를 돌리는 건 "5. [2164] 카드2"에서 해봤으니, 이제 원하는 값이 나올 때까지 큐를 돌려보면 됩니다.

프린트할 값들을 모두 큐에 넣은 뒤, 가중치를 정렬해서 i번째 출력에서 원하는 가중치 값을 들고 온 뒤

그 가중치를 가지는 프린트가 나올 때까지 열심히 큐를 돌려주면 됩니다.

int arr[120];

void Main(){
	int t; cin >> t;
	while (t--){
		int n, m; cin >> n >> m; m += 1;
		queue<pi2> q;
		for (int i = 1; i <= n; i++){ cin >> arr[i]; q.push({i, arr[i]}); }
		sort(arr+1, arr+n+1, [](int a, int b){ return a > b; });
		for (int i = 1; i <= n; i++){
			while (q.front().sc != arr[i]){ q.push(q.front()); q.pop(); }
			if (q.front().fr == m){ cout << i << endl; break; }
			q.pop();
		}
	}
}

7. [24511] queuestack (Silver III)

큐와 스택을 분석해봅시다.

큐의 경우, 새로운 값을 넣은 뒤 원래 값을 빼게 됩니다.

스택의 경우, 새로운 값을 넣은 뒤 그 새로운 값을 다시 빼게 됩니다.

 

스택을 보면 알겠지만, 새로운 값을 넣고선 그 값을 그냥 뺍니다. 즉 의미가 없습니다.

그럼 남는 건 큐밖에 없는데, 여러 개의 큐들을 이어보면 알겠지만 그냥 하나의 큰 큐가 됩니다.

 

그러니, 큐에 담긴 모든 원소들을 "N번에 가까운 원소가 앞에 오도록" 큐에 넣은 뒤 새로운 원소를 뒤에 넣고 / 맨 앞의 원소를 빼는 걸 반복해주면 됩니다.

queue<int> que;
bool chk[100020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> chk[i]; }
	stack<int> stk;
	for (int i = 1; i <= n; i++){
		int x; cin >> x;
		if (!chk[i]){ stk.push(x); }
	}
	while (!stk.empty()){ que.push(stk.top()); stk.pop(); }
	int q; cin >> q;
	while (q--){
		int x; cin >> x; que.push(x);
		cout << que.front() << ' '; que.pop();
	}
}

8. [1874] 스택 수열 (Silver III)

그리디입니다.

x를 출력하기 위해서는 일단 x까지 스택에 넣어야 하고, 그 뒤에 x를 빼내야 합니다.

물론 이미 x가 스택 저 안쪽에 들어가있다면 "불가능"하다는 결론을 내야 하지만요.

 

만약 위 과정에서 '불가능'이 뜨지 않고 끝까지 다 출력해냈다면, 이미 우리는 그 스택 수열을 만드는 방법을 알아냈으니 그 방법을 그대로 출력해주면 됩니다.

 

"불가능"이 스택 수열을 만드는 과정에서 판별되기 때문에 +, -의 출력을 "가능함이 보장"될 때까지 미뤄야 합니다.

void Main(){
	int n; cin >> n;
	int ptr = 1;
	stack<int> stk;
	string ans = "";
	for (int i = 1; i <= n; i++){
		int x; cin >> x;
		while (ptr <= x){ stk.push(ptr); ans += "+"; ptr += 1; }
		if (stk.top() != x){ cout << "NO"; return; }
		stk.pop(); ans += "-";
	}
	for (char ch : ans){ cout << ch << endl; }
}

9. [2493] 탑 (Gold V)

스택에 다른 탑들에게 보일 가능성이 있는 탑들을 저장해봅시다.

이는 스택에 탑들을 "내림차순"으로 저장하되, 기준에 맞지 않는 건 날려버리는 방식으로 구현해주면 됩니다.

 

이제 각각의 탑에 대해, "스택의 맨 위"에 있는 탑이 내가 레이저를 쏠 때 보이는 탑이 됩니다.

이유는 간단한데, 나보다 밑에 있는 탑은 스택 처리 과정에서 다 날아가고

그럼 나보다 위에 있는 탑들이 내림차순이자 가까운 순으로 나오기 때문에

나와 가장 가까운 + 나보다 큰 탑이 스택의 맨 위에 있게 됩니다.

int arr[500020];
stack<pi2> stk;

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){
		while (!stk.empty()){
			pi2 p = stk.top();
			if (p.fr < arr[i]){ stk.pop(); }
			else{ break; }
		}
		if (stk.empty()){ cout << 0; } else{ cout << stk.top().sc; }
		cout << ' '; stk.push({arr[i], i});
	}
}

심심해서 생각해본 풀이입니다.

요약하자면 가장 작은 탑부터 시작해서 Union-Find라는 이상한 자료구조를 써가면서 풀면 됩니다.

int arr[500020]; pi2 srt[500020];

int par[500020];
inline int fnd(int x){
	if (x == par[x]){ return x; }
	return par[x] = fnd(par[x]);
}
inline void uni(int a, int b){ par[fnd(a)] = fnd(b); }

int ans[500020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ par[i] = i; }
	for (int i = 1; i <= n; i++){ cin >> arr[i]; srt[i] = {arr[i], i}; }
	sort(srt+1, srt+n+1);
	for (int i = 1; i <= n; i++){
		int idx = srt[i].sc; int pi = fnd(idx);
		ans[idx] = fnd(pi-1);
		uni(pi, pi-1);
	}
	for (int i = 1; i <= n; i++){ cout << ans[i] << ' '; }
}