정화 코딩
[ICPC Sinchon] 25W 알고리즘 캠프 초급 강의 2회차 과제 에디토리얼 본문
2회차 - 선형 자료구조, 제곱 정렬
</1406> 에디터
https://www.acmicpc.net/problem/1406
#include <iostream>
#include <list>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
list<char> li(s.begin(), s.end());
int n;
cin >> n;
// 최초의 커서 위치는 문장의 맨 뒤
auto cur = li.end();
while (n--) {
char cmd;
cin >> cmd;
if (cmd == 'L') {
// 커서가 맨 앞이 아니라면 한 칸 앞으로 이동
if (cur != li.begin()) cur--;
} else if (cmd == 'D') {
// 커서가 맨 뒤가 아니라면 한 칸 뒤로 이동
if (cur != li.end()) cur++;
} else if (cmd == 'B') {
// 커서가 맨 앞이 아니라면 바로 앞 문자 하나 삭제
if (cur != li.begin()) li.erase(prev(cur));
} else if (cmd == 'P') {
// 커서 바로 앞에 문자 하나 추가
char c;
cin >> c;
li.insert(cur, c);
}
}
for (auto i = li.begin(); i != li.end(); i++) cout << *i;
cout << '\n';
}
</9012> 괄호
https://www.acmicpc.net/problem/9012
#include <iostream>
#include <stack>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
string ans = "YES\n";
stack<char> stk;
string s;
cin >> s;
for (char c: s) {
// 왼쪽 괄호면 스택에 넣기
// 오른쪽 괄호면 스택에서 맨 위 하나를 꺼내서 확인
// 꺼낼 수 없으면 (오른쪽 괄호가 남으면) "NO"
if (c == '(') {
stk.push(c);
} else if (c == ')') {
if (stk.empty()) {
ans = "NO\n";
break;
} else {
stk.pop();
}
}
}
// 스택이 비어있지 않다면 (왼쪽 괄호가 남으면) "NO"
if (!stk.empty()) ans = "NO\n";
cout << ans;
}
}
</24511> queuestack
https://www.acmicpc.net/problem/24511
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// n: 자료구조의 개수
int n;
cin >> n;
// qn: 큐의 개수
int qn = 0;
// isQue: 특정 위치가 큐인지 저장하는 용도의 배열
// (초기 원소 하나를 삽입할 때 사용됨.)
vector<bool> isQue(n, false);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
// x가 0, 즉 큐일 때만 체크하고 개수 카운트
if (x == 0) {
isQue[i] = true;
qn++;
}
}
// q: 큐의 배열
vector<queue<int>> q(qn);
// idx: 큐 배열의 인덱스
int idx = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
// 큐일 때만 초기 원소 삽입
if (isQue[i]) q[idx++].push(x);
}
// m: 삽입할 수열의 길이
int m;
cin >> m;
while (m--) {
int x;
cin >> x;
// x를 삽입하고 새로운 반환값을 x에 넣는 것을 반복
for (int i = 0; i < qn; i++) {
q[i].push(x);
x = q[i].front();
q[i].pop();
}
cout << x << ' ';
}
cout << '\n';
}이렇게 풀면 시간 초과가 납니다…
시간을 더 줄이기 위해서는 여러 큐가 마치 하나의 큐로 동작한다는 것을 이해해야 합니다.
이는 큐의 FIFO 성질 때문입니다.
말로 이해가 잘 되지 않는다면 아래 그림을 참고해주세요.
수정된 코드는 아래와 같습니다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// n: 자료구조의 개수
int n;
cin >> n;
// q: 큐
queue<int> q;
vector<int> a(n);
vector<int> b(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
for (int i = n - 1; i >= 0; i--) {
if (a[i] == 0) q.push(b[i]);
}
// m: 삽입할 수열의 길이
int m;
cin >> m;
while (m--) {
int x;
cin >> x;
q.push(x);
cout << q.front() << ' ';
q.pop();
}
cout << '\n';
}
</2493> 탑
https://www.acmicpc.net/problem/2493
현재 탑에서 발사하는 레이저가 신호를 수신하는 탑은 현재 탑에서 왼쪽으로 이동하면서 볼 때, 자신보다 높이가 높은 탑 중 처음 만나는 탑입니다.
좀 더 풀어서 설명하면, 우선 탑은 레이저 신호를 왼쪽으로 발사하기 때문에 현재 탑에서 시작하여 왼쪽으로 이동하면 살펴보아야 합니다. 현재 탑보다 낮은 탑들은 신호가 닿지 않기 때문에 무시하고, 현재 탑보다 높은 탑들 중 처음으로 만나는 탑이 현재 탑의 신호를 수신하게 됩니다.
이해를 돕기 위해 그림으로 그려보았습니다.
이 아이디어를 사용하여 스택을 관리하면 됩니다. 코드와 그에 대한 간단한 설명은 아래에 있습니다.
#include <iostream>
#include <stack>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
stack<pair<int, int>> s;
for (int i = 1; i <= n; i++) {
// x: 현재 탑의 높이
int x;
cin >> x;
// 현재 탑 높이보다 낮은 것들 스택에서 전부 빼기
while (!s.empty() && s.top().second < x) {
s.pop();
}
// 현재 탑에서 발사한 레이저 신호를 수신하는 탑은
// 현재 탑에서 왼쪽으로 이동하면서 볼 때, 자신보다 높이가 높은 탑 중 처음 만나는 탑
if (s.empty()) cout << 0 << ' ';
else cout << s.top().first << ' ';
s.emplace(i, x);
}
cout << '\n';
}
</30885> Φ²
https://www.acmicpc.net/problem/30885
#include <iostream>
#include <list>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
list<pair<long long, int>> li;
int n;
cin >> n;
for (int i = 1; i < n + 1; i++) {
int x;
cin >> x;
li.emplace_back(x, i);
}
while (li.size() > 1) {
for (auto i = li.begin(); i != li.end(); i++) {
long long a = i->first; // 현재 가리키고 있는 미생물의 크기
long long newa = a; // 새로운 미생물의 크기 (흡수 후)
// 첫 번째 미생물이 아닐 때만
if (i != li.begin()) {
auto prev_i = prev(i);
// 바로 앞 미생물이 작거나 같으면
if (prev_i->first <= a) {
newa += prev_i->first;
// i는 계속 현재 미생물을 가리키도록 유지
i = li.erase(prev_i);
}
}
// 마지막 미생물이 아닐 때만
if (next(i) != li.end()) {
auto next_i = next(i);
// 바로 뒤 미생물이 작거나 같으면
if (next_i->first <= a) {
newa += next_i->first;
// i는 계속 현재 미생물을 가리키도록 유지
i = li.erase(next_i);
i--;
}
}
// 미생물의 크기 갱신
i->first = newa;
}
}
auto ans = li.begin();
cout << ans->first << '\n' << ans->second << '\n';
}우선 모든 미생물을 연결 리스트에 담습니다. first에는 미생물의 크기를, second에는 미생물의 초기 위치를 넣었습니다.
그 후 미생물이 한 마리만 남을 때까지 다음을 반복합니다.
1. 앞에 미생물이 존재할 경우, 바로 앞 미생물이 작거나 같으면 흡수합니다. 이 때, 바로 앞 미생물의 바로 다음 미생물이 현재 미생물이므로 i는 erase에서 그대로 받습니다.
2. 뒤에 미생물이 존재할 경우, 바로 뒤 미생물이 작거나 같으면 흡수합니다. 이 때, 바로 뒤 미생물의 바로 다음 미생물은 현재 미생물 기준 바로 뒤 미생물이 되므로 i는 erase에서 받은 후 1을 빼줍니다.
3. 미생물의 크기를 흡수 후의 크기로 갱신해줍니다.
- erase 함수는 list에서 해당 iterator 위치의 원소를 삭제하고 원래 위치의 다음 원소의 iterator를 반환합니다.
- prev 함수는 list에서 해당 iterator 위치의 원소의 바로 앞 원소의 iterator를 반환합니다.
- next 함수는 list에서 해당 iterator 위치의 원소의 바로 뒤 원소의 iterator를 반환합니다.
- prev, next 함수를 사용할 때는 범위가 벗어나 정의되지 않은 동작(Undefined Behavior)이 발생하지 않도록 주의해야 합니다.
'PS' 카테고리의 다른 글
| [ICPC Sinchon] 25W 알고리즘 캠프 초급 강의 4회차 과제 에디토리얼 (0) | 2025.03.05 |
|---|---|
| [ICPC Sinchon] 25W 알고리즘 캠프 초급 강의 3회차 과제 에디토리얼 (0) | 2025.03.05 |
| [C++] 기념품 (백준 12873번) (0) | 2025.03.04 |
| [C++] 행렬 제곱 (백준 10830번) (0) | 2025.01.23 |
| [C++] 에디터 (백준 1406번) (2) | 2025.01.22 |
