[백준 20437][💛5] 문자열 게임 2

🚀 난이도

💛 골드 5

🚀 문제

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

🚀 내 풀이

푼 지가 꽤 오래되어 가물가물 하지만… 오랜 시간 고민하다가 포기하고 구글링했던 문제로 기억한다..⭐ 내가 크게 간과했던 것은 3 번과 4 번을 별개로 생각했던 것이다. 3 번은 어떤 문자를 정확히 K 개 포함하면서 가장 짧은 연속 문자열의 길이 를 구하는 것이기 때문에 4 번처럼 문자열의 첫 번째와 마지막 글자가 같아야할 수 밖에 없다 ! ! !

그렇기 때문에 3, 4 번 이 둘을 별개로 생각하지 않고, 어떤 문자를 정확히 K 개 포함하고 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 문자열들을 구하고 최소 길이와 최대 길이를 구하면 된다.

🔥 첫 번째 풀이

코드 출처 블로그 https://taxol1203.github.io/codingtest/bj-%EB%AC%B8%EC%9E%90%EC%97%B4-%EA%B2%8C%EC%9E%842/

위 링크의 풀이를 참고하였다.

• 1️⃣ str 의 알파벳 문자별로 등장 빈도수를 저장한다.
• 2️⃣ K 와 같거나 K 보다 큰 빈도수를 가진 문자들만을 대상으로(이때 이 문자가 부분 문자열의 시작 문자가 됨), 해당 문자를 만날 때마다, 즉 동일한 문자를 만날 때마다 카운트 하고(이 과정에서 자동으로 시작 문자와 끝 문자가 같게 됨) 그 카운트 수가 K 가 되었을 때 최소 길이, 최대 길이를 업데이트 하면 된다.
  • 나는 처음에 count[str[i] - ‘a’] == K 에 해당하는 문자만 해야하지 않을까? 왜지? 하고 생각했었다. 근데 아니다 !!!!! K 개 미만으로 적은 문자들에 대해서는 조건에 만족하는 부분 문자열을 구할 수 조차 없기에 넘어가야 하는게 맞지만, K 개 이상인 문자들에 대해서는 충분히 그 안에서도 K 개의 부분 문자열을 만들 수 있기 때문이다. 예를 들어 abcafa 라는 문자열이 있고 K 가 2 라고 가정해보자면, a 는 3 번 등장하므로 K 와 일치하지는 않지만 abca 혹은 afa 혹은 abcafa 이런 K = 2 개가 속한 문자열을 만들 수 있는 것이다. 내가 착각했었던 부분이다. 따라서 count[str[i] - ‘a’] >= K 조건에 만족하는 문자들에 대해서만 진행해야 하는 것이 맞다.

#include <bits/stdc++.h>

using namespace std;

int main() {
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while(T--) {
        string str; 
        int K; 
        cin >> str;
        cin >> K;
        
        // str 의 알파벳 문자별로 등장 빈도수 저장
        vector<int> count(26);
        for (int i = 0; i < str.length(); i++)
            ++count[str[i] - 'a']; // ex) count[0] = 3 은 'a' 가 str 에 3 번 등장했다는 뜻
        
        int answer3 = INT_MAX; 
        int answer4 = -1;
        for (int i = 0; i < str.length(); ++i) {
            // ⭐ 빈도수가 K 개 미만인 문자들은 문자열도 못 만들므로 패스
            if (count[str[i] - 'a'] < K)
                continue;

            int cnt = 0;
            for (int j = i; j < str.length(); ++j) {  // 연속 문자열의 시작 문자 str[i]
                if (str[i] == str[j])  // str[j] 와 같다면 카운팅! (자동으로 시작문자 = 끝문자 인 연속 문자열이 되는 것이나 마찬가지)
                    ++cnt;
                
                if (cnt == K) {  // 카운트 수가 K 와 같을 때 길이 업데이트
                    answer3 = min(answer3, j - i + 1);
                    answer4 = max(answer4, j - i + 1);
                    break;
                }
            }
        }
        
        if (answer3 == INT_MAX || answer4 == -1) 
            cout << -1 << "\n";
        else 
            cout << answer3 << " " << answer4 << "\n";
    }
}

🔥 두 번째 풀이 (투포인터)

코드 출처 블로그 https://blog.naver.com/PostView.nhn?blogId=gustn3964&logNo=222291615095&categoryNo=0&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView

아이디어가 좋은 풀이라고 느꼈다!

• 1️⃣ 이차원 배열을 선언하여 문자(인덱스)별로 그 문자가 등장하는 위치 인덱스들을 저장한다.
• 2️⃣ 어차피 어떠한 문자로 시작하고 끝이나는 문자열을 구해야하는 것이기 때문에 문자 별 위치 인덱스들에서 두 포인터가 가리키는 인덱스의 사이에 K 개 만큼의 고정적인 문자 수를 유지한 채로 두 포인터를 한 칸씩 옮겨나가면 된다.
  • 예를 들어 a 문자가 5, 8, 13, 15 위치에 있고 (즉, alpha_pos[0] 는 {5, 8, 13, 15}) K 가 3 이라면 투포인터는 차례로 (5, 13) -> (8, 15) 이 순서로 각각 가리키게 된다. 5 와 13 위치엔 같은 문자가 있으며 5 와 13 사이엔 5, 8, 13 이렇게 K = 3 개의 동일한 문자가 있게 된다. 마찬가지로 8, 15 위치엔 같은 문자가 있으며 8 과 15 사이엔 8, 13, 15 이렇게 K = 3 개의 동일한 문자가 있게 된다.
  • alpha_pos[문자] 해당 문자의 위치들이 기록된 배열(전부 동일한 문자를 가리키는 위치들)에서 사이에 K 개의 문자가 포함되도록 거리를 유치한 채 두 포인터를 모두 1 씩 증가하면 됨
  • 따라서 왼쪽 포인터는 alpha_pos[문자][0] 을 가리키는 것 에서, 오른쪽 포인터는 alpha_pos[문자][K - 1] 을 가리키는 것에서 출발한다. (초기값)

#include <bits/stdc++.h>

using namespace std;

int main() {
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    for (int i = 0; i < T; i++) {
        string str; 
        int K;
        cin >> str;
        cin >> K;

        vector<int> alpha_pos[26];
        int answer3 = INT_MAX; int answer4 = -1;
         
         // 문자(인덱스)별로 그 문자가 등장하는 위치 인덱스들을 저장
        for (int j = 0; j < str.length(); j++) 
            alpha_pos[str[j] - 'a'].push_back(j);
        
        for (int j = 0; j < 26; j++) {
            if (alpha_pos[j].size() >= K) {
                int l = 0; 
                int r = K - 1;

                int temp3 = alpha_pos[j][r] - alpha_pos[j][l] + 1; 
                int temp4 = alpha_pos[j][r] - alpha_pos[j][l] + 1;
                while (r < alpha_pos[j].size() - 1) {
                    r++; 
                    l++;
                    temp3 = min(alpha_pos[j][r] - alpha_pos[j][l] + 1, temp3);
                    temp4 = max(alpha_pos[j][r] - alpha_pos[j][l] + 1, temp4);
                }
                answer3 = min(temp3, answer3);
                answer4 = max(temp4, answer4);
            }
        }
        if (answer3 == INT_MAX) 
            cout << -1 << "\n";
        else 
            cout << answer3 << " " << answer4 << "\n";
        
    }
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기