반응형
문제 출처
https://www.acmicpc.net/problem/9935
문제풀이
1. 문자열 풀이
/**
* 폭탄문자열 끝과 결과값의 끝이 같다면 폭탄문자열이 포함되어 있는지 검사한다.
* 만약 포함되어 있다면 그 문자열의 길이만큼 결과값에서 지워주면 되는 문제.
* 중간에 포함되어 있어도 일단 끝문자를 첫 기준으로 삼기 때문에 연쇄적으로 폭발시킬 수 있다.
*/
2. 스택 풀이
/**
* 아이디어는 스택에 push할때 int값을 같이 push해줘서 int값이 폭탄 문자열 길이와 같다면 pop해주는 것이다.
* 먼저 stack에 input문자열을 push한다. 이때 문자열과 현재 문자열로부터 폭탄문자열과 몇번째로 같은지 같이 push한다.
* 예시를 들어 설명하면 AWSASWA가 input이고 폭탄 문자열이 SW라고 가정한다.
* 스택에는 다음과 같이 입력될 것이다.
* (A,0) / (W,0) / (S,1) / (A,0) / (S,1) / (W,2) / (A,0)
* 이 때 폭탄문자열의 길이가 2이므로 int값이 2일때 2개만큼 pop을 해준다.
*/
소스코드
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 | #include <iostream> #include <string> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string input, bomb, result; cin>>input>>bomb; int inputSize=input.size(); int bombSize=bomb.size(); for(int i=0; i<inputSize; i++) { result.push_back(input[i]); bool searchBomb = true; if(result.back() == bomb.back() && result.size() >= bombSize) { for(int j=0; j<bombSize; j++) { if(bomb[j] != result[result.size() -bombSize +j]) { searchBomb = false; break; } } if(searchBomb) { result.erase(result.size()-bombSize, bombSize); } } } if(result.empty()) cout<<"FRULA"; else cout<<result; return 0; } | cs |
2. 스택 사용
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 | #include <iostream> #include <stack> #include <string> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string input, bomb; cin>>input>>bomb; stack<pair<char, int> > st; int inputSize=input.size(); int bombSize=bomb.size(); int sameBombCnt=0; for(int i=0; i<inputSize; i++) { if(input[i] == bomb[0]) sameBombCnt=1; else if(input[i] == bomb[sameBombCnt]) sameBombCnt++; else sameBombCnt=0; st.push(make_pair(input[i], sameBombCnt)); if(bombSize == sameBombCnt) { for(int j=0; j<bombSize; j++) st.pop(); if(!st.empty()) sameBombCnt=st.top().second; else sameBombCnt=0; } } if(st.empty()) cout<<"FRULA"; else { char result[st.size()]; result[st.size()]='\0'; for(int i=st.size()-1; i>=0; i--) { result[i]=st.top().first; st.pop(); } cout<<result; } return 0; } | cs |
반응형
'Algorithm' 카테고리의 다른 글
| [BOJ 10974] 모든 순열 (0) | 2019.02.25 |
|---|---|
| [BOJ 9996] 한국이 그리울 땐 서버에 접속하지 (0) | 2019.02.22 |
| [BOJ 1764] 듣보잡 (0) | 2019.02.20 |
| [BOJ 1213] 펠린드롬 만들기 (0) | 2019.02.19 |
| [BOJ 1431] 시리얼 번호 (0) | 2019.02.18 |