Level 1. 문자열 나누기

Level 1. 문자열 나누기

 

 

처음에 문제의 조건을 x가 아닌 다른 글자들이 아니라 x가 아닌 다른 글자들 중으로 잘못 이해하여 정답률이 31%가 나왔다.

 

// 이 코드는 틀린 풀이이다.
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <climits>

using namespace std;

int solution(string s)
{
    int answer = 0;
    unordered_map<char, int> umap;

    for (int i = 0; i < s.length(); ++i)
    {
        ++umap[s[i]];

        int minCount = INT_MAX;
        
        for (pair<char, int> pr : umap)
        {
            if (pr.second == minCount)
            {
                s = s.substr(i + 1);
                ++answer;
                umap.clear();
                i = -1;

                break;
            }
            else
            {
                minCount = min(minCount, pr.second);
            }
        }
    }

    return answer + !!s.length();
}

 

질문하기 페이지에서 조건을 잘못 이해한 것을 깨닫고 각 문자의 개수가 아니라 나머지 문자들의 총 개수로 비교하여 해결했다.

 

풀고 나서 생각해보니 굳이 string.substr() 함수로 문자열을 나눌 필요도 없었다.

 

#include <iostream>
#include <unordered_map>

using namespace std;

int solution(string s)
{
    int answer = 0;
    int sum = 0;
    size_t length = s.length();
    unordered_map<char, int> umap;

    for (int i = 0; i < length; ++i)
    {
        ++sum;
        ++umap[s[i]];

        for (pair<char, int> pr : umap)
        {
            if (pr.second == sum - pr.second)
            {
                ++answer;
                sum = 0;
                umap.clear();

                break;
            }
        }
    }

    return answer + !!sum;
}

 

아래는 다른 사람의 풀이인데, 개수를 map에 저장하지 않고 이중 for문을 돌면서 모든 경우의 수를 계산하는 방법이다.

 

내 방법은 map에 존재하는 문자에 대해서만 확인하는 반면, 다른 사람의 방법은 i부터 이후의 모든 문자를 확인한다.

 

반복 횟수가 적어서 내 풀이가 더 빠를 줄 알았는데 아무래도 map 컨테이너를 사용해서 그런지 다른 사람의 풀이가 훨씬 빨랐다.

 

#include <iostream>

using namespace std;

int solution(string s)
{
    int answer = 0;
    int count = 0, otherCount = 0;
    int i, j;
    size_t length = s.length();
    
    for (i = 0; i < length; ++i)
    {
        for (j = i; j < length; ++j)
        {
            (s[j] == s[i]) ? ++count : ++otherCount;

            if (count == otherCount)
            {
                count = otherCount = 0;
                i = j;
                ++answer;

                break;
            }
        }
    }

    return answer + (i == j);
}