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

Lv0_문자열 밀기

📄Description

문자열 "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을 반환합니다.

---

🤔생각 정리

1. 재귀를 사용해서 풀 수 있겠네.
   • 탈출조건 1) A == B
   • 탈출조건 2) A를 돌려 다시 A가 될 때까지 B가 될 수 없는 경우
   • 인자) A, B, 횟수
2. 문자열을 하나씩 밀면서 횟수를 세면 되겠네.

💡Pseudo Code💡

1. 탈출조건 1) A == B: return cnt
2. 탈출조건 2) B를 만들 수 없다면: return -1 
3. 반복) A = 문자열 1 칸 밀기 cnt += 1

---

🖥️코드화

# 문자열 밀면서 확인하는 재귀 함수
def valid(a, b, cnt=0):
    if a == b:
        return cnt
    if cnt == len(a): # B를 만들 수 없다면
        return -1
    return valid(a[-1]+a[:-1], b, cnt+1)

def solution(A, B):
    return valid(A, B)

---

📌코드 비교 및 감상

1. 문자열의 반복 활용
   문자열을 밀면서 단어를 만들기 때문에 2배의 문자열 내에서 발견이 된다는 사실을 활용하여 문제를 해결할 수 있다.
   (정말 세상에는 다양한 문제 풀이가 있다...😂)
   
   코드를 인용하자면 이렇다.
   1) 두 배의 문자열을 생성한 후 find함수를 통해 생성 가능한 단어인지 확인한다.
   이때, find함수가 찾고자 하는 문자열이 없을 때 -1을 return한다.
   (이런식으로 결과를 사용할 수 있다는 사실을 알고 있어야 겠다.)
   2) 여기에 더해 함수가 간단해지니까 lambda를 사용해 더 간단하게 함수를 작성했다.

solution = lambda a,b:(b*2).find(a)

2. 덱 활용
   덱 자료구조의 rotate 함수를 활용해서 문자열을 밀면서 문제를 해결할 수 있다.
   (자료구조를 더 공부해야 겠다..😥)
   
   코드를 인용하자면 이렇다.

from collections import deque

def solution(A, B):
    a, b = deque(A), deque(B)
    for cnt in range(len(A)):
        if a == b:
            return cnt
        a.rotate(1)
    return -1