110 옮기기(프로그래머스) 문제풀이

문제 

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

프로그래머스

 

문제 접근 방식

문자열에서 "110" 을 찾아서 기존 문자열보다 빠른 문자열 되도록 옮겨줘야하는 문제이다. 문자열을 통한 구현 문제이며, 어디에 110을 옮길 수 있는지를 파악해야 한다. "110" 보다 사전 순으로 뒤에 오는 "111" 이 존재한다면 "111"의 바로 앞쪽으로 위치시키고, 만약 "111"이 존재하지 않는다면 가장 우측에 존재하는 0 뒤에 "110"을 붙여준다. 

 

정리를 해보자면 110을 위치시키는 방법은 아래와 같다.

1. "111" 존재한다면 
>>"111"의 앞쪽에 위치시킨다(만약 111이 여러개일 경우, 가장 왼쪽에 존재하는 111 앞쪽에 위치)

2. "111" 존재하지 않는다면
>> 가장 우측의 0 뒤에 110을 위치시킨다

 

 

처음 문제를 풀 때, 문자열에서 "110을 하나씩 찾고 문자열을 변환시키는 방식으로 진행했으나 로직도 복잡해지고 제대로 동작도 안돼서 다른 풀이 방법을 보았다. 다른 풀이를 보니 다들 스택을 사용했는데, 스택을 생각도 안해봐가지고 왜 갑자기 스택이 나왔는지 조금 의아했다. 코드도 눈으로만 봐서는 이해가 안가서 작성해보면서 이해를 했다. 

 

아래와 같은 상황인 경우, 110을 옮긴 후 양 옆의 "11" 과 "0" 이 다시 합쳐지면서 기존에 존재하지 않는 "110"이 생겨나게 된다. 스택을 사용하지 않는다면 이렇게 새로 생기는 "110"을 다시 찾아줘야한다.

 

 

반면, 스택을 사용하게 되면 "110"이 만들어지면 pop 시키고,  이후 스택 상단인 "11" 인 상태에서 "0"이 들어오면 스택의 상단만 확인하여 "110"이 생겼는지를 확인할 수 있다. 이렇게 변환하다가 생기는 "110"의 개수도 바로 추적할 수 있기 때문에 스택 자료구조를 사용한다.

 

 

시간 복잡도

스택을 사용하여 문자열을 1번만 수행하기 때문에 O(n)의 시간이 걸리며, n의 최댓값이 1e6이므로 시간 내에 동작한다.

 

 

코드

def solution(s):
    answer = []
    
    for string in s:
    	# count: 110의 개수
        # stack: 110을 제외한 문자열 저장
        count,stack=0,""
        
        # 문자열을 순회하며 "110" 이 나온면 문자열에서 제거를 하고 개수만 센다
        for i in range(len(string)):
            if string[i]=="0" and stack[-2:]=="11": # "110" 이라면 stack에서 "11"을 제거하고 개수 +1
                stack=stack[:-2] 
                count+=1
            else:
                stack+=string[i]
        
        # "110"을 옮기는데 기준이 되는 "111"을 찾는다
        index=stack.find("111")
        
        if index!=-1: #" 111"을 찾았다면 "111" 바로 앞쪽에 모든 "110"을 위치시킨다
            converted=stack[:index]+"110"*count+stack[index:]
        
        else: #"111"이 없다면 가장 우측 "0" 뒤에 모든 "110"을 위치시킨다
            index=stack.rfind("0")
            converted=stack[:index+1]+"110"*count+stack[index+1:]
        
        answer.append(converted)
            
    return answer

 

 

회고

3시간 정도 따로 풀어보았는데 계속 코드가 꼬여서 결국은 다른 분들의 풀이를 봤다. 스택이라는 자료구조에 대해 배우긴 했지만 이렇게도 사용할 수 있구나를 배웠다.

기존 target을 제거 후, 새로운 target이 생성되는 경우 stack을 이용해서 선형시간으로 해결할 수 있다