[백준 BOJ][C++]9093번 단어 뒤집기 풀이: Stack

BOJ 9093번 문제 설명

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

9093번: 단어 뒤집기

 

  풀이과정

1.  공백을 포함하는 문자열 입력
2.  공백(' ')을 기준으로 스택을 사용하여 단어 저장
3.  단어가 저장된 스택을 이용하여 문자열의 해당 단어를 교체

#include<iostream>
#include<cstring>
#include<vector>

using namespace std;

int main(void) {

	int T;
	char str[1001]; //문자열 
	vector<char> buf; //단어 저장할 스택
	int j;

	cin >> T;
	cin.ignore(); //버퍼 지우기

	while(T > 0) {
		cin.getline(str, 1001); //공백 포함하는 문자열 입력

		for (int i = 0; i < strlen(str) + 1; i++) {

			if (str[i] == ' ' || i == strlen(str)) {
				j = i - buf.size();  //str 내에서 각 단어의 첫 번째 index

				while (!buf.empty()) {
					str[j++] = buf.back(); //단어 다시 저장
					buf.pop_back();
				}
			}
			else {
				buf.push_back(str[i]);
			}
		}
		cout << str << endl;
		T--;
	}

	return 0;
}

 

 먼저, vector container는 맨 뒤에서 삽입과 삭제 연산이 가능하므로 스택과 같이 사용할 수 있습니다. 

 스택은 FILO(First In Last Out)의 성질을 갖고 있음으로, 단어를 뒤집을 때의 연산이 효율적으로 이루어질 수 있습니다. 

 

 cin.getline()을 사용하여 공백을 포함하는 문자열을 입력합니다. 이때 만약 cin>>str; 처럼 작성한다면 공백을 포함하는 문자열을 입력할 수 없게 됩니다. 

 

 for 문을 통해 str에 저장된 문자들을 탐색합니다. 각 단어를 저장할 스택 buf는 공백(' ')을 만나기 전까지 문자들을 저장합니다. 이때 for문의 조건식을 i<strlen(str)+1로 한 이유는 문자열의 마지막에는 공백(' ')이 포함되지 않기 때문에 단어를 뒤집을 조건문 if에서의 마지막 단어에 대한 조건을 주기 위해서입니다. 

 

 문자열(str)에서 각 단어의 시작 index를 나타내는 j를 설정합니다. 스택에서 차례대로 pop 연산을 수행하여 해당 단어를 뒤집어 줍니다.