[Python] 프로그래머스 - 큰 수 만들기

1. 문제정보

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

프로그래머스

 

2. 해결전략

리스트를 순회하면서 뒤의 수가 앞의 수보다 크다면 앞의 수를 삭제하는 방식으로 진행했다. 다만 삭제 이후 아래와 같이 다시 첫번 째 인덱스로 돌아와서 다시 탐색을 진행해야 한다(백트래킹). 

numbers=314321, k=2
# 314321 -> 34321
# 34321 -> 4321

 

처음 시도는 스택을 이용해서 하려고했는데 백트래킹을 구현하는데 부담을 느껴서 인덱스로 문제풀이를 시도했다. 구현은 잘 한 것 같은데 시간 초과로 인해 다시 스택을 이용해서 풀이를 시도했다.

 

하지만 두 번째도 시간초과가 발생해서 결국 다른 분들의 코드를 참고했다. 다른 분들도 스택을 이용했지만 전체 리스트를 스택으로 만들고 시작하는 것이 아닌 결과값을 스택구조로 만들었다. 하긴 나처럼했으면 리스트나 스택이나 다를게뭐람...

 

3. 소스코드

- 시간초과(리스트이용)

# 시간초과
def solution(number, k):
    number = list(number)

    while k > 0:
        # 뒤의 숫자가 앞의 숫자보다 큰 경우 앞의 숫자를 제거
        startCnt = len(number)
        # 지우지 않고 넘어간 수
        skip_cnt = 0
        execute_remove = False
        for i in range(startCnt-1):
            if number[i] < number[i+1]:
                number.remove(number[i])
                k -= 1
                execute_remove = True
                break
            else:
                # 지우지 않은 숫자가 lenth-k개 일 때
                skip_cnt += 1
                if skip_cnt == k:
                    break

        # 모두 같은수만 남아서 지울수가 없는 경우
        if not execute_remove:
           break

    # 모두 같은 수만 남아서 지울 수 없는 경우에는 남은 k만큼 잘라냄
    if k > 0:
        number = number[:-k] 
    return ''.join(number)

 

- 시간초과(리스트를 스택으로 변환)

# 시간초과2
def solution(number, k):
    number = list(number)
    number.reverse()

    temp = []
    while k > 0:
        num_length = len(number)
        if num_length > 1:
            v1, v2 = number.pop(), number.pop()
            # 뒤의수가 앞의수보다 큰 경우 앞의수를 버림
            if v1 < v2:
                number.append(v2)
                temp.reverse()
                number += temp
                temp = []
                k -= 1
            # 앞의수가 뒤의수보다 큰 경우 앞의수를 임시저장
            else:
                temp.append(v1)
                number.append(v2)
            #print(number, temp)
        else:
            temp.reverse()
            number += temp
            break

    number.reverse()
    if k != 0:
        number = number[:-k]
    return ''.join(number)

 

3. 성공(스택사용)

def solution(number, k):
    result = []
    result.append(number[0])

    for i in range(1, len(number)):
        n = number[i]
        
        # 스택을 검사하면서 지워버림
        while k > 0 and result and result[-1] < n:
            result.pop()
            k -= 1
        result.append(n)

    if k > 0:
        result = result[:-k]
    return ''.join(result)

 

4. 배운점

주어진 데이터를 스택으로 보는 것이 아니라 결과를 담는 데이터를 스택으로 만들어보는 것이 해결의 전략이 될 수 있다.