Programmers. 큰 수 만들기

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 큰 수 만들기

문제 풀이

앞 자리서부터 다음 자리 수가 현재 위치보다 크다면 제거하고 다시 원점에서 탐색을 반복하여 주어진 횟수만큼 제거된 숫자가 만들 수 있는 가장 큰 수가 될 것이다.

처음엔 buffer에 저장하여 추출할 글자를 빼고 다시 재할당하거나 리스트로 특정 좌표를 pop하는 형태로 구현했다. 그 결과 timeout이 계속 발생해 데이터의 relocate를 막아야 함을 알아낼 수 있었다. 탐색기준은 항상 2개의 자리수만큼 비교하므로 deque를 두 개 선언해서 popleft를 적절히 사용하면 relocate 없이 해결할 수 있을 듯 하다.

1. 전체 글자를 우측 deque에 삽입

2. 뺀 숫자를 count하며 주어진 k와 같아질 때까지 아래 탐색과정을 반복한다.

3. 만약 좌측 큐가 존재하고(이전 단계들에서 통과한 숫자들) 좌측 큐의 마지막 원소가 우측 큐 첫번째 원소보다 작다면 계속 pop하고 그렇지 않다면 빠져나온다.

4. 좌측 큐의 원소를 빼고나서 k와 같아졌다면 2번 과정을 빠져나온다.

5. 아직 더 빼야 한다면 우측 큐가 존재하는 동안 첫 번째 원소를 popleft하고 우측 큐의 첫 번째 원소와 비교하여 같거나 크면 좌측 큐에 삽입하고 작으면 그대로 삽입하지 않아 추출된 채로 카운트 1을 올리고 3번으로 회귀한다.

6. 2번 단계 반복문이 모두 끝났음에도 더 빼야 한다면 좌측 큐의 모든 원소를 3번 과정에 따라 단조 감소 형태이므로 남은 개수만큼 pop한다.

7. 이후 큐에 남아있는 값들을 리스트에 모아 string화하여 출력한다.

python 코드

from collections import deque

def solution(number, k):
    left_q, right_q = deque(), deque()
    cnt = 0
    for num in number:
        right_q.append(num)
    while cnt < k:
        while left_q:
            if cnt < k and left_q[-1] < right_q[0]:
                left_q.pop()
                cnt += 1
            else:
                break
        if cnt == k:
            break
        while right_q:
            x = right_q.popleft()
            if right_q and right_q[0] <= x:
                left_q.append(x)
            else:
                cnt += 1
                break
        if not right_q:
            break
    while cnt < k:
        left_q.pop()
        cnt += 1
    sol = list(left_q) + list(right_q)
    return "".join(sol)