๋ฌธ์
2812๋ฒ: ํฌ๊ฒ ๋ง๋ค๊ธฐ
N์๋ฆฌ ์ซ์๊ฐ ์ฃผ์ด์ก์ ๋, ์ฌ๊ธฐ์ ์ซ์ K๊ฐ๋ฅผ ์ง์์ ์ป์ ์ ์๋ ๊ฐ์ฅ ํฐ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
www.acmicpc.net
์ฝ๋
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, K; cin>>N>>K;
string num; cin>>num;
stack<char> st;
int remove_cnt = 0;
int i=0;
for(i; i<N; i++){
if(st.empty()) st.push(num[i]);
else if(st.top()>num[i]) st.push(num[i]);
else{
while(true){
if(!st.empty() && num[i]>st.top()){
if(remove_cnt == K) break;
st.pop();
remove_cnt++;
}
else break;
}
st.push(num[i]);
}
}
string ans = "";
while(!st.empty()){
ans += st.top();
st.pop();
}
reverse(ans.begin(), ans.end());
ans = ans.substr(0, N-K);
cout<<ans;
}
ํ์ด
stack์ ํ์ฉํ์ฌ ํด๊ฒฐํ์ต๋๋ค.
- ์ด์ ์ ์ซ์๋ณด๋ค ํ์ฌ์ ๊ฐ์ด ํฌ๋ค๋ฉด ํ์ฌ๋ณด๋ค ๊ฐ์ฅ ํฐ ๊ฐ์ด ๋์ค๊ธฐ ์ ๊น์ง ์คํ์ ๋ชจ๋ ๊ฐ๋ค์ ์ง์๋๋ค.
- ์ด์ ์ ์ซ์๊ฐ ํ์ฌ์ ๊ฐ๋ณด๋ค ํฌ๋ค๋ฉด ํ์ฌ์ ๊ฐ์ ์ถ๊ฐํฉ๋๋ค.
- ์คํ์ ๋ฌธ์์ด์ 0, n-k ๊ธธ์ด๊น์ง ์ถ๋ ฅํฉ๋๋ค.
์ด๋ฏธ k๊ฐ๋ฅผ ์ ๊ฑฐํ์์๋ ๋ถ๊ตฌ ํ๊ณ 3๋ฒ ์์ ์ ํ๋ ์ด์ ๋ ์๋์ ๊ฐ์ด ํฌ๊ธฐ๊ฐ ๊ฐ์ ์ซ์๋ง ์์ด์ ์ ๋ถ ์คํ์ push ๋ ๊ฒฝ์ฐ๊ฐ ์๊ธฐ ๋๋ฌธ์ ๋๋ค.
2 1
1 1
'Algorithm ๐ง๐ปโ๐ป > ๋ฐฑ์ค(BOJ)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค,c++] 19542๋ฒ - ์ ๋จ์ง ๋๋ฆฌ๊ธฐ (0) | 2022.08.14 |
---|---|
[๋ฐฑ์ค,c++] 2250๋ฒ - ํธ๋ฆฌ์ ๋์ด์ ๋๋น (0) | 2022.08.14 |
[๋ฐฑ์ค,c++] 19637๋ฒ - IF๋ฌธ ์ข ๋์ ์จ์ค (0) | 2022.08.02 |
[๋ฐฑ์ค,c++] 13164๋ฒ - ํ๋ณต ์ ์น์ (0) | 2022.07.27 |
[๋ฐฑ์ค,c++] 2138๋ฒ - ์ ๊ตฌ์ ์ค์์น (0) | 2022.07.27 |
[๋ฐฑ์ค,c++] 1167๋ฒ - ํธ๋ฆฌ์ ์ง๋ฆ (0) | 2022.07.26 |
๋๊ธ