1157, 단어 공부

 

 

★ "왜?" 라는 질문을 스스로에게 하면서 학습하자.

 

 

0. 문제 풀이 순서

• 논리적 순서 확정
• 관련 카테고리 혹은 문제 끌어오기
• 필요한 자료연산 리스트업
• 이에 제일 유리한 자료구조 선택
• 구현

 

1. 설명

 

문제 링크 :

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

 

문제 사진 :

 

문제 설명 : 대소문자로 이루어진 단어가 주어질 때 가장 많이 사용되는 알파벳이 무엇인지 알아내야 한다. 따라서 대문자/소문자 입력 상관없이 모두 대문자로 변환하여 처리하거나 소문자로 변환하여 처리하는 방법이 필요하다.

 

---

 

나의 소스 코드 : 

 

#include <iostream>
#include <string>
#include <cstring>
#include <climits>
#include <cctype>
#include <algorithm>
#include <functional>
#include <tuple>
#include <utility>
#include <list>
using namespace std;

int main()
{
    char UserInput[1000001];
    int Result[26] = { 0, };
    
    cin >> UserInput;
    int UILength = strlen(UserInput);
    
    for (int i = 0; i < UILength; i++)
    {
        // 대문자로 변환
        char temp = toupper(UserInput[i]);
        Result[temp - 'A']++;
    }
    
    int MaxCount = 0;
    char ResultText = '?';
    
    for (int i = 0; i < 26; i++)
    {
        if (Result[i] > MaxCount)
        {
            MaxCount = Result[i];
            ResultText = i + 'A';
        }
        else if (Result[i] == MaxCount)
        {
            ResultText = '?';
        }
    }
    
    cout << ResultText << endl;
    return 0;
}

 

코드 설명 : 먼저 문제의 '입력'으로 주어진 길이만큼 배열을 선언하고, 이를 입력받는다. 이 후 사용자의 입력한 길이를 strlen을 통해 받아온다. 반복문을 통해서 사용자가 입력한 길이만큼 순회하며 입력 내용을 모두 대문자로 변환한다. (toupper)

 

 이 후, Result[26] (=알파벳 개수)의 배열에 변환한 값에서 대문자 'A'를 뺀 값을 인덱스로 설정하여 값을 증감시킨다. 예) aAa일 경우 aaa로 변환되고 a 인덱스의 해당하는 값은 3이 된다. 즉 Result는 [a - 3][b - 0][c - 0]..[z-0]의 값을 가진다. 

 

 마지막으로 알파벳 개수만큼 반복문을 순회하여 Resuit[i]의 값이 MaxCount 보다 크거나 같은지를 비교하여 최종적으로 나타나야할 ResultText를 설정한다.

 

2. 시간

• 문제 풀이를 위해 설정한 시간 : 1시간
• 실제 풀이 시 걸렸던 시간 : 30분

 

3. 질문

• 시간 복잡도 : 사용자의 입력은 O(N), 문자열 길이는 O(N), 대문자 변환도 문자열 길이만큼 반복되므로 O(N), 문자열 찾는 행위는 26번 반복하므로 O(1)이므로 전체 코드의 시간 복잡도는 O(N)이다.
• 공간 복잡도 : 사용자의 입력은 마찬가지로 O(N) 공간, 빈도수 배열은 O(1)이므로 전체 코드의 공간 복잡도는 O(N)이다.
• 어려웠던 부분 : 사용자의 입력 길이만큼 반복해서 대/소문자로 변환해야하는 것 까지는 이해했지만, 사용자가 어떤 값을 입력했는데 작성하기가 매우 어려웠다. (=Result[temp - 'A'] 부분)
  
   물론, 배열에다가 사용자 입력값을 저장해야하는건 이해했지만 Result[temp - 'A']++와 같이 사용자의 입력을 Result라는 결과 배열에 - 'A'의 값을 인덱스로 설정해줘야 하는 부분에서 '이런게 가능하다고?'와 '왜 이걸 생각못했을까?'라는 두 생각이 교차했다.

 

4. 기타

• 최초 풀이 : 24.03.28
• 재 풀이 : 24.05.30, 24.08.01
• 왜? : 이전에 풀었을 때에는 답을 보고했기도 했고, 온전히 내가 푼것이 아니였기 때문에 다시 풀어보았다.