프로그래머스 입문 120921 문자열 밀기

2026. 07. 15

문제

str1과 str2는 길이가 자연수인 문자열이다.
str1의 각 문자를 오른쪽으로 한 칸씩 밀어 str2를 만들려고 한다.
이때 str2를 만들 수 없다면 -1을 반환하고, 만들 수 있다면 필요한 최소 횟수를 반환하시오.

str1	str2	result
“abc”	“abc”	0
“hello”	“ohell”	1
“atat”	“tata”	1
“apple”	“elppa”	-1

풀이

뒤에서부터 앞 문자를 당겨 문자열 밀기

#include <stdlib.h>
#include <string.h>

int solution(const char* str1, const char* str2)
{
    if (strcmp(str1, str2) == 0)
    {
        return 0;
    }

    int len = strlen(str1);
    char* shifted = malloc(sizeof(char) * (len + 1));

    memcpy(shifted, str1, sizeof(char) * (len + 1));

    for (int i = 0; i < len - 1; i++)
    {
        char last_char = shifted[len - 1];

        for (int j = len - 1; j > 0; j--)
        {
            shifted[j] = shifted[j - 1];
        }

        shifted[0] = last_char;

        if (strcmp(shifted, str2) == 0)
        {
            free(shifted);
            return i + 1;
        }
    }

    free(shifted);
    return -1;
}

두 문자열이 같으면 원소를 밀 필요가 없으므로 바로 함수를 종료한다.
원본 문자열을 수정하지 않도록 str1을 shifted에 복사한 뒤, shifted의 문자를 직접 이동시킨다.

바깥 반복문은 문자열을 미는 횟수를 나타낸다.
반복문을 len - 1번만 수행하는 이유는 len번 밀면 문자열이 처음 상태로 돌아오기 때문이다.

0번: abc
1번: cab
2번: bca
3번: abc

이제 안쪽 반복문에서 문자열의 각 문자를 오른쪽으로 한 칸씩 밀어야 한다.
이는 문자열의 뒤에서부터 각 원소에 바로 앞 원소의 값을 복사하는 방식으로 구현할 수 있다.
예를 들어 "abc"에서는 먼저 마지막 원소인 'c'를 따로 저장한다.
그런 다음 2번 인덱스에 1번 인덱스의 값인 'b'를 복사하면 "abb"가 되고, 1번 인덱스에 0번 인덱스의 값인 'a'를 복사하면 "aab"가 된다.
마지막으로 저장해 둔 'c'를 0번 인덱스에 넣으면 "cab"가 완성된다.

문자열을 두 구간으로 나누어 비교하기

#include <string.h>

int solution(const char* str1, const char* str2)
{
    int len = strlen(str1);

    for (int shift_count = 0; shift_count < len; shift_count++)
    {
        int prefix_len = len - shift_count;

        if (strncmp(str1, str2 + shift_count, prefix_len) == 0
            && strncmp(str1 + prefix_len, str2, shift_count) == 0)
        {
            return shift_count;
        }
    }

    return -1;
}

이 풀이는 문자열을 실제로 밀지 않는다.
대신 str1을 두 구간으로 나누어 생각한 뒤, 오른쪽으로 밀었을 때 각 구간이 str2의 알맞은 위치에 있는지 비교한다.
예를 들어 str1이 "abc"이고 str2가 "bca"인 경우를 살펴보자.

shift_count가 0이면 prefix_len은 3 - 0 = 3이다.
따라서 첫 번째 strncmp는 str1의 앞 3글자와 str2의 0번 인덱스부터 3글자를 비교한다.

문자열을 밀지 않았을 때의 비교

str1: [ a b c ] = "abc"
str2: [ b c a ] = "bca"

첫 번째 비교: "abc"와 "bca"가 다르므로 거짓
두 번째 비교: shift_count가 0이므로 비교할 문자가 없음

첫 번째 비교가 거짓이므로 &&의 단락 평가에 따라 두 번째 strncmp는 실제로 호출되지 않으며, 다음 반복으로 넘어간다.

shift_count가 1이면 prefix_len은 3 - 1 = 2이다.
이는 str1을 앞쪽의 "ab"와 오른쪽으로 이동할 뒤쪽의 "c"로 나누는 경우다.

오른쪽으로 한 번 밀었을 때 예상되는 배치

str1:    [ a b ][ c   ] = "abc"
shifted: [ c   ][ a b ] = "cab"
str2:    [ b   ][ c a ] = "bca"

첫 번째 비교: str1[0..1]의 "ab"와 str2[1..2]의 "ca"가 다르므로 거짓
두 번째 비교: 첫 번째 비교가 거짓이므로 실행되지 않음

str1을 오른쪽으로 한 번 밀면 "cab"가 되지만 str2는 "bca"이므로 두 문자열은 일치하지 않는다.
코드의 첫 번째 strncmp는 밀고 난 뒤 뒤쪽에 놓일 "ab"가 str2의 뒤쪽인 "ca"와 같은지 먼저 확인한다.
코드에서는 첫 번째 비교부터 거짓이므로 이때도 두 번째 strncmp는 실제로 호출되지 않고 다음 반복으로 넘어간다.

shift_count가 2이면 prefix_len은 3 - 2 = 1이다.
이는 str1을 앞쪽의 "a"와 오른쪽으로 이동할 뒤쪽의 "bc"로 나누는 경우다.

오른쪽으로 두 번 밀었을 때 예상되는 배치

str1:    [ a   ][ b c ] = "abc"
shifted: [ b c ][ a   ] = "bca"
str2:    [ b c ][ a   ] = "bca"

첫 번째 비교: str1[0]의 "a"와 str2[2]의 "a"가 같으므로 참
두 번째 비교: str1[1..2]의 "bc"와 str2[0..1]의 "bc"가 같으므로 참

두 비교가 모두 참이므로 str1을 오른쪽으로 2번 밀면 str2가 된다는 뜻이며, 함수는 2를 반환한다.