[백준][C++] 20437 문자열 게임 2

20437. 문자열 게임 2

20437번: 문자열 게임 2

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

보자마자 엄청 어려울 것 같은 문제였지만... 3번과 4번 조건을 하나하나씩 정복하면 꽤 쉬운 문제였다.

 

하지만... 개행을 안 하는 치명적인 실수로 5번을 광탈한 다음에... 가장 최상의 코드로 도전을 해봤는데도 광속 탈락이길래 이상해서 출력이 잘못된 것 아닌가 의심을 했는데...

혹시나 했더니 역시나... 개행을 안 해줬던 것이다... 바보!!!!!

 

사소한 실수임에도 꽤 얻은 게 있다. 5번의 탈락으로 코드를 깔끔하고 효율적이게 정리했고, 코드의 길이를 2배 정도 줄일 수 있었다!

 

처음 접근은...

 

1. 알파벳마다 queue를 생성해주고, 알파벳 개수(26)개의 길이인 최단길이 배열, 최장길이 배열을 생성해준다.

queue =>

알파벳이 K개 들어있는 최단, 최장거리를 갱신해주기 위함.
최단길이, 최장길이 배열 => 알파벳의 최단길이, 최장길이를 저장하기 위함.

 

 

2. 해당 알파벳의 queue의 길이가 K-1을 넘어가면, queue의 front와 현재 위치의 거리를 구해주고 pop해준다.

 

3. 문자열을 돌아가며 queue에 해당 문자의 위치를 넣어준다.

 

4. 2~3을 문자열이 끝날 때까지 반복한다.

 

5. 3에서 나온 거리 중에 가장 작은 값과 큰 값을 출력한다.

이때, 작은 값의 변수와 큰 값의 변수가 초깃값과 같다면 어떤 문자를 K개 포함하지 않으므로 -1을 출력한다.

 

코드

#include<iostream>
#include<queue>
using namespace std;

int main()
{
    int tCnt;
    cin >> tCnt;

    while (tCnt--)
    {
        string str;
        queue<int> alphabets[26];
        int minDists[26], maxDists[26], num;
        int result1 = 10001, result2 = -1;
        cin >> str >> num;

        fill_n(minDists, 26, 10000);
        fill_n(maxDists, 26, 0);

        for (int i = 0; i < str.size(); i++)
        {
            int idx = str[i] - 'a';

            if (!alphabets[idx].empty() && alphabets[idx].size() == num - 1)
            {
                int dist = i - alphabets[idx].front() + 1;

                // 조건 3
                if (dist < minDists[idx])
                {
                    minDists[idx] = dist;

                    if (dist < result1)
                        result1 = dist;
                }

                // 조건 4
                if (dist > maxDists[idx])
                {
                    maxDists[idx] = dist;

                    if (dist > result2)
                        result2 = dist;
                }

                alphabets[idx].pop();
            }

            alphabets[idx].push(i);
        }

        if (result1 > 10000 && result2 < 0)
        {
            // 이때 개행을 안 했다...
            if (num == 1)
                cout << "1 1";
            else
                cout << -1;
        }
        else
            cout << result1 << ' ' << result2 << '\n';
    }
}

 

개행을 안 했으니 결과는 광속 탈락... 이었지만... 코드를 자세히 보다 필요 없는 부분을 떼어냈다.

 

• 최단길이와 최장길이를 알파벳별로 저장하는 배열을 제거했다.
  • 알파벳에 상관 없이 최단길이, 최장길이를 구하면 되므로 굳이 필요가 없었던 배열이었기 때문이다.
• queue의 push하는 것을 길이를 구하는 것보다 먼저 했다.
  • 입력이 1 >= K >= W이므로 1도 포함이 된다. 길이를 먼저 구하면 queue의 size가 0이 되어 별도로 처리를 해주어야 하는데, 먼저 푸쉬하면 그럴 필요가 없다!

 

이 개선점을 반영해서 작성한 코드이다.

#include<iostream>
#include<queue>
using namespace std;

int main()
{
    int tCnt;
    cin >> tCnt;

    while (tCnt--)
    {
        string str;
        queue<int> alphabets[26];
        int result1 = 10001, result2 = -1, num;
        cin >> str >> num;

        for (int i = 0; i < str.size(); i++)
        {
            int idx = str[i] - 'a';

            alphabets[idx].push(i);

            if (alphabets[idx].size() == num)
            {
                int dist = i - alphabets[idx].front() + 1;

                result1 = min(dist, result1);
                result2 = max(dist, result2);

                alphabets[idx].pop();
            }
        }

        if (result2 < 0)
            cout << -1 << '\n';

        else
            cout << result1 << ' ' << result2 << '\n';
    }
}

고친 것도 개행이 없어서 바로 틀렸습니다가 나왔었다...

이상해서 뚫어져라 쳐다보는데 개행이 빠진 걸 발견했다..

이 바보!!!!!!!!!!!!!!

 

그래도 코드를 나름 깔끔하게 잘 짠 것 같아서 기분이 좋다!!!!