문제 풀이 강의라서 강의를 듣기 전에 먼저 문제를 풀었다. 어떻게 풀었냐에 따라 3가지 기준으로 표시를 남겨서, 나중에 복습할 때 활용하고자 한다.
low: 솔루션이 떠올라서 답을 풀었다.
mid: 솔루션이 떠오르지 않아 강의를 참고해 답을 풀었다.
high: 솔루션이 떠오르지 않아 강의를 봤는데도 아리까리 해서 정답 코드를 참조했다.
+ 그리고 스스로에게 다시 한번 당부. 방법론은 이해 했으나 사소한 실수로 인한 런타임 에러 등으로 시간 낭비를 할 필요는 굳이 없는 것 같다. 차근차근 체크를 해도 도저히 영문을 모르겠다 싶으면 그냥 정답 코드를 참고하고, 다시 풀어보도록 하자.
연습문제 정리 시작!
-
* 단어 뒤집기2 (low): 단어 뒤집기 업그레이드 버전. 괄호 안의 단어는 안 뒤집는 조건이 추가 됐다.
일단 내가 먼저 풀어봤다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include <iostream>
#include <string>
#include <stack>
using namespace std;
stack<char> s;
void rev();
int main()
{
string str;
getline(cin, str);
str += '\n';
int cnt = 0;
while (cnt < str.size())
{
if (str[cnt] == ' ') {
rev();
cout << ' ';
}
else if (str[cnt] == '<') {
rev();
while (str[cnt] != '>') {
cout << str[cnt];
cnt += 1;
}
cout << str[cnt];
cnt += 1;
continue;
}
else if (str[cnt] == '\n') {
rev();
}
else {
s.push(str[cnt]);
}
cnt++;
}
return 0;
}
void rev()
{
if (!s.empty()) {
while (!s.empty()) {
cout << s.top();
s.pop();
}
}
return;
}
|
cs |
괄호를 처리하는 과정이 좀 번거로운데 정답이긴 하다.
정답 코드가 좋아서 같이 올린다. bool 변수 하나만 추가해도 훨씬 깔끔해진다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <iostream>
#include <string>
#include <stack>
using namespace std;
stack<char> s;
void print();
int main()
{
string str;
bool tag = false;
getline(cin, str);
for (char ch : str) {
if (ch == '<') {
print();
tag = true;
cout << ch;
}
else if (ch == '>') {
tag = false;
cout << ch;
}
else if (tag) {
cout << ch;
}
else {
if (ch == ' ') {
print();
cout << ch;
}
else
s.push(ch);
}
}
print();
cout << '\n';
return 0;
}
void print()
{
if (!s.empty()) {
while (!s.empty()) {
cout << s.top();
s.pop();
}
}
}
|
cs |
- 14: bool 변수를 써서 현재 단어가 괄호 안에 있는지 확인한다.
- 18: for문을 이렇게 만드니 코드가 훨씬 보기 좋다. 기억 해뒀다가 나중에 또 써먹자.
* 쇠막대기 (low): 레이저로 쇠막대기를 자를 때 몇 조각이 나는지 구하는 문제. 스택을 사용해서 풀었던 괄호 문제를 활용하면 쉽게 풀 수 있다.
10799번: 쇠막대기
여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저�
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main()
{
string str;
stack<char> s;
int sum = 0;
getline(cin, str);
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(') {
s.push(str[i]);
}
else {
s.pop();
if (str[i - 1] == '(') {
sum += s.size();
}
else sum += 1;
}
}
cout << sum;
return 0;
}
|
cs |
- 25: 괄호가 끝나는 부분이 레이저가 아닌 쇠막대기의 끝일 때, 한 조각이 더 추가된다.
* 오큰수 (high): 여기서 많이 헤맸다. 뭔가 풀릴듯 안 풀리더라.. 입력 범위가 크기 때문에 단순하게 생각해서는 시간 초과로 못 푼다. 주어진 조건과 반대로 생각해야 풀 수 있는 문제다.
17298번: 오큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n), nge(n);
stack<int> s;
for (int i=0; i<n; i++)
cin >> a[i];
s.push(0);
for (int i=1; i<n; i++) {
if (s.empty())
s.push(i);
while(!s.empty() && a[s.top()] < a[i]) {
nge[s.top()] = a[i];
s.pop();
}
s.push(i);
}
while(!s.empty()) {
nge[s.top()] = -1;
s.pop();
}
for (int i=0; i<n; i++)
cout << nge[i] << ' ';
cout << '\n';
return 0;
}
|
cs |
- 18: 첫 항의 인덱스는 비교 대상이 없으므로 바로 스택에 넣는다.
- 21: 스택이 비어있다면, 마지막 항의 순서이므로 마지막 항의 인덱스를 스택에 넣어준다.
- 23: 아직 오큰수를 모르는 스택의 top에 위치한 인덱스의 값보다 현재 인덱스의 값이 크면, 스택의 top에 위치한 인덱스 값의 오큰수는 현재 인덱스의 값이다.
- 30: 스택에 남아 있는 인덱스의 값은 오큰수가 없는 애들이다.
* 오등큰수(mid): 이번엔 크기가 아니라 등장 횟수로 비교한다. 비슷하게 풀 수 있는데, 인덱스 값을 잘 생각해서 넣자. 어이 없이 많이 헤맸다
17299번: 오등큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int f[1000001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n + 1);
vector<int> ngf(n + 1);
stack <int> s;
for (int i = 1; i <= n; i++) {
cin >> a[i];
f[a[i]] += 1;
}
s.push(1);
for (int i = 2; i <= n; i++) {
if (s.empty())
s.push(i);
while (!s.empty() && f[a[s.top()]] < f[a[i]]) {
ngf[s.top()] = a[i];
s.pop();
}
s.push(i);
}
while (!s.empty()) {
ngf[s.top()] = -1;
s.pop();
}
for (int i = 1; i <= n; i++)
cout << ngf[i] << ' ';
cout << '\n';
return 0;
}
|
cs |
-7: 숫자 별로 카운트 하기 편하게 최대크기 +1로 만들어주자.
-32~33: 인덱스가 어떤 식으로 적용되는지 정확히 이해하지 못 하면 결과가 꼬인다..
-
이렇게 또 정리를 해봤다. 문제를 많이 풀어서 머리가 말랑말랑 해지는 느낌이다.
곧 잘 푸는 모습에 스스로 만족하기도, 어이 없이 헤매는 모습에 스스로 실망하기도 하면서 풀어봤다.
빡세게 하다가 지치지 말고, 꾸준히 하자. 꾸준히!
'알고리즘 > 백준 알고리즘 강의' 카테고리의 다른 글
| 백준 알고리즘 기초 - 수학1 (연습) (0) | 2020.07.07 |
|---|---|
| 백준 알고리즘 기초 - 수학1 (0) | 2020.07.07 |
| 백준 알고리즘 기초 - 자료구조1 (큐, 덱) (0) | 2020.07.06 |
| 백준 알고리즘 기초 - 자료구조1 (스택) (0) | 2020.07.04 |
| 백준 알고리즘 기초 - 알고리즘 시작 (0) | 2020.07.04 |
