[C++] 백준 1157번: 단어 공부

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

1157번: 단어 공부

 

문제는 별 것 없다.. 

문자열 중 가장 많이 포함된 문자 하나를 출력하면 된다. 

 

 

일단 내 코드는 40ms.. 최적화? 그런거 신경 안 쓰고 쉬운 문제는 쉽게 푸는게 답이라고 생각하는 사람이라 넘겼다..

그런데 채점 현황에서 c++17로 12ms대로 풀어버린 것을 봤다. 

 

참을 수 없었다..

 

그래서 리팩토링을 했지만 오히려 4ms나 더 늘어버려서 글을 남긴다.

왤까... 정말 왤까?....

 

---

 

40ms 코드

- 이 함수는 들어오는 문자열의 길이 n만큼 함수를 호출한다. 

#include <iostream>
#include <vector>
#include <algorithm>

const int NULL_STR = '\0';

char lower2uppder(const char c)
{
    if(96 < c && c < 123) return (char)(c-32);
    return c;
}

int main() {

    std::vector<int> arr(32, 0);
    std::string input;
    
    std::cin >> input;

    char uc;
    int idx;
    int max_value = 0;
    char answer;
    
    for(int i=0; i<input.size(); ++i)
    {
        uc = lower2uppder(input[i]);
        //std::cout << uc << std::endl;
        idx = uc-64;
        ++arr[idx];
        if(max_value < arr[idx])
        {
            max_value = arr[idx];
            answer = uc;
        }
    }
    
    std::sort(arr.rbegin(), arr.rend());
    bool isMulti = false;
    int tmp = arr[0];
    for(int i=1; i<arr.size(); ++i)
    {
        if(arr[0] == arr[i])
        {
            isMulti = true;
        }
        break;
    }
    
    if(isMulti)
        std::cout << "?";
    else
        std::cout << answer;

    return 0;
}

 

 

44ms 코드

- 함수 호출 대신 모듈러 연산을 한다. 

- 정답을 출력할 때 딱 한 번 함수를 호출한다. 

#include <iostream>
#include <algorithm>
#include <vector>

char lower2uppder(const char c)
{
    if(96 < c && c < 123) return (char)(c-32);
    return c;
}

int main() {
    
    std::vector<int> arr(33, 0);
    std::string input;
    std::cin >> input;

    char answer;
    for(int i=0; i<input.size(); ++i)
    {
        ++arr[input[i]%32];
        if(arr[input[i]%32] > arr[answer%32])
        {
            answer = input[i];
        }
    }
    
    std::sort(arr.rbegin(), arr.rend());
    if(arr[0] == arr[1])
        std::cout << "?";
    else
        std::cout << lower2uppder(answer);

    return 0;
}

 

 

정렬하는 것도 똑같고, 로직이 대부분 비슷한데 왜 시간이 더 나올까? 

솔직히 코드2가 1초라도 덜 나왔으면 글도 안 남겼다..

 

 

---

그래서 어떻게 하면 시간을 줄 일 수 있나? 

 

일반적으로 cout보다 printf가 더 빠르기 때문에 12ms 연산이 가능한게 아닐까 라는 가설도 틀렸다. 

printf로 바꾼 후 44 -> 48이 됐다. (12ms 코드에서 printf를 썼음)

12ms 사람은 cpp인데 입출력을 scanf/printf를 쓴게 가장 큰 시간 절약한 방법인 것 같다. 

#include <iostream>
#include <algorithm>
#include <vector>

char lower2upper(const char c)
{
    if(96 < c && c < 123) return (char)(c-32);
    return c;
}

int main() {
    
    std::vector<int> arr(33, 0);
    std::string input;
    std::cin >> input;

    char answer;
    for(int i=0; i<input.size(); ++i)
    {
        ++arr[input[i]%32];
        if(arr[input[i]%32] > arr[answer%32])
        {
            answer = input[i];
        }
    }
    
    std::sort(arr.rbegin(), arr.rend());
    if(arr[0] == arr[1])
        printf("?");
    else
        printf("%c", lower2upper(answer));
    
    return 0;
}

 

 

정답은 역시 로직이 아니라 입출력이었긴 하다. 아래 코드를 넣고 나도 12ms에 진입할 수 있었다. 

그래도.. 코드1과 코드2의 속도 차이 원인은 아직도 모르겠다..! 

    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

근데 입출력부분을 고치면 로직이 아니라 꼼수를 쓴거같아서 마음이 좀 찝찝하다..