백준 링크 : https://www.acmicpc.net/problem/1152

문제 개요

문장이 몇개의 단어로 이루어졌는지 출력하는 문제이다.

예를들어, “The apple”은 두 개의 단어로 이루어져있고, 공백을 기준으로 단어들은 구분된다.

아이디어

• 문자열을 순회할 때 이전 문자와 현재 문자를 비교하고, 이전 문자가 공백이라면 단어의 개수를 증가시킨다.
  • “The apple”이라는 문자열을 순회할 때 현재 문자가 a이면 이전 문자는 공백이며, 이 때 단어의 개수를 증가시킨다.
  • 이전 문자를 저장하는 변수에는 공백을 저장해서 시작부터 공백이 아닌 글자가 나왔을 때 올바르게 개수를 셀 수 있게 초기화한다.

주의사항

• c++에서 공백이 포함된 문자열을 입력받을 때는 getline함수를 사용해야 한다.
• 시작 문자가 공백이거나 마지막 문자가 공백인 경우를 잘 생각해서 알고리즘을 만들어야 한다.
  • 시작 문자가 공백인 경우 : “ The apple”
  • 마지막 문자가 공백인 경우 : “The apple “

코드

// 아래의 코드는 dev c++환경에서 동작됩니다.
// visual studio에서는 bit/stdc++.h가 기본적으로 없기 때문에
// 정삭적인 작동이 되지 않을 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

// bits/stdc++.h에 prev변수가 선언되어있는데,
// 이 때문에 prev라는 변수명을 사용하지 못하는 것을 막아주는 매크로
#define prev asdfasdfd
int cnt = 0;
string input;
char prev = ' '; // 반드시 공백으로 초기화해야 한다.
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	getline(cin, input);
	
	for(int i = 0; i < input.size(); i++)
	{
		if(prev == ' ' && input[i] != ' ')
			cnt++;
		
		prev = input[i];
	} 
	
	cout << cnt;
	
    return 0;
}

후기

예전에 인프런 강의에서 split 알고리즘을 배운 적이 있다. 문자열을 구분자로 나누는 방법이다. 이걸 바탕으로 나눠진 문자열을 vector 컨테이너에 저장하고, 그 크기를 출력해서 문제를 풀어보려 했는데 시간 초과가 났다.

곰곰이 생각해보니, 문자열 길이가 최대 1,000,000이고 split 함수는 $O(n^2)$의 시간 복잡도를 가지고 있어서 시간 초과가 당연했다.

망치질을 배우면 모든 것이 못으로 보인다고 했던가. 새로운 알고리즘을 배우면 문제를 그 관점으로만 보게 되는 경향이 생기는 것 같다. 앞으로는 복잡한 알고리즘에 기대기보다 단순 구현으로 해결 가능한지부터 생각해 봐야겠다.