2022. 10. 6. 14:29ㆍPS (Program Solving)/BOJ (백준)
문제 설명
https://www.acmicpc.net/problem/17413
접근 방법 - 스택을 이용한 문자열 연산 문제
백준의 17413번 문제는 스택을 이용하여 문자열 연산을 수행해야 하는 응용문제이다.
해당 문제는, 입력받은 문자열에 대하여 공백으로 나누어진 단어의 알파벳 순서를 뒤바꾸어 출력해야 하는 문제이다.
다만, 꺽쇠(<>)로 감싸진 단어와 같은 경우엔 알파벳 순서를 유지하여 출력하도록 해야 한다.
필자는 이 문제를 볼 때 바로 스택이 떠올랐고 그 즉시 바로 이를 이용하여 문자열 연산을 수행하였다.
이 문제와 같은 경우에는 스택을 꼭 사용하지 않고도 해결할 수 있을 것으로 확인되기 때문에 이 점을 미리 인지해주길 바란다.
이때 이 문제에선 공백을 포함한 문자열이 입력값으로 주어지기 때문에, cpp로 코딩을 진행한다면 아래의 구문을 참고하며 이를 통해서 입력을 받아야 할 것이다.
getline(cin, st);
// 공백을 포함하여 입력받은 문자열을 st에 저장한다.
혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있으며 스택에 대해 어느 정도 알고 있다면, 아래의 설명과 코드를 참고해보길 바란다.
필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.
코드의 실행 순서
1) 공백을 포함한 문자열(st)을 입력받는다.
2) 문자열 연산을 위한 char형 스택(s)을 선언해둔다.
3) st의 길이만큼 반복문을 수행하여 아래의 연산을 수행한다.
꺽쇠(<>)로 감싸 지지 않은 단어들은 스택을 거치게끔 하여 알파벳 순서를 뒤집어보았다.
다만 꺽쇠(<>)로 감싸진 단어들은 스택을 거치지 않고 즉시 출력을 하여 알파벳 순서에 변동이 없게끔 하였다.
- 만일 현재 탐색값이 꺽쇠의 시작 부분(<)이라면 다음과 같은 연산을 취한다.
만일 이 앞으로 공백 없이 이 부분을 발견한 것이라면 s에 남아있는 문자가 분명히 있을 것이다. 따라서 이 경우엔, s에 있는 값들을 하나씩 출력하면서 pop 연산을 취한다.
꺽쇠 부분(<>)과 그 안에 있는 공백들을 모두 포함하여 감싸진 단어를 그대로 출력하도록 한다. st의 인덱스를 나타내는 i를 틈틈이 증가하는 것도 잊지 말자.
위 연산을 모두 했다면, continue를 사용하여 반복문 첫 부분으로 넘어간다.
- 만일 현재 탐색값이 공백(' ')이 아닌 문자라면 그대로 s에 push한다.
- 만일 현재 탐색값이 공백(' ')이거나 st의 끝 부분이라면, s에 있는 문자들을 하나씩 출력하면서 pop 연산을 취한다.
모두 출력되었다면, 그 뒤에 공백을 출력한다.
4) 위 연산이 모두 수행되었다면, 실행 종료한다.
성공한 코드
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <string>
#include <stack>
#define endl '\n'
using namespace std;
//백준 17413번 코드
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
string st;
getline(cin, st);
stack<char> s;
for (int i = 0; i < st.length(); i++) {
if (st[i] == '<') {
while (!s.empty()) {
cout << s.top();
s.pop();
}
while (st[i] != '>') {
cout << st[i]; i++;
}
cout << '>';
continue;
}
if (st[i] != ' ') {
s.push(st[i]);
}
if (st[i] == ' ' || i == st.length() - 1) {
while (!s.empty()) {
cout << s.top();
s.pop();
}
cout << " ";
}
}
}
제출 결과
(2022.07.25 백준 17413번 문제 제출 결과)
'PS (Program Solving) > BOJ (백준)' 카테고리의 다른 글
[백준 BOJ] 3046번 R2 (C++/cpp) (0) | 2022.10.07 |
---|---|
[백준 BOJ] 9020번 골드바흐의 추측 (C++/cpp) (0) | 2022.10.06 |
[백준 BOJ] 7891번 Can you add this? (C++/cpp) (0) | 2022.10.06 |
[백준 BOJ] 4948번 베르트랑 공준 (C++/cpp) (0) | 2022.10.06 |
[백준 BOJ] 2460번 지능형 기차 (C++/cpp) (1) | 2022.10.05 |