백준 2866 - 문자열 잘라내기 (C++)

 

 

dobarz

adatak 

 

두 개의 문자열이 입력되었다고 치자.

이 때, 각 열을 준으로 문자열을 새로 만들게 되면, "da", "od", "ba", "at", "ra", "zk" 총 6개의 문자열이 만들어진다.

첫 번째 행의 문자열을 제거한 뒤, 동일한 방법으로 문자열을 만들게 되면, "a", "d", "a", "t", "a", "k" 총 6개의 문자열이 만들어진다.

 

처음에 만들었던 "da", "od", "ba", "at", "ra", "zk" 간에는 중복이 존재하지 않는다.

두 번째로 만든  "a", "d", "a", "t", "a", "k" 에는 "a"가 총 3번 중복되고 있다. 

 

즉, 기존의 문자열을 1개 제거했더니 열 문자열에서 중복되는 문자열이 발생한 것이다.

 

이처럼, 입력으로 주어진 문자열에서 몇 개를 지우면 열 문자열에서 중복되는 문자열이 발생하는지를 구하면 된다.

위의 예시에선 1을 답으로 출력하면 된다.

 

문제 풀이

아주 단순하게 접근하였다.

 

주어진 문자열을 기반으로 열 문자열을 만들어서 자료구조에 저장한 뒤, 맨 앞의 문자를 하나씩 지워가며 중복 검사를 진행한 것이다.

 

하지만, 문자열의 경우 맨 앞의 문자를 제거하면 뒤의 모든 문자를 앞으로 땡겨오는 연산을 해야하는 문제가 있다.

그러므로, 열 문자열을 저장할 때 앞뒤를 뒤집은 상태로 저장하고 맨 뒤의 문자를 제거하면서 중복 검사를 하였다.

 

중복검사는 unordered_set을 이용해서 하였다. unordered_set에 모든 문자열을 삽입한 뒤, 문자의 개수와 unordered_set의 size가 동일한지를 테스트하여 중복 여부를 검사하였다.

 

풀이 코드

int StrSize = 0;
int VecSize = 0;
std::cin >> StrSize >> VecSize;

std::vector<std::string> Vec(VecSize, std::string(StrSize, '0'));
for (int i = 0; i < StrSize; i++)
{
    for (int j = 0; j < VecSize; j++)
    {
        std::cin >> Vec[j][StrSize - 1 - i];
    }
}

 

벡터에 열 문자열을 모두 저장해주고 있다.

앞에서 말했던 것처럼, 열 문자열을 저장할 때 뒤집어서 저장을 해주고 있다.

 

int Count = 0;

for(int j = 0; j < StrSize; j++)
{
    for (int i = 0; i < VecSize; i++)
    {
        Vec[i].pop_back();
    }

    std::unordered_set<std::string> Strs;

    for (int i = 0; i < VecSize; i++)
    {
        Strs.insert(Vec[i]);
    }

    if (Strs.size() == VecSize)
    {
        Count++;
    }
    else
    {
        break;
    }
}

 

이후, 모든 문자열의 가장 마지막 원소(실제로는 열 문자열의 가장 앞 문자)를 제거해주었다.

그리고 unordered_set에 모든 문자열을 삽입하였고, unordered_set의 size와 기존 문자열의 개수와 동일한지를 검사하여 Count를 증가시키거나 반복문을 탈출하도록 분기를 두었다.

 

std::cout << Count;

return 0;

 

반복문이 끝나고 Count를 출력하면 끝이다.

 

코드 전문

#include <iostream>
#include <vector>
#include <unordered_set>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int StrSize = 0;
    int VecSize = 0;
    std::cin >> StrSize >> VecSize;

    std::vector<std::string> Vec(VecSize, std::string(StrSize, '0'));
    for (int i = 0; i < StrSize; i++)
    {
        for (int j = 0; j < VecSize; j++)
        {
            std::cin >> Vec[j][StrSize - 1 - i];
        }
    }

    int Count = 0;
    
    for(int j = 0; j < StrSize; j++)
    {
        for (int i = 0; i < VecSize; i++)
        {
            Vec[i].pop_back();
        }

        std::unordered_set<std::string> Strs;

        for (int i = 0; i < VecSize; i++)
        {
            Strs.insert(Vec[i]);
        }

        if (Strs.size() == VecSize)
        {
            Count++;
        }
        else
        {
            break;
        }
    }

    std::cout << Count;

    return 0;
}