0x06 - queue
다 간단함. queue에 관한 문제.
queue는 First In First Out!1021
놀이공원 줄 생각하면 됨. 먼저 선 사람대로 먼저 나감.
들어오는 사람은 앞사람 뒤에 줄 섬.
0x07 - deque
10866 | 덱
간단
1021 | 회전하는 큐
간단.
find() 알아두기.
ex) find
int idx = find(dq.begin(), dq.end(), t) - dq.begin();5430 | AC
어우 복잡. 골드인데 생각이 좀 필요하지만 깔끔하게 떨어지는 문제가 아니라 그냥 구현이 복잡;;
#include <bits/stdc++.h>
using namespace std;
deque<int> dq;
bool is_front;
void print() {
cout << '[';
for (int i = 0; i < dq.size(); ++i) {
if (is_front)
cout << dq[i];
else
cout << dq[dq.size() - 1 - i];
if (i == dq.size() - 1) break;
cout << ',';
}
cout << "]\n";
}
void run(string cmd) {
for (auto c : cmd) {
if (c == 'R')
is_front = !is_front;
else {
if (dq.empty()) {
cout << "error\n";
return;
}
if (is_front)
dq.pop_front();
else
dq.pop_back();
}
}
print();
}
void fill_dq(string numbers) {
dq.clear();
is_front = 1;
int x = 0;
for (auto c : numbers) {
if (isdigit(c)) {
x = x * 10 + c - '0';
} else if (c == ',' || c == ']') {
if (x < 1) continue;
dq.push_back(x);
x = 0;
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
// 4
int T;
cin >> T;
while (T--) {
// RDD
string cmd;
cin >> cmd;
// 4
int n;
cin >> n;
// [1,2,3,4]
string numbers;
cin >> numbers;
fill_dq(numbers);
run(cmd);
}
}11003 | 최솟값 찾기
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
deque<pair<int, int> > dq;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int N, L;
cin >> N >> L;
for (int i = 0; i < N; ++i) {
int x;
cin >> x;
if (!dq.empty() && dq.front().Y < i - L + 1) dq.pop_front();
while (!dq.empty() && dq.back().X >= x) dq.pop_back();
dq.push_back({x, i});
cout << dq.front().X << ' ';
}
}헙 많이 발전했다....
이제 스택 큐 관련 문제는 대충 감이 잡힌다
0x08 - 스택의 활용
3986 | 좋은 단어
아주 간단
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int ans = 0;
while (n--) {
string str;
cin >> str;
stack<char> s;
for (auto c : str) {
if (!s.empty() && s.top() == c)
s.pop();
else
s.push(c);
}
if (s.empty()) ++ans;
}
cout << ans;
}10799 | 쇠막대기
조금 복잡
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
string str;
cin >> str;
stack<char> s;
int ans = 0;
for (int i = 0; i < str.length(); ++i) {
if (str[i] == '(')
s.push(str[i]);
else {
s.pop();
if (i > 0 && str[i - 1] == ')')
++ans;
else
ans += s.size();
}
}
cout << ans;
}
2504 | 괄호의 값
분배법칙!!
ex)
(()[[]])([])이는 (()) + ([[]]) + ([]) 와 같음.
더해져야 하는 값들은 맞닿아 있는 쌍의 개수와 같음.
여는 괄호면 stack에 push하고 닫는 괄호면 stack에서 pop해야 하는 기본 원리는 같다.
대신 여기선 여는 괄호를 push할 때 곱해져야 하는 값들을 update 해가고
pop할 때는 곱해졌던 값을 다시 나눠준다
이때 맞닿아 있는 쌍인 경우엔 ans 값에 더해준다
괄호를 하나씩 읽으면서:
여는 괄호((, [)를 만나면:
- 스택에 넣기
- 현재 곱셈값 업데이트 (2배 또는 3배)
닫는 괄호(), ])를 만나면:
- 스택에서 빼기
- 만약 바로 앞 문자와 쌍을 이룬다면 → 답에 현재값 더하기
- 현재 곱셈값을 원래대로 되돌리기
#include <bits/stdc++.h>
using namespace std;
bool is_match(char a, char b) {
return (a == '[' && b == ']') || (a == '(' && b == ')');
}
bool is_open(char c) { return c == '[' || c == '('; }
int multi(char c) {
if (c == '[' || c == ']') return 3;
if (c == '(' || c == ')') return 2;
return 0;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
string str;
cin >> str;
stack<char> s;
int ans = 0, value = 1;
for (int i = 0; i < str.length(); ++i) {
// open이면 multi 곱하고 stack에 push
if (is_open(str[i])) {
value *= multi(str[i]);
s.push(str[i]);
} else { // 닫기이면
if (s.empty() ||
!is_match(s.top(), str[i])) { // 올바르지 않으면 0 리턴
cout << '0';
return 0;
} else {
if (is_match(str[i - 1], str[i]))
ans += value; // 맞쌍이면 ans 업데이트
value /= multi(str[i]);
s.pop();
}
}
}
if (!s.empty()) // ()( 인 경우를 거르기 위함
cout << '0';
else
cout << ans;
}꽤 까다롭...
