4일차, 큰 수 만들기

문제

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한사항

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

문제를 보고 든 생각

뭔가 풀 수 있을 것 같았다.

방법이 아예 떠오르지 않았던 것도 아니었다.

하지만 시간이 가면 갈수록 이게 맞나 싶은 생각이 강해졌다.

나의 아이디어

크게 두 가지 방법이 떠올랐다.

1. for문을 돌리면서 리스트의 요소 i와 i - 1번째 그리고 i + 1번째를 비교해주면 될 것 같았다. 그리고 비교에 의해 작다고 판단된 수는 빼주면서 조건에 맞는 개수만큼만 리스트에서 빠질 수 있도록 짜면 될 것 같았다.

 

2. 스택이나 큐 같은 자료구조를 사용하면 될 것 같았다. 앞에서부터 하나씩 담아가면서 수를 비교하고 작으면 빼는 이런 식으로 풀 수 있지 않을까하는 생각을 했었다.

 

안타깝게도 나는 1번을 택했고 그 방법으로 문제를 해결하려고 했다.

총 주어진 시간인 3시간 중 약 1시간 30분 ~ 2시간 정도를 이 문제에 쏟은 것 같다.

결과

def solution(number, k):
    number = [x for x in number]
    # 비교를 쉽게 하기 위해 앞뒤로 0붙이기
    numbers = ["0"]
    numbers.extend(number)
    numbers.append("0")

    n = 1
    r = 3

    if len(list(set(number))) == 1:
        for i in range(k):
            number.pop()
        answer = "".join(number)
        return answer
    else:
        # 2번 인덱스부터 비교 시작
        # 제거는 number에서!
        # 그래도 결국 numbers에서 지워지지 않은 숫자 때문에
        # 중복적인 작은 수를 제거할 가능성이 있다.
        for data in numbers[2 : -1]:
            if numbers[n] < data and k != 0:
                numbers.remove(numbers[n])
                k -= 1
                continue
            elif numbers[n] > data and k != 0:
                numbers.remove(data)
                k -= 1
                continue
            if data < numbers[r] and k != 0:
                numbers.remove(data)
                k -= 1
                continue
            elif data > numbers[r] and k != 0:
                numbers.remove(numbers[r])
                k -= 1
                continue
            n += 1
            r += 1

        answer = "".join(numbers).strip("0")
        return answer

마음이 아프지만 나의 방법으로 이 문제를 해결해내지 못했다.

강의에서 배운 것

내가 두 번째로 생각했던 방법이 맞았다는 걸 알 수 있었다.

심지어 수를 리스트에서 빼는 기준까지 강사님의 방법과 일치했는데

도대체 왜 그 방법은 틀렸다고 판단했는지 지금까지도 이해가 되지 않는다.

강의를 통해 알게 된 풀이

def solution(number, k):
    # 문자열 상태에서 수를 비교해도
    # 사전순으로 비교가 되기 때문에
    # int형 상태에서 비교하는 것과 결과가 같아서
    # 형 변환을 해줄 필요가 없다
    q = []
    for i, data in enumerate(number):
        # 지금 들어와있는 것보다 들어오려는 게 크면
        # 들어와있는 걸 제거한다.
        while len(q) > 0 and q[-1] < data and k > 0:
            q.pop()
            k -= 1
        # 빼야하는 수의 개수만큼
        # 다 뺀 상태라면
        # 남은 데이터들을 q에 전부 집어넣고
        # for문을 종료한다.
        if k == 0:
            q += number[i:]
            break
        q.append(data)
    q = q[:-k] if k > 0 else q
    answer = "".join(q)
    
    return answer

위의 코드가 나타내주는 풀이 방식은 이러하다.

 

number를 앞에서부터 하나씩 담는다. 그런데 들어오려는 숫자가 들어와있는 숫자보다 크면 들어와있는 작은 숫자들을 모두 제거해준다.

이 과정을 k가 0이 될 때까지 반복한다.

 

반례가 될 수 있는 케이스들이 있으니 작성 시 조심해야 한다.

a. number의 모든 요소가 똑같은 경우

b. number가 내림차순으로 정렬되어 있는 경우

 

코드의 흐름은 아래와 같다.

1. 큰 수를 담을 리스트인 q를 배열로 초기화한다.

 

2. number의 각 요소들을 앞에서부터 한 개씩 q에 담는다.

 

3. 만약 q의 길이가 0이 아니고, q의 맨 마지막 요소가 현재 들어오려는 수보다 작다면, 그리고 k가 0이 아니라면

-> 현재 들어오려는 수보다 작은 값을 q에서 모조리 제거한다.

-> 제거한 횟수에 맞춰 k값도 차감해준다.

 

4. 제거할 수의 개수 정보인 k가 모두 사용됐다면 그 즉시 남은 number의 요소들을 q에 더해주고 반복문을 종료한다.

4-1. k가 모두 사용되지 않았어도 number의 요소를 모두 탐색했다면 반복문은 종료된다.

 

5. 4-1의 상황에 대응하기 위해 남은 k의 값만큼 q의 뒤에 달린 요소들을 제거해준다. (슬라이싱한다.)

5-1. k를 다 사용한 상황이었다면 그대로 q를 저장한다.

 

6. 리스트 형태인 q를 문자열로 바꿔주고 리턴한다.

느낀 점

해결 방식을 찾았음에도, 그리고 그 방식을 가지고 머릿속에서 시뮬레이션을 돌려봤음에도 이 방식을 내던져버렸다.

생각이 짧은 걸까, 머리가 나쁜 걸까.

4번의 테스트를 거쳤지만, 테스트에서 맞힌 문제가 한 문제도 없다는 게 참.

한편으로는, 한번도 만나보지 못한 문제들을 만나보게 되는 기회라고 생각한다.

 

그래도 풀고 싶다.