10773번: 제로
첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경
www.acmicpc.net
<풀이>
1. 정수를 입력받는다.
2. 입력받은 수가 0일 경우, 가장 최근에 넣었던 수를 지운다.
3. 남아있는 모든 수의 합을 출력한다.
<해법>
1. 가장 최근에 넣었던 수를 지우는 방법
=> 후입선출 특징을 가진 자료구조(스택)를 사용하면 쉽게 풀 수 있습니다. 저는 벡터를 사용하였습니다.
|
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 <vector>
using namespace std;
int k;
vector<int> v;
int answer = 0;
int main() {
//입력
cin >> k;
for (int i = 0; i < k; i++) {
int tmp;
cin >> tmp;
//0일 경우 가장 최근에 담은 수 빼기
if (tmp == 0) {
v.pop_back();
}
//0이 아닌 경우 담기
else {
v.push_back(tmp);
}
}
//담긴 수 모두 더하기
for (int i = 0; i < v.size(); i++) {
answer += v[i];
}
//출력
cout << answer;
}
|
후입선출 자료구조에 대해 알아볼 수 있는 문제였습니다.
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [C++] 백준 1120 - 문자열 (0) | 2021.01.03 |
|---|---|
| [C++] 백준 4949 - 균형잡힌 세상 (0) | 2021.01.01 |
| [C++] 백준 1764 - 듣보잡 (0) | 2021.01.01 |
| [C++] 백준 2636 - 치즈 (0) | 2020.12.28 |
| [C++] 백준 2941 - 크로아티아 알파벳 (0) | 2020.12.27 |