BOJ 25705 - 돌림판 문자열

BOJ 25705 - 돌림판 문자열

문제 링크



CODE

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).en()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f;
using namespace std;

int N, M;
string words, target;
int ans;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); std::cout.tie(NULL);
    cin >> N; cin >> words; cin >> M; cin >> target;

    int idx = N - 1; // 돌림판의 인덱스
    int turn = 0; // 회전수
    int tidx = 0; // 찾을 문자열의 인덱스

    while (1)
    {
        if (tidx == M) // 찾을 문자열을 완성했다면
            break ; // 반복문을 탈출함

        turn++; // 회전 수 추가
        idx++; // 돌림판을 1칸 전진시킴

        if (idx == N) // 인덱스가 돌림판보다 커지면
            idx = 0;  // 돌림판의 첫 문자로 돌아가게 됨

        // 돌림판의 문자가 만들 문자와 일치하면?
        if (words[idx] == target[tidx]) {
            tidx++; // 찾을 문자열의 인덱스를 전진시켜 목표를 갱신함
            ans += turn; // 회전수를 그대로 정답에 더해줌
            turn = 0; // 다시 회전수를 0으로 함
        }

        // 돌림판을 전부 회전했는데도 찾을 문자열의 문자를 찾지 못했다면
        if (turn >= N) {
            cout << -1; 
            return 0; // -1을 출력하고 반복문을 종료함
        }
    }
    
    cout << ans << '\n'; // 정답을 출력함
    return 0;
}

DESCRIPTION

  • 문자열은 내가 정말 어려워하는 타입의 알고리즘 문제이다. 이번 문제 같은 경우 거의 구현에 가까웠는데, 간만에 알고리즘을 풀어서 그런가 난이도에 비해 정말 어렵게 풀었다.

  • 지문이 그렇게 긴 편은 아니었는데, 난독(?)증세를 일으키면서 문제 이해에 상당히 애를 먹었다. 돌림판을 돌리고 액션을 취하는 코드를 짜야하는데, 먼저 액션을 하고 끝에 돌림판을 돌리는 코드를 짜놓고 맞왜틀을 외쳤다.

  • 또 돌림판이 한칸씩 딱딱 돌아가면서 횟수를 헤아리는데, 찾을 때 까지 돌려서 찾으면 횟수를 더해줘야 하는 줄 알았다.이정도면 그냥 문제를 새로 창조한 수준이 아닌지

  • 특이사항이 있는데, aacdbc와 같이 같은 문자가 2번 연속 나오는 경우, 첫 번째 a에서 돌림판을 맞춘다고 해서 횟수를 더하지 않고 두 번째 a를 찾은 것 취급할 수 없다. 일단 돌림판을 돌려버리고 시작하기 때문이다. 돌림판을 돌리고 액션을 취하는 코드를 짜야한다는 사실을 모를땐 이거도 이해가 잘 안됐다.

  • 일주일 안했다고 문해력이 이 정도로 박살날 줄이야… 역시 사람은 쉬지 않고 알고리즘을 해야하나보다.