본문 바로가기
코딩과 알고리즘

백준 알고리즘 1152. 단어의 개수 풀이 & 해설

문제

영어 대소문자와 띄어쓰기만으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다.

입력

첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열의 앞과 뒤에는 공백이 있을 수도 있다.

출력

첫째 줄에 단어의 개수를 출력한다.

예제입력

 

예제입력

The Curious Case of Benjamin Button

예제출력

6

해설

한줄을 읽어 단어의 갯수를 세는 문제인데요.

단순히 공백의 갯수를 세어서 1을 더해준다고 생각하기 쉬운데

앞 뒤에 공백이 올 수도 있다고 하기 때문에 예외처리를 해주어야 합니다.

우선 1,000,000 바이트, 약 1메가바이트의 입력이 주어지기 때문에 문자열을 한꺼번에 읽어서 판단하는건 비효율적이고 한 문자씩 읽어서 판단하는 것이 빠릅니다.

다양한 풀이 방법이 있을 수 있으니 크레이가 제시해드리는 것만이 꼭 정답은 아닌 점 유념해 주세요 :)

핵심처리조건.

글자를 하나하나 세면서 공백이 나오면 띄어쓰기 상태로,

글자가 나오면 단어를 읽는 상태로 인식합니다.

그 과정을 반복하는 도중 단어에서 띄어쓰기로 바뀔때마다 단어 1개씩 읽었다고 세면 됩니다.

단어를 읽는 도중 문장이 끝난 경우에도 단어 1개를 읽었다고 세주는 부분이 필요합니다.

처리순서

1. 맨처음 시작할때는 '띄어쓰기'모드로 시작합니다.

bool space=true;

2. 문장의 처음부터 한 글자씩 읽어 나갑니다.

do { ... scanf("%c", &c);

3. 현재 읽은 글자가 문장의 끝을 의미하면 7단계로 이동합니다.

if (c == EOF || c == '\0' || c == '\n')break;

4. 띄어쓰기 상태였는데 공백이 나온 경우 맨 앞의 공백이 온 경우이므로 아무것도 안하고 다음 글자를 읽어들입니다.

// 띄어쓰기 상태에서 또 공백이 나오면

if (space == true && c == ' ') {

continue; // 다음 문자로 진행

}

5. 만일 띄어쓰기가 아닌 상태에서 공백이 나온다면 단어를 읽다가 끝난 것이므로 단어를 하나 셉니다. 그리고 띄어쓰기 상태로 바꾸고 다음 문자를 읽습니다

space = true; // 띄어쓰기 상태로 바꿈

WordCount++; // 단어 1개를 마친것이므로 증가

continue; // 다음 문자로 진행

6. 공백이 아닌 문자가 나온다면, 띄어쓰기 아닌 상태로 바꾸고 다음 문자로 진행합니다.

사실 앞 단계에서 모두 continue 로 돌아가도록 했기 때문에

여기서는 space 값만 false 로 지정해주시면 됩니다.

space = false;

7. 마지막이 띄어쓰기로 끝나지 않은 경우 마지막은 아직 카운트가 안된 단어였기 때문에 하나를 더 세줍니다. 그리고 결과를 출력하면 끝!

if (space == false)

{

WordCount++; // 단어 1개를 마친것이므로 증가

}

printf("%d\n", WordCount);

이해가 어려우신 부분 있으면 문의 주세요 :)

 

소스코드

 

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

// 단어의 갯수
void WordCount()
{
	char c;
	int WordCount = 0;  // 단어의 갯수를 세는 변수
	bool space = true;	// 띄어쓰기 상태 여부
	do
	{
		scanf("%c", &c); // 한글자를 읽는다

        // 한줄을 읽었으면 끝
		if (c == EOF || c == '\0' || c == '\n')break;

		// 띄어쓰기 상태에서 또 공백이 나오면
		if (space == true && c == ' ') {
			continue;         // 다음 문자로 진행
		}

		// 띄어쓰기 아닌 상태에서 공백이 나오면
		if (space != true && c == ' ') {
			space = true;	// 띄어쓰기 상태로 바꿈
			WordCount++;	// 단어 1개를 마친것이므로 증가
			continue;       // 다음 문자로 진행
		}
		// 그 외의 경우 공백 문자가 아니므로
		space = false;	// 띄어쓰기 상태 해제 ( 단어 상태 )		
	} while (true);
	// 마지막 후처리
	// 띄어쓰기가 아닌 상태로 끝났으면
	if (space == false)
	{
		WordCount++;	// 단어 1개를 마친것이므로 증가
	}
	printf("%d\n", WordCount);
}

int main()
{
	WordCount();
	return 0;
}

열혈모드로 문제 풀이! 16000위권이 곧 고지입니다 :)

 

반응형