[프로그래머스/C++ 문제 풀이] Lv. 0 - 문자열 밀기

문제 설명

문자열 "hello"에서 각 문자를 오른쪽으로 한 칸씩 밀고 마지막 문자는 맨 앞으로 이동시키면 "ohell"이 됩니다. 이것을 문자열을 민다고 정의한다면 문자열 A와 B가 매개변수로 주어질 때, A를 밀어서 B가 될 수 있다면 밀어야 하는 최소 횟수를 return하고 밀어서 B가 될 수 없으면 -1을 return 하도록 solution 함수를 완성해보세요.

제한 사항

• 0 < A의 길이 = B의 길이 < 100
• A, B는 알파벳 소문자로 이루어져 있습니다.

입출력 예

A	B	result
"hello"	"ohell"	1
"apple"	"elppa"	-1
"atat"	"tata"	1
"abc"	"abc"	0

 

입출력 예 #1

• "hello"를 오른쪽으로 한 칸 밀면 "ohell"가 됩니다.

입출력 예 #2

• "apple"은 몇 번을 밀어도 "elppa"가 될 수 없습니다.

입출력 예 #3

• "atat"는 오른쪽으로 한 칸, 세 칸을 밀면 "tata"가 되므로 최소 횟수인 1을 반환합니다.

입출력 예 #4

• "abc"는 밀지 않아도 "abc"이므로 0을 반환합니다.

---

문제 풀이

이번 문제는 약간의 아이디어가 있다면 간편하게, 아니라면 조금은 무식하게 풀이가 가능한 문자열 관련 문제였습니다.

 

저는 조금 무식한 방식으로 문자열의 맨 뒤 문자를 맨 앞으로 옮겨주는 방식을 통해 풀게 되었지만...

간단히 이야기하자면 결국 문자열 A를 회전시켜 B를 만들어야 하는 문제이므로 다음과 같이 생각할 수 있습니다.

 

[ B를 2번 이어서 붙인 경우 해당 문자열 안에 문자열 A가 존재해야만 밀어서 만들 수 있는 문자열 ]

 

즉, "BCA" 문자열을 밀어서 "ABC" 문자열을 만들어야 한다면

[ ABCABC ] 라는 문자열에서 "BCA" 문자열이 존재한다면 가능한 경우입니다.

 

심지어 위 문자열에서 BCA의 첫 인덱스는 1로, "BCA" 문자열을 우측으로 1회 밀면 "ABC" 문자열이 만들어지게 됩니다.

 

다른 예시로 "Hello" 문자열로 "lloHe" 문자열을 만들어보도록 하겠습니다.

위와 동일하게 "lloHe" 문자열을 2번 이어 붙인다면 [ lloHelloHe ] 문자열이 되며, 첫 'H'는 3번 인덱스에 위치해 있는 것을 확인할 수 있습니다.

 

즉, Hello -> oHell(1회) -> loHel(2회) -> lloHe(3회) 와 결과가 동일하며 이를 활용해 find() 함수로 다음과 같이 간단히 풀이가 가능합니다.

#include <string>

using namespace std;

int solution(string A, string B)
{
    B += B;
    return B.find(A);
}

다음으로는 제가 무식하게 문자열을 직접 수정하며 풀이한 결과물입니다..

 

정답 코드

풀이 시간 : 20m 13s

1회 오답 이유 : 우측 or 좌측으로 문자열을 밀어 최소 횟수를 구하는 것으로 생각하여 오답..

#include <string>
#include <vector>

using namespace std;

int solution(string A, string B) {
    int answer = 0;

    // 문자열이 같다면 굳이 실행해보지 않고 종료합니다.
    if (A == B)
    {
        return answer;
    }

    string tempStr = A;

    // 카운트 저장용 변수
    int rCount = 0;

    // right 방향으로 밀기
    for (int i = 0; i < tempStr.length(); i++)
    {
        // 맨 뒤에 위치한 문자를 저장합니다.
        char tmp = tempStr[tempStr.length() - 1];
        // 맨 뒤에 위치한 문자를 제거합니다.
        tempStr.erase(tempStr.length() - 1);
        // 맨 앞에 해당 문자를 추가합니다.
        tempStr = tmp + tempStr;

        // 만약 tempStr과 B가 동일한 문자열이라면?
        if (tempStr == B)
        {
            // 해당 인덱스 + 1을 저장합니다.
            rCount = i + 1;
            break;
        }
    }

    // 결과 출력용
    if (rCount == 0)
    {
        answer = -1;
    }
    else
    {
        answer = rCount;
    }

    return answer;
}