바로 이전 글에서.. 미련함에서 벗어나자고 했건만.. 아직 한참 멀었다.. 오답 수집가냐 진짜
떠오르는대로 꾸역꾸역 코딩을 하다보니 이런 일이 벌어졌다. 구조를 구상하고, 정리가 됐을 때 코딩을 시작해라 좀.
저렇게 시간 낭비하는 건 너무 아깝다.. 됐고 스택 공부한 거나 정리 해보자.
-
* 스택: 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조. 제일 위(top)에 뭐가 있는지가 관심사다.
- top에 추가하는 것을 push, top에서 빼는 것을 pop이라고 한다.
- LIFO (Last In First Out) 구조다. 제일 마지막에 들어온 사람이 제일 먼저 나가야 된다. (짬 대우)
* 스택 구현: 일단 STL 없이 한번 구현 해봤다.
10828번: 스택
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,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
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include <iostream>
#include <string>
int stack[10000], size = 0;
int empty()
{
if (!size)
return 1;
return 0;
}
void push(int x)
{
stack[size] = x;
size += 1;
}
int pop()
{
if (empty())
return -1;
size -= 1;
return stack[size];
}
int top()
{
if (empty())
return -1;
return stack[size - 1];
}
int main()
{
int n;
std::string cmp;
std::cin >> n;
while (n--)
{
std::cin >> cmp;
if (cmp == "push") {
int p;
std::cin >> p;
push(p);
}
else if (cmp == "pop") {
std::cout << pop() << '\n';
}
else if (cmp == "size") {
std::cout << size << '\n';
}
else if (cmp == "empty") {
std::cout << empty() << '\n';
}
else if (cmp == "top") {
std::cout << top() << '\n';
}
}
return 0;
}
|
cs |
- 귀찮지만 이렇게 구현 해보는 게 확실히 구조를 이해하는데 효과적인 것 같다.
- 하지만 이걸 언제 다 구현하고 있으랴.. STL을 적극 활용하자. STL을 활용해서 같은 문제를 풀어봤다.
|
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
|
#include <iostream>
#include <stack>
#include <string>
int main()
{
std::stack<int> st;
int n;
std::string cmp;
std::cin >> n;
while (n--)
{
std::cin >> cmp;
if (cmp == "push") {
int p;
std::cin >> p;
st.push(p);
}
else if (cmp == "pop") {
if(st.empty())
std::cout << -1 << '\n';
else {
std::cout << st.top() << '\n';
st.pop();
}
}
else if (cmp == "size") {
std::cout << st.size() << '\n';
}
else if (cmp == "empty") {
if (st.empty())
std::cout << 1 << '\n';
else
std::cout << 0 << '\n';
}
else if (cmp == "top") {
if (st.empty())
std::cout << -1 << '\n';
else
std::cout << st.top() << '\n';
}
}
return 0;
}
|
cs |
- 함수를 일일이 구현할 필요가 없어서 훨씬 수월하다. 더 복잡한 것 같기도..?
- 구글링을 하다가 using namespace std;를 안 쓰는 게 좋다는 정보를 보고 저렇게 했는데.. 뭐 딱히 내 수준에서는 문제가 생길 것 같지도 않고.. 백준님도 쓰시니까 그냥 namespace 쓸란다. 그걸 고려 해야하는 수준까지 달려~~~
* 단어 뒤집기 문제: 스택은 이 문제를 가장 있어 보이게 풀 수 있는 구조라더라.
9093번: 단어 뒤집기
문제 문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다. 입력 첫째 줄에 테스트 케이스의
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
|
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
cin.ignore();
while (n--)
{
string str;
getline(cin, str);
str += '\n';
stack<char>s;
for (int i = 0; i < str.size(); i++)
{
if (str[i] == ' ' || str[i] == '\n') {
while (!s.empty()) {
cout << s.top();
s.pop();
}
cout << ' ';
}
else {
s.push(str[i]);
}
}
cout << '\n';
}
return 0;
}
|
cs |
- 9~10: C++11 이상 버전에서만 적용되는 것 같다.
- 14: cin.ignore() 이 놈은 19에 getline 때문에 추가되었다. (안 써주면 13에서 친 엔터를 getline에서 그대로 받는다)
- 20: string형의 끝에는 '\n'가 없기 때문에 마지막을 식별하기 위해서 추가한다.
* 괄호 문제: 가능한 괄호 형식인지 판별하는 문제다.
9012번: 괄호
문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)��
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
|
#include <iostream>
#include <string>
using namespace std;
string vps(string s)
{
int cnt = 0;
for (int i=0; i<s.size(); i++)
{
if (s[i] == '(')
cnt+=1;
else
cnt-=1;
if (cnt < 0)
return "NO";
}
if (!cnt) return "YES";
else return "NO";
}
int main()
{
int n;
string str;
cin >> n;
cin.ignore();
for (int i=0; i<n; i++)
{
getline(cin, str);
cout << vps(str) << '\n';
}
return 0;
}
|
cs |
- 왼쪽 괄호는 스택에 저장 -> 오른쪽 괄호와 매칭될 때마다 스택에서 제거 -> 왼쪽과 오른쪽 괄호가 모두 소진 되어야 올바른 구조다.
- 스택의 원리를 사용하지만 굳이 스택 구조를 사용하지 않고 풀 수 있는 문제였다.
* 스택 수열: 이게 좀 까다로웠다. 무조건 오름차순으로 입력을 받는 스택 구조에서 입력한 순서대로 수열을 만들 수 있는지를 판별하고 어떤 식으로 push & pop 해야 만들 수 있는지까지 알아내는 문제다.
1874번: 스택 수열
1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.
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
|
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main()
{
int n, m = 0;
stack <int> s;
string ans;
cin >> n;
while (n--) {
int x;
cin >> x;
if (x > m) {
while (x > m) {
s.push(++m);
ans += '+';
}
s.pop();
ans += '-';
} else {
bool valid = false;
int top = s.top();
s.pop();
ans += '-';
if (top == x)
valid = true;
if (!valid) {
cout << "NO" << '\n';
return 0;
}
}
}
for (auto x : ans) {
cout << x << '\n';
}
return 0;
}
|
cs |
- 18: x를 수열의 그 다음 순서에 들어갈 값, m을 마지막으로 스택에 들어간 값으로 생각하면, x가 m보다 클 때는 m을 x만큼 push하고 pop하면 된다.
- 25: x가 m보다 작으면 수열은 성립하지 않는다. x가 m과 같을 때는 top값이 x와 같을 때만 성립한다.
- 39: 얘도 C++11 이상에서 사용 가능하다. auto가 데이터 타입을 알아서 정해준다.
* 에디터 문제: 두개의 스택으로 나눠서 생각하면 문제가 상당히 간단해진다. 이번 챕터에 제일 멋진 문제 같다.
1406번: 에디터
문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
int main()
{
stack<char>left, right;
char str[600000];
int len, n;
scanf("%s", str);
len = strlen(str);
for (int i = 0; i < len; i++)
left.push(str[i]);
scanf("%d", &n);
while (n--)
{
char x;
scanf(" %c", &x);
if (x == 'L') {
if (!left.empty()) {
char top = left.top();
right.push(top);
left.pop();
}
}
else if (x == 'D') {
if (!right.empty()) {
char top = right.top();
left.push(top);
right.pop();
}
}
else if (x == 'B') {
if (!left.empty())
left.pop();
}
else if (x == 'P') {
char y;
scanf(" %c", &y);
left.push(y);
}
}
while (!left.empty())
{
char top = left.top();
right.push(top);
left.pop();
}
while (!right.empty())
{
char top = right.top();
printf("%c", top);
right.pop();
}
return 0;
}
|
cs |
- 18: 처음엔 커서가 맨 오른쪽에 있으니까 left에 모든 값이 들어있다.
- 26, 48: scanf를 따로 연이어 사용하면 몇 개가 씹힌(?)다. 하기 쉬운 실수이니 구분해서 인식하도록 꼭 띄워서 쓰자.
- 커서 왼쪽이 left, 오른쪽이 right라고 생각하면 술술 풀린다. 마지막엔 right로 모아서 하나씩 pop 해주면 된다.
-
정리를 하면서도 공부가 되는 것 같다. 근데 생각보다 정리 시간이 오래 걸린다.
감안해서 계획을 적절하게 수정할 필요가 있을 것 같다.
조금 천천히 가더라도 꾸준하게, 확실하게 이해하고 넘어가자!
'알고리즘 > 백준 알고리즘 강의' 카테고리의 다른 글
| 백준 알고리즘 기초 - 수학1 (연습) (0) | 2020.07.07 |
|---|---|
| 백준 알고리즘 기초 - 수학1 (0) | 2020.07.07 |
| 백준 알고리즘 기초 - 자료구조1 (연습) (0) | 2020.07.06 |
| 백준 알고리즘 기초 - 자료구조1 (큐, 덱) (0) | 2020.07.06 |
| 백준 알고리즘 기초 - 알고리즘 시작 (0) | 2020.07.04 |
