그냥 이 표를 외우는 게 빠를 것 같다.
시간복잡도 공간복잡도 파악
아 맞다 이런 게 있었지
c++에서 reference로 인자를 넘기면 복사 비용이 발생하지 않는다.
아 맞다. v1.size()는 unsigned long이라 -1을 하게 되면 overflow가 발생할 수 있다. size()가 0인데 -1을 하면 -1이 되는 것이 아니라 overflow가 된 값으로 넘어가니까 무한루프가 발생할 수 있다. 주의!
0x03
2577
초간단 문제
1475
아 바보
틀린 코드
#include <bits/stdc++.h>
using namespace std;
bool use[11];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
long long ans = 1;
while (n > 0) {
int k = n % 10;
n /= 10;
if (k == 9 && use[9])
k = 6;
else if (k == 6 && use[6])
k = 9;
if (!use[k])
use[k] = 1;
else {
fill(use, use + 10, 0);
use[k] = 1;
ans++;
}
}
cout << ans;
}
접근법이 잘못 됐었다.
1을 이미 썼는데 다음에 또 1을 써야 하는 경우
아예 스티커를 새로 가져와서 1을 쓰게 했는데
그렇게 되면 안 썼던 다른 번호들을 사용하지 못 하게 된다.
예를 들어 11234의 경우
스티커 하나로 1,2,3,4를 쓰고 새로운 스티커로 1을 한 번 더 쓰면 되니까 스티커가 2개만 필요한데
저 방법으로 하면
정답 코드
#include <bits/stdc++.h>
using namespace std;
int cnt[11];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
while (n > 0) {
cnt[n % 10]++;
n /= 10;
}
cnt[6] = (cnt[6] + cnt[9] + 1) / 2;
cnt[9] = cnt[6];
cout << *max_element(cnt, cnt + 10);
}int 나누기 2 주의
/2 할 때 처음에 그냥 (cnt[6] + cnt[9]) / 2로 해서 틀렸었다;;
int형이라 5/2 같은 경우 2가 나와 버린다.
제대로 계산하려면 (a + b + 1) / 2를 해줘야 한다.
3273
#include <bits/stdc++.h>
using namespace std;
bool cnt[2000001];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n, x;
cin >> n;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
cnt[k] = 1;
}
cin >> x;
int ans = 0;
for (int i = 1; i < (x + 1) / 2; ++i) {
if (cnt[i] && cnt[x - i]) ans++;
}
cout << ans;
}"서로 다른 양수 "
처음엔 cnt를 int로 하고 count를 해줬었는데
서로 다른 양수기 때문에 한 번 이상 나올 수 없다. 그래서 bool로 선언해주면 된다.
0x04
5397
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
list<char> L;
string str;
auto it = L.begin();
cin >> str;
for (auto c : str) {
if (c == '<') {
if (it != L.begin()) --it;
} else if (c == '>') {
if (it != L.end()) ++it;
} else if (c == '-') {
if (it != L.begin()) it = L.erase(--it);
} else
L.insert(it, c);
}
for (auto c : L) cout << c;
cout << '\n';
}
}주의
it = L.erase(--it);
L.erase(--it)를 하면 it 위치에 있던 노드가 지워져 버린다. 올바르지 않는 곳을 가리키게 됨.
그래서 it = L.erase(--it)를 해서 지웠던 곳 다음 위치를 가리키는 iterator를 반환받아 업데이트 시켜줘야 함.
1158
ver1
#include <bits/stdc++.h>
using namespace std;
int num[5001];
int cnt;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
list<int> L;
for (int i = 1; i <= n; ++i) L.push_back(i);
auto it = L.begin();
while (!L.empty()) {
for (int i = 0; i < k - 1; ++i) {
++it;
if (it == L.end()) it = L.begin();
}
num[cnt++] = *it;
it = L.erase(it);
if (it == L.end()) it = L.begin();
}
cout << '<';
for (int i = 0; i < n - 1; ++i) cout << num[i] << ", ";
cout << num[n - 1] << '>';
}
ver2
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
queue<int> Q;
for (int i = 1; i <= n; i++) Q.push(i);
cout << '<';
while (!Q.empty()) {
for (int i = 0; i < k - 1; i++) {
Q.push(Q.front());
Q.pop();
}
cout << Q.front();
Q.pop();
if (Q.size()) cout << ", ";
}
cout << '>';
}바킹독님 풀이 보니까 훨씬 간단했다.
큐를 이용해서 앞에 있는 원소를 뒤로 계속 넣어주면
ver1처럼 end()일 때 begin()으로 돌아가고 이럴 필요가 없다.
10773
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int k;
vector<int> v;
cin >> k;
for (int i = 0; i < k; ++i) {
int t;
cin >> t;
if (t == 0)
v.pop_back();
else
v.push_back(t);
}
long ans = 0;
while (!v.empty()) {
ans += v[v.size() - 1];
v.pop_back();
}
cout << ans;
}그냥 벡터로 풀었다.
0x05
1874
#include <bits/stdc++.h>
using namespace std;
stack<int> s;
string ans;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int cnt = 1;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
while (cnt <= k) {
s.push(cnt++);
ans += "+\n";
}
if (s.top() != k) {
cout << "NO";
return 0;
}
s.pop();
ans += "-\n";
}
cout << ans;
}2493
ver1
#include <bits/stdc++.h>
using namespace std;
stack<pair<int, int> > s;
int ans[500001];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
int t;
cin >> t;
while (!s.empty() && s.top().first < t) {
int idx = s.top().second;
s.pop();
if (!s.empty()) ans[idx] = s.top().second;
}
s.push({t, i});
}
while (!s.empty()) {
int idx = s.top().second;
s.pop();
if (!s.empty()) ans[idx] = s.top().second;
}
for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
}예를 들어
5 -> 4 -> 2 -> 3 입력이 들어왔을 때
3이 들어온 시점에서 2는 남아 있을 필요가 없어진다.
왜냐하면 이후에 들어오는 2보다 큰 입력들이 3에 가로막히게 되기 때문이다.
그래서 stack에 원소를 저장하다 내림차순이 깨지는 순간
현재 입력값보다 작은 원소들을 pop하고, ans에 답을 저장했었다.
그런데 불필요 했다.
ver2
#include <bits/stdc++.h>
using namespace std;
stack<pair<int, int> > s;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
s.push({100000001, 0});
for (int i = 1; i <= n; ++i) {
int t;
cin >> t;
while (s.top().first < t) s.pop();
cout << s.top().second << ' ';
s.push({t, i});
}
}아까는 ans 배열에 저장하고 마지막에 배열을 출력하게 했었다.
그런데 그럴 필요가 없다. 입력을 받을 때마다 s.top()을 출력해주면 된다.
현재 탑보다 낮은 탑들은 pop() 해가다 높은 탑을 만나면 멈추기 때문에
s.top()이 정답이다.
그리고 나서 스택에 push()를 해주면 된다.
그리고 저렇게 정답을 바로바로 출력해줬다면 pop() 하는 탑들은 이전에 이미 정답이 출력된 상태일 것이기 때문에 그냥 pop()만 해주면 된다.
추가로 0번 인덱스에 높이 제한을 초과하는 탑을 넣어준다.
1번까지 어떤 탑에도 걸리지 않는 탑은 0번 탑에 걸리게 되고
스택에는 항상 0번 탑이 남아있게 되어 스택이 empty()일 일이 없어서 조건문이 간결해진다.
6198
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
stack<int> s;
cin >> n;
long ans = 0;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
while (!s.empty() && s.top() <= k) s.pop();
ans += s.size();
s.push(k);
}
cout << ans;
}위에랑 비슷하게 풀면 된다.
스택에는 나를 볼 수 있는 빌딩들만 들어있게 하면 된다.
그래서 나보다 작은 애들은 pop하고
stack size만큼 ans에 더하면 된다.
나보다 작은 애들을 아예 pop 해도 되는 이유는
나보다 작다면 어차피 다음 입력들도 나에게 걸려서 보지 못할 애들이기 때문이다.
스택은 내림차순 정렬이된 상태이게 된다.
그렇기 때문에 while문에서 단순히 s.top() <= k인 동안 pop을 해주면 되는 것이다.
17298
#include <bits/stdc++.h>
using namespace std;
int ans[1000001];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
fill(ans, ans + n, -1);
stack<pair<int, int> > s;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
while (!s.empty() && s.top().first < k) {
ans[s.top().second] = k;
s.pop();
}
s.push({k, i});
}
for (int i = 0; i < n; ++i) cout << ans[i] << ' ';
}
6549
틀린 내 코드
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n = 1;
while (n) {
cin >> n;
stack<pair<long, int> > s;
long ans = 0;
long min_h = 1000000001;
for (int i = 0; i < n; ++i) {
long h;
cin >> h;
min_h = min(min_h, h);
while (!s.empty() && s.top().first > h) {
int w = i - s.top().second;
ans = max(ans, w * s.top().first);
s.pop();
}
s.push({h, i});
}
s.push({0, n});
while (!s.empty()) {
int w = n - s.top().second;
ans = max(ans, w * s.top().first);
s.pop();
}
cout << max(min_h * n, ans) << '\n';
}
}
바킹독님 코드
// Authored by : haneulkimdev
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/d98aedfde0e444509de83f1a21c8ef7e
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
while (true) {
int n;
cin >> n;
if (n == 0) break;
stack<pair<int, int>> S;
long long ans = 0;
for (int i = 0; i < n; i++) {
int h;
cin >> h;
int idx = i;
while (!S.empty() && S.top().X >= h) {
ans = max(ans, 1LL * (i - S.top().Y) * S.top().X);
idx = S.top().Y;
S.pop();
}
S.push({h, idx});
}
while (!S.empty()) {
ans = max(ans, 1LL * (n - S.top().Y) * S.top().X);
S.pop();
}
cout << ans << '\n';
}
}
/*
스택에는 (높이, 해당 높이가 최초로 등장한 위치)가 저장된다. 기본적으로 스택은
높이에 대한 monotone stack으로 관리된다. 스택에서 pop이 발생할 때 마다 현재
스택의 top을 가지고 만들 수 있는 직사각형의 넓이를 계산할 수 있다.
long long으로의 형변환을 편하게 처리하기 위해 1LL을 매번 곱했고, 그냥 스택
자체를 pair<long long, long long>으로 선언해도 크게 상관 없다.
*/아... 나보다 큰 애들을 pop해가야 한다는 것과
i를 저장해서 넓이를 계산할 때 쓰일 너비를 구해야한다는 것도 맞았는데
나보다 같은 애들도 pop하고 pop한 원소의 index들로 새로 저장할 index를 업데이트 해야한다는 것을 생각해내지 못했다.
왜냐하면 나를 가지고 만들 수 있는 직사각형의 넓이는 내가 pop한 이전 원소들부터 쭉 이어질 수 있기 때문에 index를 pop한 원소들의 index로 업데이트 해주면 되는 것이었다.
스택 문제인지 어떻게 파악할 수 있을까
일단 지금 생각으로는
스택을 적용할지 안 할지를 떠올리려면
-
가장 직관적인 풀이법 떠올리기 -> 보통 이중 반복문. 소요. 그런데 시간은 1초 이내. 그럼 시간 초과
-
시간을 줄여야 하는데 누적합 같은 게 아니다, 점화식이 있지 않다, 처음 만나는, 가장 가까운 이런 표현이 들어 있다 -> 스택 풀이 고려하기
스택 문제는 스택을 사용해야하는지만 파악이 되고 나면 진짜 풀이가 쉬운 것 같다.
