[Python] 프로그래머스 코딩테스트 연습 > 문자열 밀기 (문자열 슬라이싱, deque)

안녕하세요! 오늘은 문자열 밀기 문제를 여러 가지 방법으로 풀어보겠습니다.

어려운 문제는 아니지만 자료구조의 특징, 속도, 아이디어 등을 고민해 볼 수 있는 문제라고 생각해서 가져왔습니다.

 

문자열 밀기 문제 링크

프로그래머스

 

모든 문제의 저작권은 프로그래머스에게 있음을 밝힙니다.

---

목차

 

1. 문제 설명
2. 풀이 과정

---

 1. 문제 설명

 

 

A의 마지막 index 문자를 첫 번째 index 문자로 보내고 나머지 문자들은 뒤로 미는 것을 "문자열 밀기"라고 문제에서 정의합니다. A 문자열을 밀어서 B 문자열이 되려면 몇 번 밀어야 하는지 return 하는 함수를 작성하면 됩니다. 단, 밀어서 B가 되지 못할 경우 -1을 return 해야 합니다.

---

2. 풀이 과정

 

• 문자열 슬라이싱을 이용한 풀이

 

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

 

조건에는 나와있지 않지만 A와 B가 같은 경우 len(A) 번 민 게 아니라 0번 밀었다고 간주합니다.

A와 B가 같다면 cnt가 0일 때 바로 if문을 만족하기 때문에 return값은 0이 됩니다.

그렇지 않다면 cnt가 1씩 증가하면서 A = A [-1] + A [:-1] 코드를 통해 한 번씩 밀게 되고

그 횟수만큼 return값이 됩니다. 문자열은 리스트와 달리 수정 불가능한(Immutable) 자료구조이기 때문에 A를 재선언하는 방법으로 구현했습니다.

for문을 다 돌아도 if문을 만족하는 cnt가 없다면 -1이 반환돼야 하므로 함수의 return값에 -1을 넣어주었습니다.

 

 

• 리스트 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

 

수정 가능한(mutable) 리스트의 특성을 이용한 풀이입니다.

A.pop()을 실행하게 되면 마지막 인덱스가 삭제되고 그 값이 return 됩니다. 이 return값을 A의 0번 index에 insert 하면 첫 번째 풀이와 같이 "문자열 밀기"가 일어납니다.

 

• 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는 앞과 뒤에서 데이터를 처리할 수 있는 양방향 자료형으로, 스택(stack)처럼 써도 되고 큐(queue)처럼 써도 됩니다.

다음은 List와 Deque의 연산자 별 시간 복잡도를 나타낸 표입니다.

 

List 관련 함수의 시간 복잡도

 

 

Deque 관련 함수의 시간 복잡도

 

 

중간에 데이터를 삽입하거나 삭제하는 경우 list와 deque 모두 O(N), append()와 pop()의 경우 list와 deque 모두 O(1)의 시간 복잡도를 가집니다. 하지만 deque는 양방향이기 때문에 popleft()와 appendleft()의 시간 복잡도가 O(1)입니다.

이번 문제에서 list를 사용했을 경우 insert 과정에서 첫 번째 index를 제외하고 모두 뒤로 밀어야하기 때문에 시간 복잡도가 O(N)이지만 deque를 사용했을 경우 rotate()는 rotate(1)과 같기 때문에 O(1)의 시간 복잡도를 가집니다.

데이터의 길이가 길었다면 유의미한 시간 차이가 발생했을 것입니다.

 

• find 함수를 이용한 풀이

 

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

 

find 함수의 특성을 이용한 신박한 풀이입니다.

만약 A가 "hello"이고 B가 "lohel"이라고 한다면 BB는 "lohellohel"이 되고 BB.find(A)를 실행하게 되면 hello가 시작되는 index인 2가 반환됩니다. 만약 "hello"가 존재하지 않는다면 find 함수의 특성에 의해 -1이 반환됩니다. 공교롭게도 문제의 조건과 정확히 일치합니다.

 

이렇게 총 4가지 방법으로 문제를 풀어보았습니다. 여러 파이썬 함수들의 특성을 이해할 수 있었고 시간 복잡도에 대해서도 고민해볼 수 있는 시간이었던 것 같습니다.

도움이 되셨다면 하트와 구독 부탁드립니다. 감사합니다.