[프로그래머스][PYTHON] Lv. 0 문자열 밀기

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/120921

프로그래머스

 

내 풀이

처음 풀이(틀림)

def solution(A, B):
    answer = 0
    # B에서 A 첫번째 글자는 어디에 위치하는가?
    idx = B.index(A[0])
    
    # B에서 A의 첫 번째 글자부터 문자열과 그 전의 문자열을 합쳐서 A와 같으면 idx 값을 answer로
    if (B[idx:] + B[:idx]) == A:
        answer = idx
    else:
        answer = -1
    return answer

 

위와 같이 진행했을 때, 주어진 테스트 케이스는 모두 정답이었다. 그러나 실제 평가에서는 2, 4, 7번에서 실패가 발생하였다. 

 

여러가지 케이스들을 추가하여 찾아보았는데, 한 가지 케이스에서 오류가 나는 것을 발견하였다. 

 

즉, 나는 B에서 A의 첫 번째 글자가 어디있는지 판단하여 풀었지만, A의 첫 번째 글자와 마지막 글자가 같아서 제대로된 인덱스 값을 찾지 못한게 문제였다. 

 

수정 풀이

다른 사람의 풀이를 참고하여 다시 풀어보았다. 

def solution(A, B):
    answer = -1
    
    ## 처음부터 A와 B가 같으면 for문을 돌지 않음
    if A==B:
        return 0
        
    for i in range(1, len(A)) :
        ## A를 오른쪽으로 한 칸씩 밀어보며, B와 같은지 비교한다. 
        # A[-1]은 A의 마지막 문자열을 의미하고, A[0:-1]은 0인덱스부터 마지막 문자열 전까지의 문자열을 의미
        A = A[-1] + A[0:-1]

        if A == B:
            return i  
            
    return answer

 

먼저, 처음부터 A와 B가 같으면 for문을 돌지 않고 바로 0을 반환한다. 

A와 B가 같지 않다면, A를 오른쪽으로 한 번씩 밀어보며 B와 같은지 비교한다. 

이 때, A를 한 번 오른쪽으로 밀게되면 A는 A[-1] + A[0:-1]의 값으로 바뀌게 된다. 

이후, A와 B가 같다면 A를 민 횟수를 정답으로 반환한다.  

 

 

예시를 통해 알아보자면, 

A가 "apple", B가 "elppa"일 때, 

A의 길이만큼 오른쪽으로 한 칸씩 밀어보자. 

그렇게되면 A 값 (A[-1] + A[0:-1]) 은

eappl

-> leapp

-> pleap

-> pplea

 

로 변화한다. 따라서 A는 4번 밀어졌을 때 B와 같으므로 4를 정답으로 반환한다. 

 

다른 사람 풀이

[코드 1] : 문자열 슬라이싱 이용

def solution(A,B):
    for cnt in range(len(A)):
        if A == B:
            return cnt
        A = A[-1] + A[:-1]
    
    return -1

 

-> 위의 코드를 좀 더 직관적으로 보기 쉽게 바꾼 코드이다. 

 

[코드 2] : 리스트 insert, pop 함수 이용

def solution(A,B):
    A, B = list(A), list(B)
    
    for cnt in range(len(A)):
        if A == B:
            return cnt
        
        A.insert(0,A.pop())
    
    return -1

 

-> A.pop()을 실행하면 A의 마지막 인덱스 값이 삭제되고 그 값이 return 된다. 

이 return 값을 A의 0번 인덱스에 추가(insert)하여 첫 번째 풀이와 같은 문자열 밀기를 실행하게 되는 것이다. 

 

[코드 3] : deque 이용

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()
    
    return -1

 

deque는 앞과 뒤에서 데이터를 처리할 수 있는 양방향 자료형이다. 

리스트를 사용하여 문자열을 미는 경우에는 시간 복잡도가 O(N)이지만, 

deque를 사용하면 rotate() 함수를 O(1)의 시간 복잡도를 갖게 된다! 

따라서 위의 방법보다 조금 더 효율적인 코드인 것이다. 

 

* deque의 rotate() 

: 함수의 인자 안에 음수를 넣게 되면 왼쪽 회전, 양수를 넣게 되면 오른쪽으로 회전하게 된다. 

ex. 

from collections import deque
test = [1, 2, 3, 4, 5, 6, 7, 8, 9]
test = deque(test)
test.rotate(2) 

result = list(test)
result
# [8, 9, 1, 2, 3, 4, 5, 6, 7]

 

[코드 4] : find 함수 이용

def solution(A,B):
    BB = B*2
    return BB.find(A)

 

-> find 함수의 특징을 이용한 풀이이다. 

A가 hello 이고, B가 lohel 이라고 한다면, BB는 lohellohel이 된다. 

이 후, BB.find(A)를 실행하게 되면, hello가 시작되는 인덱스인 2가 반환된다. 

특이한 점은 만약 A를 찾을 수 없다면 find 함수의 특성에 의해 -1이 반환되게 된다!