구름톤 챌린지 2주차 학습 일기(1)

서론

완전 탐색 문제를 제공하는 2주차가 시작되었다.

1주차 문제는 쉬웠는데, 오늘 푼 2주차 문제는 문자열과 순열 그리고 unique를 사용하게되어 복잡해서 푸는 맛이 있었다.

2주차 1일 캐릭터

5일차 문자열 나누기

문제 요약 : 문자열을 받고, 3개로 분할 하여 한 세트를 만들고, 모든 세트들을 합쳐서 정렬한 배열을 만들어서, 한 세트의 문자열이 정렬한 배열에서 몇 번째 인덱스에 해당되는지를 더해서 최대 값을 정답으로 출력하는 문제이다.

 

조합을 통해서 문자열을 자를 위치를 지정해 잘라서 문자열을 P와 Plist에 저장해주고

P에서 정렬제거와 중복을 제거한뒤

Plist의 3개씩 각각 점수를 계산하여 최댓 값을 출력해준다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> P;
vector<string> Plist;
int main()
{
    int N, answer = 0;
    cin >> N;
    cin.get();
    string S;
    getline(cin, S);

    for (int i = 1; i < N; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            P.push_back(S.substr(0, i));
            P.push_back(S.substr(i, j - i));
            P.push_back(S.substr(j, S.size() - j));
            Plist.push_back(S.substr(0, i));
            Plist.push_back(S.substr(i, j - i));
            Plist.push_back(S.substr(j, S.size() - j));
        }
    }
    sort(P.begin(), P.end());
    P.erase(unique(P.begin(), P.end()), P.end());


    for (int i = 0; i < Plist.size(); i += 3)
    {
        int bufAnswer = 0;
        for (int j = i; j < i + 3; j++)
        {
            for (int k = 0; k < P.size(); k++)
            {
                if (P[k] == Plist[j])
                {
                    bufAnswer += k + 1;
                }
            }
        }
        if (bufAnswer > answer)
        {
            answer = bufAnswer;
        }
    }

    cout << answer;
}

배운 점

 

문자열의 중복을 제거하는 방법이 기억이 애매했는데 이번 문제를 통해서 

unique를 통하여 중복되는 값을 뒤로 보낸뒤,

반환값(중복되는 값의 시작 위치)부터 끝까지 erase를 사용해서 지워서 문자열을 정리했다.

sort(P.begin(), P.end());
    P.erase(unique(P.begin(), P.end()), P.end());

 

느낀 점

문자열을 다루는 문제이다 보니 substr, sort, erase 와 같은 라이브러리를 사용하였는데 잘 알지 못해 검색해서 사용했기 때문에 내가 아직 문자열에 대해 부족함을 느꼈다.

 

그리고 중복되는 문자열을 제거한 배열에서 점수를 계산해야 되는데 처음에 정렬하지 않아 문제 분석들 더 철저하게 해야해야겠다.

 

마지막으로 반복문의 매개변수를 잘못써서(Plist 대신 P) 모든 문자열 세트의 점수를 계산하지 않아 해매어서, 코드를 짤 떄 정신을 차리고 짜야겠다는 것과 이러한 오류를 빠르게 잡기 위해, 코드를 읽어보는 능력을 길러야 겠다.

    sort(P.begin(), P.end());
    P.erase(unique(P.begin(), P.end()), P.end());


    for (int i = 0; i < Plist.size(); i += 3)
    {
        int bufAnswer = 0;
        for (int j = i; j < i + 3; j++)
        {
            for (int k = 0; k < P.size(); k++)
            {
                if (P[k] == Plist[j])
                {
                    bufAnswer += k + 1;
                }
            }
        }
        if (bufAnswer > answer)
        {
            answer = bufAnswer;
        }
    }

어려웠던 점

처음에 완점탐색으로 풀지 않는다고 생각했을 떄 막막함을 느꼈었다.

숨겨진 문제풀이 방법이 있진 않을까? 라는 생각을 했었는데

코딩테스트는 다른 방법이 생각나지 않는다면 완전 탐색으로 일단 구현하는것이 맞는데 다른 풀이 방법에 너무 몰두해서 시간을 많이 쓴점이 아쉬웠다.

 

그리고 문제를 이해하는데에 있어서도 어려움을 겪었는데, 여러번 읽고나서야 문제를 이해하였다.