BOJ 1157 - 단어 공부

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

1157번: 단어 공부

 

처음 이 문제를 풀었을 때는, algorithm 헤더의 count 함수를 이용해서 

문자열에 포함된 각 문자들의 갯수를 카운팅하려 했다.

 

그러나 한가지 간과한것이 있었는데,

algorithm 헤더의 count() 함수에 대한 시간 복잡도가 O(N) 이기 때문에

입력 받은 문자열 기준 한바퀴를 도는 포문 O(N) 과 겹쳐서, O(N^2) 의 시간 복잡도를 갖는 코드가 되었고,

계속 시간초과가 발생하였다

 

그래서 다음과 같이 수정해서 코드를 작성해야 했다.

 

- c++

#include <iostream>
 
using namespace std;
 
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
 
    string str;
 
    cin >> str;
 
    int str_len = str.size();
    int alphabet_cnt[100] = {
        0,
    };
 
    for (char ch : str) {
        if ('a' <= ch) ch -= 32;
        alphabet_cnt[ch]++;
    }
 
    char answer;
    int max_cnt = 0;
    for (int i = 'A'; i <= 'Z'; i++) {
        if (max_cnt < alphabet_cnt[i]) {
            max_cnt = alphabet_cnt[i];
            answer = i;
        } else if (max_cnt == alphabet_cnt[i]) {
            answer = '?';
        }
    }
 
    printf("%c", answer);
 
    return 0;
}

 

 

 

이 문제를 통해 알 수 있었던것은

 

1. 아스키 코드를 이용해서 대소문자 전환을 하자

2. 문자열 갯수 세는 것을 배열을 이용해서 처리하자. 

 

이다.

 

 

- 참조

https://hibee.tistory.com/48