프로그래머스 | 문자열 밀기 [파이썬 python]

프로그래머스

 

처음 시도한 코드

def solution(A, B):
    Alist = list(A)
    
    idx = B.index(A[0])
    for i in range(len(Alist)):
        if i+idx >= len(A):
            Alist[(i+idx) % len(Alist)] = A[i]
        else:
            Alist[i+idx] = A[i]
            
    if Alist == list(B):
        return idx
    else:
        return -1

먼저, 주어진 테스트 케이스들을 보며 규칙을 찾아내었다.

B에서 A의 첫 번째 문자열이 위치한 인덱스를 찾으면 그 값이 A에서 오른쪽으로 이동한 횟수라고 생각하였다.

A를 이동 횟수만큼 이동시킨 문자열이 B와 같으면 그 이동 횟수가 답이 되는 것이고, 같지 않다면 불가능한 경우이므로 -1을 리턴한다. 

이 코드로 주어진 테스트 케이스는 모두 통과한다.

하지만 실제로 채점을 해보면 통과하지 못하는 케이스가 존재하였다.

 

 

A='abca', B='aabc'인 경우에는 위 코드를 통과하지 못한다.

A의 0번째 문자열인 a는 B에서 1번째에 위치한다. 그러므로 abca에서 aabc는 한 칸만 이동하면 된다. 

하지만, index() 함수는 같은 문자가 존재하면 앞쪽에 위치한 문자열의 인덱스 번호를 알려주기 때문에 우리가 의도한 대로 B에서 1번 인덱스를 리턴하는 것이 아니라 0번 인덱스를 리턴한다. 

이러한 이유로, 채점 시 통과하지 못하는 케이스가 존재했던 것이다.

 

그럼 어떻게 리스트 형태로 해결할 수 있을까 생각하다가 deque의 rotate() 함수가 떠올렸다.

 

정답 코드

from collections import deque

def solution(A, B):
    Alist = deque(A) # 데크
    Blist = deque(B) # 데크
    for i in range(len(Alist)):
        if Alist == Blist: # A와 B가 같아지면 이동 횟수 i 리턴
            return i
        Alist.rotate(1) # 오른쪽으로 1칸 이동
    return -1 # 불가능한 경우 -1 리턴

A와 B를 비교해야 하므로 둘 다 deque로 만들어 준다.

그런 다음 A를 1칸씩 이동하여 그 결과가 B와 같은 지 확인하는 것이다.

deque에서 아이템을 이동시키는 함수는 rotate()이다. 양수값을 넣으면 오른쪽으로, 음수값을 넣으면 왼쪽으로 이동한다.

우리는 오른쪽으로 한 칸씩 미는 문제이므로 rotate(1)을 해주었다.

A와 B가 같아지면 이동 횟수인 i를 리턴하여 답을 찾을 수 있다.

 

다른 사람의 코드 - find() 이용

def solution(A, B):
    B *= 2
    if A in B:
        return B.find(A)
    else:
        return -1

와 이렇게 간단하게 풀 수 있다니! 하고 크게 놀랐던 코드이다.

 

B가 A를 한 칸씩 밀어 가능한 문자열이라면 B를 반복했을 때 A가 B안에 들어있어야 한다.

예를 들어, A = 'abca', B='aabc'일 때 B * 2는 'aabcaabc'이다. 

B * 2에 A가 들어있고, 그 위치는 1번 인덱스이다.

 

이 과정이 if 문에 작성되어 있다. A가 B에 포함되어 있으면 A의 위치를 find() 함수로 찾아 리턴한다.

find() 함수는 abca에서 첫 번째 문자열의 위치를 리턴해주므로 1이 리턴된다.