반응형

https://www.acmicpc.net/problem/9935

 

9935번: 문자열 폭발

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모

www.acmicpc.net

 

 

[ 문제풀이 ]

 

스택을 사용해서 문자열을 넣어가며 폭탄 문자열을 만나면 제거하는 방식으로 문제를 풀었습니다.

 

하지만 폭탄 문자열과 일부만 일치하는 문자열이 들어왔을 때는 한 과정이 더 추가되었습니다. temp 스택에 문자열을 넣으면서 비교를 하다가 폭탄 문자열과 다르다면 temp 스택에 들어있는 문자열을 다시 정답 스택에 집어넣어주었습니다.

 

 

[ 소스 코드 ]

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<string>
#include<stack>
 
using namespace std;
 
string str, bomb;
 
int main()
{
    cin >> str >> bomb;
 
    stack<char> ans;
    stack<char> temp;
 
    for (int i = 0; i < str.size(); i++) {
        ans.push(str[i]);                //stack의 크기가 폭탄문자열의 길이보다 길고 문자가 일치한다면
        if (ans.size() >= bomb.size() && ans.top() == bomb[bomb.size() - 1]) {
            for (int j = bomb.size() - 1; j >= 0; j--) {
                if (bomb[j] == ans.top()) {        //임시로 temp스택에 저장
                    temp.push(ans.top());
                    ans.pop();
                }
            }
            if (temp.size() == bomb.size()) {    //폭탄 문자열이 나오면
                while (!temp.empty()) {            //temp스택을 비움
                    temp.pop();
                }
            }
            else {
                while (!temp.empty()) {            //ans 스택에 temp를 다시 넣어줌
                    ans.push(temp.top());
                    temp.pop();
                }
            }
        }
    }
 
    while (!ans.empty()) {        //스택을 그대로 출력하면 반대로 나오므로
        temp.push(ans.top());    //temp 스택에 다시 넣어줌
        ans.pop();
    }
 
    if (temp.size() == 0) {
        cout << "FRULA";
    }
    else {
        while (!temp.empty()) {
            printf("%c", temp.top());
            temp.pop();
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1967번 - 트리의 지름 (C++)  (0) 2022.06.16
[ 백준 ] 13549번 - 숨바꼭질 3 (C++)  (0) 2022.06.15
[ 백준 ] 2638번 - 치즈 (C++)  (0) 2022.06.13
[ 백준 ] 13460번 - 구슬 탈출 2 (C++)  (0) 2022.06.12
[ 백준 ] 11404번 - 플로이드 (C++)  (0) 2022.06.11

+ Recent posts

티스토리툴바