백준 / 스택 / 9093번 / 단어 뒤집기 / C++

문제

문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오.

단, 단어의 순서는 바꿀 수 없다.

단어는 영어 알파벳으로만 이루어져 있다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다.

단어의 길이는 최대 20, 문장의 길이는 최대 1000이다.

단어와 단어 사이에는 공백이 하나 있다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 문장의 단어를 모두 뒤집어 출력한다.

예제 입력 1 

2

I am happy today

We want to win the first prize

예제 출력 1 

I ma yppah yadot

eW tnaw ot niw eht tsrif ezirp

 

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
	int t;
	cin >> t;
	cin.ignore();

	for (int i = 0; i < t; i++) {
		string input;
		getline(cin, input);
		input += ' ';

		stack<char> stack;

		int len = input.length();

		for (int j = 0; j < len; j++) {
			if (input[j] == ' ') {
				while (true) {
					cout << stack.top();
					stack.pop();

					if (stack.empty()) break;
				}
				cout << ' ';
			}

			else {
				stack.push(input[j]);
			}
		}
	}

	return 0;
}

---

문자열로도 해결할 수 있었지만, 스택 챕터 공부중이라서 스택으로 풀어보았다.

이 문제에서 중요한 것 몇가지만 잘 확인해보면 될 것 같다.

1. 공백 포함 문자열 입력받기
2. 문자열 입력시 (마지막)개행문자 처리

이걸 잘 처리하고 알고리즘은 간단하다.

 

input의 마지막에 ' '(공백)을 더해준 이유는, 공백 단위로 끊어서 문자열을 뒤집기 때문이다.

만약 더해주지 않았다면, 마지막 단어는 뒤집어지지 않았을 것이다.

---

문자열로 풀어본 코드이다.

#include <iostream>
#include <string>
using namespace std;

int main() {
	int n;
	int idx;
	cin >> n;
	cin.ignore();

	for (int i = 0; i < n; i++) {
		string input;
		getline(cin, input);

		int len = input.length();
		idx = 0;

		for (int j = 0; j < len; j++) {
			if (input[j] == ' ') {
				for (int k = j - 1; k >= idx; k--) {
					cout << input[k];
				}
				cout << " ";
				idx = j + 1;
			}
		}

		for (int m = len - 1; m >= idx; m--) {
			cout << input[m];
		}
		cout << endl;
	}

	return 0;
}

---

원래 스택이용보다 문자열로 하는게 더 간단할것 같았는데 막상해보니 그렇지 않았다.

알고리즘은 쉽게 떠올랐지만, 문자열의 범위를 벗어나는 런타임 에러가 계속 떴다.

 

알고리즘 순서는 대강 이렇다.

1. cin.ignore()로 정수 입력받을 때 들어간 개행문자를 무시한다.
2. 정수만큼 반복문을 돌고, idx = 0으로 초기화한다.
3. 문자열의 마지막까지 루프를 돈다.
   1. 만약 공백이 나오면,
      1. 공백 전부터 idx번째까지 루프를돌면서 출력한다.
      2. 출력한후 공백을 출력해주고, idx에 공백 다음 인덱스를 넣어준다.
4. 마지막 단어는 끝에 공백이 없으므로 위 루프에 포함되지 않기때문에 따로 처리를 해준다.

 

이문제만 약 2시간 가량을 쏟아부은 것 같다.

스택을 이용하면 쉽지만, 문자열 처리에 더 익숙해져야 할 것 같다.