문제

내용

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

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

풀이

풀이 시간

시작 시각	종료 시각	총 소요 시간
		30분

문제 분석

제약 사항 파악 & 테스트 케이스 작성

제한사항

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을 반환합니다.

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

solution(A, B) {
    // while 문 사용
        // A와 회전된 문자열 비교
            // - 같을 시 횟수 반환
        // B 회전
        // 횟수++
}

구현

1차 풀이

import java.util.Arrays;

class Solution {
    public int solution(String A, String B) {
        int lenA = A.length();
        char[] chars = B.toCharArray();
        char[] rotate = new char[lenA];
        int answer = 0;
        while (answer < lenA) {
            if (A.equals(String.valueOf(chars))) break;
            for (int i = 0; i < lenA; i++) {
                rotate[i] = chars[(i + 1) % lenA];
            }
            answer++;
            chars = Arrays.copyOfRange(rotate, 0, lenA);
        }
        return lenA == answer ? -1 : answer;
    }
}

Arrays.copyOfRange 사용이 성능적으로 비효율적인 것 같아 리팩토링을 진행한다.

2차 풀이

import java.util.ArrayDeque;

class Solution {
    public int solution(String A, String B) {
        int lenA = A.length();
        StringBuilder sb = new StringBuilder(B);

        for (int i = 0; i < lenA; i++) {
            if (A.equals(sb.toString())) return i;
            sb.insert(lenA, sb.charAt(0));
            sb.delete(0, 1);
        }
        return -1;
    }
}

sb.delete가 sb.insert보다 먼저 작성되길 바랐지만 그렇게 할 경우 sb.chartAt 코드에서 IndexOutOfRange 예외가 발생하여 이렇게 작성하였다.

복기하기

답안과 나의 풀이를 비교해보세요

class Solution {
    public int solution(String A, String B) {
        String tempB = B.repeat(3);
        return tempB.indexOf(A);
    }
}

파이썬의 경우 나도 이런 식으로 풀었는데 자바는 이렇게 풀기 싫었다.