✍ 문제
나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.
재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.
재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.
재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!
✍ 입력
첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)
이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.
정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.
✍ 출력
재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.
✅ 코드
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int test_case;
int result = 0;
stack<int> s;
cin >> test_case;
for (int i = 0; i < test_case; i++) {
int val;
cin >> val;
if (val == 0) s.pop();
else s.push(val);
}
int size = s.size();
for (int i = 0; i < size; i++) {
result += s.top();
s.pop();
}
cout << result;
}✅ 코드풀이
10773번의 핵심 포인트는 스택을 이용하는 것이다.
문제 상황이 스택의 LIFO 성질을 이용하고 있으며 (입력으로 0이 들어오면 가장 최근에 들어온 수가 지워진다 = Last In First Out), c++의 STL에 정의되어 있는 stack을 사용하면 매우 간단하게 해결할 수 있다!
✔️입출력 속도
온라인 저지 사이트에서 문제를 풀다보면 시간 초과가 뜨는 경우가 있다.
그럴 때에 아래 두 줄을 코드에 추가해주면 시간 초과 문제가 해결되기도 한다. (100% 해결은 당연히 X)
ios::sync_with_stdio(false);
cin.tie(0);
1. ios::sync_with_stido(false);
C와 C++ 표준 stream의 동기화를 비활성화 시키는 코드이다.
동기화가 되어있는 경우, cin과 scanf, cout과 printf를 혼용하여 사용하는 것이 가능하다.
하지만 위의 코드를 통해 동기화를 비활성화 시키면 c++ 스타일의 코드만 사용이 가능한 대신, 기존 동기화 과정에서 소모되던 시간이 절약되어 입출력 속도가 감소한다.
2. cin.tie(0)
cin과 cout을 untie 해주는 코드이다.
기본적으로 cin과 cout은 묶여있고 , 묶여있는 스트림들은 한 스트림이 다른 스트림에서 IO 작업을 수행하기 전에 자동으로 버퍼를 비워줌을 보장한다.
cout << "이름이 무엇인가요?: ";
cin >> name;1) cin.tie(0) 를 사용하지 않는 경우
cin과 cout은 묶여있기 때문에 반드시 "이름이 무엇인가요?:"가 출력된 이후에 이름을 입력할 수 있다.
2) cin.tie(0) 를 사용하는 경우
cin과 cout이 묶여있지 않기 때문에 출력이 되기 전에 이름을 입력할 수 있다.
기본적으로 cin으로 입력을 받을 때 출력 버퍼를 비우게 된다. 하지만 알고리즘 문제를 풀 때에는 화면에 바로 보여지는 것은 중요하지 않다. 따라서 입출력을 여러 번 반복해야 하는 경우 cin과 cout의 묶음을 풀어서 버퍼를 비우는 데 (flush) 소모되는 시간을 줄이는 것이 좋다.
❗ 실제로 위 두 줄을 추가했을 때, 기존의 28ms에서 8ms로 시간이 단축되었다.
✔️endl vs \n
입출력 속도에 대해 찾아보다보니 endl과 \n의 사용을 비교해놓은 글들이 많았다.
평소에 아무 생각 없이 endl을 사용했었는데 별로 좋지 않은 습관임을 알게되었다 🙀
endl과 \n모두 개행을 해준다는 것에서 용도는 동일하다.
하지만 개행을 할 때, endl은 출력버퍼를 비우고 \n은 그렇지 않다는 차이가 있다.
이러한 특성으로 인해 당연히 속도 면에서도 차이가 난다.
출력버퍼를 비우는 endl은 \n에 비해 느리다.
따라서 대부분의 알고리즘 문제 풀이에서는 \n을 사용하는 것이 속도면에서 유리하다!
(문제에 따라 출력버퍼를 즉시 비워야하는 경우도 존재할 것 같은데 정확히 어떤 경우에 endl을 사용해야 하는지는 아직 모르겠다... 더 찾아보고 추가하겠다.)
