C언어 백준 1157번 단어공부 해설

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

1157번: 단어 공부

 

문제 

알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.

 

 

풀이

 

●idea

1)-> ASCII 코드 에서 대문자 소문자 구분해줘야함 

2)알파벳이 있으므로 알파벳 배열 만들어주자.

3) ?출력해야하므로 조건문을 사용하자.

 

쓰이는 개념 : 문자열 ,scanf, for 문,조건문 

 

●풀이구성

 (1)scanf에 입력값을 받고 이를 문자열 배열에 넣는다.

 

 (2)문자열 배열을 첫 인덱스부터 for 문으로 체크하고 개수를 알파벳 배열에 넣는다.(52개로 하고 , 소문자 개수를 대문자에 더해주기)

 

 (3) 알파벳 배열의 인수를 비교하고 가장 큰 인수의 알파벳을 대문자로 출력한다

( 단, 가장많이 사용된 알파벳이 여러 개 존재하는 경우 ?를 출력한다) 

 

 

 

 

(1)scanf에 입력값을 받고 이를 문자열 배열에 넣는다.

 char Input_char[1000000];
    char Alphabet[52];
    scanf("%s", Input_char);

 

의문 Q1) 문자열 입력된 것을 문자열 배열에 넣어주어야하는데 단어의 길이가 1,000,000을 넘지 않는다는 조건이 있다면 배열의 길이를 1,000,000으로 해줘야 하는가? 

 

A)일부 데이터를 힙으로 이동하라는 C6262 경고가 뜨긴 하나 compile run 에는 문제가 없다.

 

 

 

 

 

(2)문자열 배열을 첫 인덱스부터 for 문으로 체크하고 개수를 알파벳 배열에 넣는다.

 

for (int i = 0; i < strlen(Input_char); i++)
    {
        printf("문자열이%c일때", Input_char[i]);

        for (int j = 65; j <= 90; j++) //대문자 알파뱃 ASCII 코드 A부터 ~Z까지 
        {
            if (Input_char[i] == j) //M 
            {
                Alphabet[j-65] = Alphabet[j-65] + 1; //M = 72 이고 Alpha배열에서 M = 13번쨰
            }
        }

        for (int j = 97; j <= 122; j++) //소문자
        {
            if (Input_char[i] == j) //M 
            {
                Alphabet[j - 71] = Alphabet[j - 71] + 1; //i = 105 일떄 Alpha배열에서 35번쨰 
            }
        }


        for (int i = 0; i < 52; i++)
        {
            printf("%d", Alphabet[i]);
        }
        printf("\n");
    }

 

각 배열에 잘 들어간 것을 확일 할 수 있음 M =1 / i = 4 / p =1 / s = 4 

 

 

(3) 알파벳 배열의 인수를 비교하고 가장 큰 인수의 알파벳을 대문자로 출력한다

( 단, 가장많이 사용된 알파벳이 여러 개 존재하는 경우 ?를 출력한다) 

 

이 마지막 풀이 단계는 총 2개로 구분 할 수있다.

 

(3)-1 대문자로 출력하기

 

 for (int k = 0; k <= 25; k++) //소문자에 있던 것을 대문자로 옮겨주기 
    {
        Alphabet[k] = Alphabet[k] + Alphabet[k + 26];
    }

    for (int k = 0; k <= 25; k++)// 소문자 초기화
    {
        Alphabet[k + 26] = 0 ;
    }

(3)-2 여러개 존재하는 경우 ? 출력하기

 //-----------(3)-2 여러개 존재하는 경우 ? 출력하기-------------
    int cnt = 0;
    for (int i = 0; i < 26; i++) //Max 개수 체크 
    {
        if (Alphabet[i] == Max)
        {
            cnt++;
        }
    }

    
    if (cnt > 1)
    {
        printf("?");
    }

    else
    {
        printf("%c", A+65);
    }

입력:Mississipi

입력:zZa

 

오답:시간초과

#include <stdio.h>
#include <string.h> //문자열 길이 

int main() {
    

    char Input_char[1000000];
    int Alphabet[52] ; //ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz --> 그러나 숫자만 넣을 것이므로 int형 
    

    for (int i = 0; i <52; i++) //Alphabet 배열 인수 0으로 모두 초기화 
    {
        Alphabet[i] = 0;
    }
    
    //---------(1)scanf에 입력값을 받고 이를 문자열 배열에 넣는다.--------------
    scanf("%s", Input_char); //Mississipi
    
    
    //------(2)문자열 배열을 첫 인덱스부터 for 문으로 체크하고 개수를 알파벳 배열에 넣는다.--------
    for (int i = 0; i < strlen(Input_char); i++)
    {

        for (int j = 65; j <= 90; j++) //대문자 알파뱃 ASCII 코드 A부터 ~Z까지 
        {
            if (Input_char[i] == j) //M 
            {
                Alphabet[j-65] = Alphabet[j-65] + 1; //M = 72 이고 Alpha배열에서 M = 13번쨰
            }
        }

        for (int j = 97; j <= 122; j++) //소문자 알파뱃 ASCII 코드 a~z까지 
        {
            if (Input_char[i] == j) //M 
            {
                Alphabet[j - 71] = Alphabet[j - 71] + 1; //i = 105 일떄 Alpha배열에서 35번쨰 

            }
        }

    }
    //-------(3)-1 대문자로 출력하기------
    for (int k = 0; k <= 25; k++) //소문자에 있던 것을 대문자로 옮겨주기 
    {
        Alphabet[k] = Alphabet[k] + Alphabet[k + 26];
    }

    for (int k = 0; k <= 25; k++)// 소문자 초기화
    {
        Alphabet[k + 26] = 0 ;
    }

    int Max = Alphabet[0]; //최대값
    int A = 0; //Max 값을 가지는 Alpha배열의 인덱스 값 
    for (int i = 0; i < 26; i++) //max값  구하기 
    {
        if (Alphabet[i] > Max)
        {
            Max = Alphabet[i];
            A = i;
         }
    }
   
    
    //-----------(3)-2 여러개 존재하는 경우 ? 출력하기-------------
    int cnt = 0;
    for (int i = 0; i < 26; i++) //Max 개수 체크 
    {
        if (Alphabet[i] == Max)
        {
            cnt++;
        }
    }

    
    if (cnt > 1)
    {
        printf("?");
    }

    else
    {
        printf("%c", A+65);
    }
    

    return 0;
}

 

시간초과 원인

 

같은 문제에 대한 원인과 그 이유

정답

int len = strlen(Input_char); 을 추가한 코드

#include <stdio.h>
#include <string.h> //문자열 길이 

int main() {
    

    char Input_char[1000000];
    int Alphabet[52] ; //ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz --> 그러나 숫자만 넣을 것이므로 int형 
    int len = 0; //input_char 의길이

    for (int i = 0; i <52; i++) //Alphabet 배열 인수 0으로 모두 초기화 
    {
        Alphabet[i] = 0;
    }
    
    //---------(1)scanf에 입력값을 받고 이를 문자열 배열에 넣는다.--------------
    scanf("%s", Input_char); //Mississipi
    len = strlen(Input_char);
    
    //------(2)문자열 배열을 첫 인덱스부터 for 문으로 체크하고 개수를 알파벳 배열에 넣는다.--------
    for (int i = 0; i < len; i++)
    {

        for (int j = 65; j <= 90; j++) //대문자 알파뱃 ASCII 코드 A부터 ~Z까지 
        {
            if (Input_char[i] == j) //M 
            {
                Alphabet[j-65] = Alphabet[j-65] + 1; //M = 72 이고 Alpha배열에서 M = 13번쨰
            }
        }

        for (int j = 97; j <= 122; j++) //소문자 알파뱃 ASCII 코드 a~z까지 
        {
            if (Input_char[i] == j) //M 
            {
                Alphabet[j - 71] = Alphabet[j - 71] + 1; //i = 105 일떄 Alpha배열에서 35번쨰 

            }
        }

    }
    //-------(3)-1 대문자로 출력하기------
    for (int k = 0; k <= 25; k++) //소문자에 있던 것을 대문자로 옮겨주기 
    {
        Alphabet[k] = Alphabet[k] + Alphabet[k + 26];
    }

    for (int k = 0; k <= 25; k++)// 소문자 초기화
    {
        Alphabet[k + 26] = 0 ;
    }

    int Max = Alphabet[0]; //최대값
    int A = 0; //Max 값을 가지는 Alpha배열의 인덱스 값 
    for (int i = 0; i < 26; i++) //max값  구하기 
    {
        if (Alphabet[i] > Max)
        {
            Max = Alphabet[i];
            A = i;
         }
    }
   
    
    //-----------(3)-2 여러개 존재하는 경우 ? 출력하기-------------
    int cnt = 0;
    for (int i = 0; i < 26; i++) //Max 개수 체크 
    {
        if (Alphabet[i] == Max)
        {
            cnt++;
        }
    }

    
    if (cnt > 1)
    {
        printf("?");
    }

    else
    {
        printf("%c", A+65);
    }
    

    return 0;
}

 

배운점

1) for 문의 조건에 strlen 을 직접사용하지말고 변수를 이용하자.

2)strlen 대신에 배열[i] != '\0'을 조건으로 쓰는 idea도 있다.

3)배열의 크기를 52로 하지 않고 26으로 한뒤 for 문/If 문을 활용해 소문자가 

나올때마다 그 자리에서 바로 소문자로 바꿔주는 idea가 더 깔끔하다.

▼바로 소문자 바꾸는 코드

for(i=0;str[i]!='\0'; i++){
    if(str[i]<97)
        str[i]+=32;
    num[str[i]-97]++;
}