본문 바로가기

별걸다하는 IT/알고리즘 문제풀이

[백준 Baekjoon알고리즘]1152번 단어의 개수 문제 풀이, 공백 문자열 자르기, 다양한 풀이법

 

백준(BAEKJOON) 알고리즘 문제 풀기 - 1차원 배열 사용하기

 

[1152] 단어의 개수

----------------------------------------------------------------------------------------

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

시간제한: 2초,  메모리 제한 128MB

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

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

 

예시1

입력: The Curious Case of Benjamin Button

출력: 6

예시2

입력:  Mazatneunde Wae Teullyeoyo

출력: 3

예시3

입력: Teullinika Teullyeotzi

출력: 2

 

답을 보기 전에! 먼저 풀어보고 고민한 시간을 가진다음 확인하는 것이 실력을 기를 수 있는 길입니다. 

 

 

 

ANSWER

사고를 해보면 공백이 문자열 앞 뒤에 있으니까 ex)1. " aa aa aa " / 2. " aa aa aa" /3. "aa aa aa " 

1. 한 라인을 읽어들인다

2. 문자열 앞 뒤에는 공백이 있을 수도 있으니까 문자열 앞 뒤 공백을 먼저 제거해준다.

3-1. 공백이 연속해서 나오는 경우는 없으므로 각 단어 사이는 공백을 기준으로 판별할 수 있다. 

즉 공백을 기준으로 문자열을 잘라서 배열에 넣고 그 배열의 개수를 출력한다.

3-2. 공백의 개수 +1을 출력한다.

이렇게 앞뒤 공백을 먼저 제거해주고 문자열을 정리한 다음에 출력해줄 수도 있고 문제에서는 문자열까지 알 필요는 없으므로 공백의 개수 +1 해서 개수만 생각해줘도 되겠죠?!

 

또는 앞뒤 공백을 제거하는 거를 사전작업하기보다는 예외처리로 빼줘도 되겠죠!

1. 한 라인을 읽어들인다

2. 공백은 연속으로 안나오니까 공백이 단어 판별의 기준이 된다. 공백이 나오면 단어 개수 +1

3. 예외처리를 해준다.

 

근데 이 문제 풀 때 정말 조심해야 하는게 저도 문제를 별생각 없이 풀었다가 바로 틀렸습니다. ㅎㅎㅎㅎㅎ

문제의 조건을 다 고려한줄 알았건만..!! 

★★★ 문장에 공백만 나올수도 있다는 점입니다! 예외처리를 꼭 해줘야 해요 ㅎㅎ

고려해야할 예시에 ex)1." aa aa aa " / 2." aa aa aa" /3."aa aa aa " /4."     " 이것도 포함해줘야 합니다.

 

[C언어]

문자열을 읽어들일건데요 먼저 scanf는 공백을 읽을 수가 없기 때문에 공백을 포한한 한 라인을 입력받는 데에는 적절하지 않습니다.

gets함수의 경우 엔터가 나올때까지 한 줄의 문자열을 입력받지만 C11 버전부터는 gets가 gets_s로 변경됐습니다 뒤에 s는 safe의 약자인데요 gets자체가 바운드를 체크해주지 않기 때문에 버퍼 오버플로우에 취약하다는 판정때문에 gets_s를 사용하도록 권장되고 있습니다. visual studio 2015버전부터는 gets사용이 불가능해요 ㅎㅎ (물론 disable warning 달아주면 사용할수 있긴 하지만)

 

정리~!

# C11에서 gts()함수가 라이브러리에서 삭제됐음, 즉 C11표준이 적용되는 컴파일러에서는 gets()함수를 사용할 수 없습니다.

# gets_s는 비주얼 스튜디오에서 gets()의 대체함수로 제공되었습니다. 다만 표준은 아니기 때문에 채점환경에서는 사용할 수 없습니다. 비주얼 스튜디오에서만 동작하는 함수이기 때문에 백준에서는 버전을 C11이전으로 해주시면 gets는 사용가능하지만 gets_s는 사용 불가능합니다. 비주얼스튜디오에서는 gets_s잘 동작!

 --> 즉 ! gets사용보다는 그 대안으로 나온 gets_s 함수를 사용(MSVC 컴파일러에서 지원, 백준은 gcc 컴파일러 사용)하거나 fgets를 사용하면 버퍼 오버플로우 문제를 피할 수 있습니다. 

#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main()
{
    char str[1000001];
    int spaceNum = 0;
    int wordNum = 0;
    int len;

    //문자열 입력받기 
    gets_s(str, 1000001);
    len = strlen(str);

    //공백 개수 세기
    for (int i = 0; i < len; i++)
    {
        if (str[i] == ' ')
            spaceNum++;
    }
    //앞뒤 공백이 없고 연속 공백이 없을 경우
    //단어의 개수는 공백+1
    wordNum = spaceNum + 1;

    //예외 처리 공백으로만 이루어져 있을 경우
    if (len == spaceNum)
    {
        wordNum = 0;
        printf("%d", wordNum);
    }
    else {
        if (isspace(str[0]))
            wordNum--;
        if (isspace(str[len - 1]))
            wordNum--;
        printf("%d", wordNum);
    }
}

 

백준일경우 gets(str);로 12번 코드를 변경해줍시다.

C-type문자열 방식을 사용하는거라서 마지막에 '\0'넣어줄 공간 때문에 크기가 1000001로 정해줍니다.

 

근데 사실 눈치채신 분들도 있겠지만 공백으로만 이루어져있는 경우 부문은 코드를 빼도 됩니다 

왜냐! 공백이 연속되서 오지 않기 때문이죠

#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main()
{
    char str[1000001];
    int spaceNum = 0;
    int wordNum = 0;
    int len;

    //문자열 입력받기 
    gets(str);
    len = strlen(str);

    //공백 개수 세기
    for (int i = 0; i < len; i++)
    {
        if (str[i] == ' ')
            spaceNum++;
    }
    //앞뒤 공백이 없고 연속 공백이 없을 경우
    //단어의 개수는 공백+1
    wordNum = spaceNum + 1;
    if (isspace(str[0]))
        wordNum--;
    if (isspace(str[len - 1]))
        wordNum--;
    printf("%d", wordNum);
}

메모리: 1972KB

시간: 12ms

코드 길이: 540B

 

[C언어]

두 번째 방법으로는 fgets와 strtok()를 사용해볼게요 strtok또한 unsafe로 사용이 권장되지 않습니다. 그래서 비주얼스튜디오에서는 strtok_s()을 대체함수로 주고 있어요 물론 gcc컴파일러 기반인 백준에서는 strtok()를 사용할 수 있습니다.

간단하게 짚고 넘어가면 strtok는 문자열을 구분자를 기준으로 나눠주는 함수입니다.

주의해야할 점은 구분자 매개변수가 문자열! 이기 때문에 구분자를 공백으로 하고 싶으면 ' '하면 안되고 " "로 해줘야합니다. 

char * strtok(char str[], const char *delims);

다음 토큰 값을 리턴해줍니다. 더 이상 토큰이 없으면 NULL을 리턴해줘요

 

NULL을 주는 이유는 last위치부터 다시 탐색해 나가게 하기 위해서예요. 이 포스팅은 여러 방안과 풀이를 알려주는 목적이니 자세한건 strtok() 함수 포스팅을 확인하고 옵시다! 이전 포스팅을 보면 알겠지만 strtok를 사용했을 경우, 앞에 공백이 있거나 사이에 공백이 있어도 영향을 주지 않아요 

#include <stdio.h>
#include <string.h>
#pragma warning (disable: 4996)
int main()
{
    //fgets는 뒤에 개행이 붙을 수도 있으므로 배열의 더 늘려줬어요
    char str[1000002];
    char* token;
    int count = 0;
    fgets(str, sizeof(str), stdin);
    /*gets라면 " "만 구분자로 넣었겠지만
    fgets는 개행이 들어가므로 개행까지 구분자로 넣어줘야 올바른 결과가 나옵니다.*/
    token = strtok(str, " \n");
    
    while (token != NULL)
    {
        count++;
        token = strtok(NULL, " \n");
    }
    printf("%d", count);
    return 0;
}

메모리: 1972KB

시간: 12ms

코드 길이: 285B

 

[C++언어]

저번 포스팅에서 다뤘던 getline함수를 이용해서 한 줄을 읽어들일 수 있어요

string 라이브러리에는 그런데 trim함수가 없습니다! 자바스크립트나 자바 등등 다른 언어에 trim이라는 함수가 워낙 많고 자주 사용하다보니까 별다른 생각없이 string클래스에 trim함수가 있을거라 생각더라고요 ㅎㅎ. 

앞 또는 뒤에 공백이 나오면 지워주는 것으로 trim을 대신해서 풀어봅시다.

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s;
    int num = 0;
    int pos;
    getline(cin, s);
    if (!s.empty())
    {
        if (s.front() == ' ')
            s.erase(s.begin());
        if (!s.empty())
        {
            if (s.back() == ' ')
                s.erase(s.end()-1);
        
            pos = s.find(' ');
            while (pos != s.npos)
            {
                num++;
                pos = s.find(' ', pos + 1);
            }
            num++;
        }
    }
    cout << num << "\n";
    return 0;
}

메모리: 4880KB

시간: 36ms

코드 길이: 445B

 

string 클래스의 멤버함수들은 이 포스팅에서 다룬적이 있으니 기억 안나시는 분은 보고 오기!

 

[Java]

언어만 바뀌었을 뿐 똑같습니다. 첫 번째 C코드에서 적용했던 방법을 Java로 변환해볼게요.

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int count = 0;
        
        for(int i=0; i<str.length(); i++){
            if(str.charAt(i)==' ') 
                count++;
        }
        count++;
        if(str.charAt(0)==' ')
            count--;
        if(str.charAt(str.length()-1)==' ')
            count--;
        System.out.println(count);
    }
}

메모리: 29996KB

시간: 336ms

코드 길이: 512B

 
[Java]
Java의 문자열 메소드를 이용해서 풀 수도 있는데요 
먼저, C의 strtok 함수와 비슷한 기능을 하는 StringTokenizer가 있습니다! 내부부터가 비슷하게 구현되어 있어요 ㅎㅎStringTokenizer의 경우 더 편리하게 countTokens()라는 메소드를 제공해줘요. strtok 함수 사용할 때와는 다르게 반복문 없이 구분된 문자열 개수를 바로 알 수 있습니다.
import java.util.StringTokenizer;
import java.util.Scanner;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        StringTokenizer st = new StringTokenizer(str, " ");
        int count = st.countTokens();
        System.out.println(count);
    }
}

메모리: 30164KB

시간: 340ms

코드 길이: 347B

 
[JAVA]
그 다음은 split 메소드를 사용해볼게요. split으로 문자열을 나눌 경우, 이 메소드는 공백을 인식을 합니다. 공백이 연속으로 나오지 않으니 중간 공백은 상관없지만 앞 뒤 공백은 미리 제거해줘야 해요.
C와는 다르게 Java는 trim이라는 함수를 제공해주고 있습니다.
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String str = sc.nextLine().trim();
            if(str.isEmpty()) {
                  System.out.println(0);
              }else {
                  String[] words = str.split(" ");
                System.out.println(words.length);    
            }
    }
}

메모리: 39732KB

시간: 364ms

코드 길이: 381B