[Programmers] #120921 - 문자열 밀기 [Java][C++][Python]

문제 링크

---

1. 아이디어

문자열 A와 B가 주어지며 A를 밀어서 B가 될 수 있다면 밀어야 하는 최소 횟수를 구하는 문제다. 문자열 밀기는 각 문자를 오른쪽으로 한 칸 밀고 마지막 문자를 맨 앞으로 이동시키므로 A와 B가 동일한지 판단하고 동일하지 않다면 문자열 밀기를 하는 과정을 다시 초기 A로 돌아올 때까지 반복하면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N^2)$	$O(N)$

($N$ = A의 길이. Java·Python은 매 반복 새 문자열을 만들어 공간 $O(N)$, C++는 rotate로 제자리 회전해 공간 $O(1)$)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(String A, String B) {
        int len = A.length();
        for (int i = 0; i < len; i++) {
            if (A.equals(B)) return i;
            A = A.substring(len - 1) + A.substring(0, len - 1);
        }

        return -1;
    }
}

#include <bits/stdc++.h>
using namespace std;

int solution(string A, string B) {
    for (int i = 0; i < A.size(); i++) {
        if (A == B) return i;
        rotate(A.begin(), A.end() - 1, A.end());
    }

    return -1;
}

std::rotate를 활용하면 간단하게 문자열 밀기를 할 수 있다.

def solution(A, B):
    for i in range(len(A)):
        if A == B:
            return i
        A = A[-1] + A[:-1]

    return -1

---