[프로그래머스][C++] 문자열 밀기

문자열 밀기

문제 링크

문자열 밀기

분석

문자열 A를 한 칸씩 오른쪽으로 밀고, 가장 마지막에 위치한 문자를 맨 앞으로 옮겨야합니다.
이때, A를 몇 번 밀어야 B와 같아지는지 최소 횟수를 구하여 반환해야합니다.

만약 B를 만들 수 없는 경우 -1을 반환해야합니다.

풀이

#include <string>

using namespace std;

int solution(string A, string B) {
    // A와 B의 길이는 같기 때문에 한 문자열의 길이만큼 반복합니다.
    for (int i = 0; i < A.size(); ++i)
    {
        // A와 B가 같은 경우 현재 횟수를 반환합니다.
        if (A == B)
        {
            return i;
        }
        
        // 마지막 글자
        char lastChar = A.back();
        // 마지막 글자 + 마지막 글자를 제외한 문자열
        A = lastChar + A.substr(0, A.size() - 1);
    }
    
    // 반복문을 다 돌아도 같은 경우를 찾지 못했다면 -1을 반환합니다.
    return -1;
}

성능 요약

시간 복잡도는 $O(n^2)$입니다.

• A문자열의 크기만큼 반복하는 반복문 $O(n)$
• A문자열의 부분 문자열을 생성하는 substr $O(n)$
• 글자를 한칸씩 민 문자열의 생성 $O(n)$
• $O(n) \times (O(n) + O(n))$

공간 복잡도는 $O(n)$입니다.

• A문자열의 부분 문자열을 생성 $O(n)$
• 글자를 한칸씩 민 문자열의 생성 $O(n)$
• $O(n) + O(n)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.02MB)
테스트 2 〉 통과 (0.01ms, 4.13MB)
테스트 3 〉 통과 (0.01ms, 4.18MB)
테스트 4 〉 통과 (0.02ms, 4.21MB)
테스트 5 〉 통과 (0.01ms, 4.12MB)
테스트 6 〉 통과 (0.01ms, 4.14MB)
테스트 7 〉 통과 (0.01ms, 3.68MB)
테스트 8 〉 통과 (0.02ms, 4.14MB)