[프로그래머스 탐욕법]큰 수 만들기 - Python3

문제

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

코딩테스트 연습 - 큰 수 만들기 | 프로그래머스

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

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

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

제한 조건

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

 

입출력

number	k	return
1924	2	94
1231234	3	3234
4177252841	4	775841

 

알고리즘

def solution(number, k):
    answer = ""
    temp = []
    # numbers에 있는 문자들을 정수로 바꿔서, temp 배열에 넣어준다.
    for i in range(len(number)):
        temp.append(str(number[i]))

    # list형인 stack에 하나씩 넣어보면서, 각 경우에 맞는 조치를 취할 것이다.
    stack = []
    for i in range(len(temp)):
        stack.append(temp[i])
        print("\ntemp[i]: ", temp[i])

        # stack에 원소가 1개밖에 없는 경우, 다른 원소가 비교할 수 없으므로 continue한다.
        if len(stack) < 2:
            continue

        # 그렇지 않다면,
        else:
            # 아직 제거해야 하는 숫자 k만큼 제거하지 않았고, stack의 마지막 원소가 그 앞 원소보다 값이 크다면
            # stack[-2]를 pop하고 k의 값을 1 감소시킨다.
            # stack의 길이가 1이 되었다면, stack[-2]를 pop할 수 없으므로 break한다.
            while k > 0 and stack[-1] > stack[-2]:
                ks = stack.pop(-2)
                print(ks, "빠짐")
                k -= 1
                if len(stack) == 1:
                    break
        print(stack)
    # 아직 k가 남아있을 경우, stack에서 가작 작은 수를 제거하고, 그 때마다 k의 값을 1 감소시킨다. 
    while k > 0:
        print(stack)
        stack.remove(min(stack))
        k -= 1

    # stack의 원소를 문자로 바꿔서 answer에 붙여넣는다. 
    for i in range(len(stack)):
        answer += str(stack[i])
    return answer

number = "4177252841"
k = 4
# number = "1111"
# k = 2
print(solution(number,k))

 

설명

문제를 대충 읽고 풀면 정말 쉽게 풀 수 있을 것처럼 보이지만, 그만큼 쉽지는 않다. 고려해야 할 것들이 몇가지 있기 때문이다. 풀이의 아이디어는 가능한 큰 수가 정답의 앞자리에 오면 그것이 정답이라는 것이다. 그러기 위해서, 어느 숫자를 stack에 집어넣었는데, 이 값이 자신보다 앞에있는 원소보다 크다면, 그 앞에 있는 원소를 지우고 방금 집어넣은 값을 앞으로 오게끔 하는 것이다. 즉, 1, 7, 9 이 세 값이 들어오고, 2개의 값을 지워야 할 때, 1이 들어온 후, 7이 들어왔으면, 7이 1보다 크므로, 1을 없애고, 7이 앞자리로 오게 한다. 그러고 그 다음 9가 들어올 경우, 7, 9 두 값중 작은 값인 7을 지우고 9를 남기면 정답이 된다. 

문제의 예로 주어진 4177252841을 보자. 각 원소를 하나씩 stack에 집어 넣는것을 그림으로 보일 것이다. 

4

이 경우, 비교할 원소가 없으므로 그냥 넘어간다. 

1

4

1이 들어왔다. stack의 마지막 값이 4보다 작다. 즉, 4를 지우고 1을 앞으로 끌어올 필요가 없으므로 넘어간다.

7

1

4

7이 들어왔다. 7은 이 중 가장 큰 숫자이므로, 7을 최대한 앞자리로 땡겨올 것이다. 그러기 위해서, stack의 뒤쪽 2개의 원소를 비교해보면, 7이 1보다 크므로, 1을 pop하고 7을 땡겨온다

7

4

땡겨 오고 보니, 7이 4보다도 크다. 따라서, k만큼의 숫자를 아직 지우지 않았다면, 4를 지우고 7을 앞으로 땡겨오는 것이 맞다. 

7

그래서 스택에는 7이 남게 된다. 

7

7

그 이후 7이 들어오지만, 지울 필요가 없고, 

2

7

7

그 다음 2가 들어오면, 마찬가지로 2가 7보다 작으므로, 앞에 원소들을 지워서 2를 땡겨올 이유가 없다. 

5

2

7

7

그리고 5가 들어오면, 5가 2보다 크므로, 2를 지워서 5를 앞으로 떙겨올 필요가 있다. 

5

7

7

2를 지우고 5를 앞으로 땡겨왔다.

8

5

7

7

그 다음 8이 들어왔다. 8은 stack에 있는 값들 중 가장 큰 값이라 제일 앞으로 땡겨오고 싶지만, stack의 원소를 하나 pop할때마다 k의 값을 1씩 감소시켰기 때문에 더이상 앞의 원소를 제거할 수가 없다. 따라서, temp에 있는 나머지 원소들을 쭉 복사해온다. 

1

4

8

5

7

7

이렇게, 4177252841에서 4개의 숫자를 지워서 만들 수 있는 가장 큰 수는 775841이 된다.

그런데 이러다가, k만큼 문자를 제거하지 못할 수도 있는데, 이런 경우 알고리즘의 하단에 있는 아래 반복문으로 숫자를 삭제한다. 

    # 아직 k가 남아있을 경우, stack에서 가작 작은 수를 제거하고, 그 때마다 k의 값을 1 감소시킨다.
    while k > 0:
        print(stack)
        stack.remove(min(stack))
        k -= 1

이렇게 하면, numbers = "1111"이고, k = 2 인 경우에도 답을 출력한다. 

 

코드를 말로 설명하자면 다음과 같다.

1. 주어진 문자열을 정수로 바꿔서 temp에 담는다.
2. temp의 원소들을 하나씩 stack에 집어 넣는다.
   1. stack에 들어간 원소의 갯수가 1개라면, 다른 원소와 비교할 수 없으므로 continue한다.
   2. stack에 원소의 갯수가 2개 이상이라면, stack[-1]과 stack[-2]를 비교해서, stack [-1], 즉  맨 뒤에있는 원소가 그 앞에 있는 원소인 stack[-2]보다 작아지는 순간까지 stack[-2]를 pop한다. 
   3. 그리고 pop할 떄마다 k의 값을 1 감소시킨다. 
   4. stack의 길이가 1이 되면, break한다. 
3. 아직 k만큼의 숫자를 제거하지 못한 경우, k가 0보다 큰 동안 
   1. staack에서 최소값을 찾아서 제거한다. 
   2. k의 값을 1 감소시킨다. 
4. stack의 원소들을 answer문자열에 하나씩 붙여서 리턴한다. 

결과

후기

문제를 잘 읽지도 않고 풀려고 하다보니까 뭐 정렬해서 젤 작은거 버리면 되겠네~ 이런 식으로 생각하다가 시간낭비를 엄청 했다. 그리고, 뭔가 원소가 어떤 정답 배열에 들어갈 때마다 원하는 처리를 해줘야 하므로, stack자료구조를 생각했다. 스택에 대한 이해가 없었다면 불가능한 일이지 않았을까 싶다. 다만 시간복잡도가 걱정이다. O(N^2)정도라서, 입력 numbers가 엄청 긴 숫자이고, 비교를 해야하는 경우가 계속 있다면 통과할 수 있을지 모르겠다. 다른 사람의 코드와 실행 시간을 비교해보니, 내 코드가 2배정도 실행시간이 더 걸린다. 어디서 불필요한 연산이 있는 것 같은데, 좀 더 보고 수정을 해야겠다. 

지금 보니, 첫 반복문을 for문으로 시작할 것이 아니라 while문으로 돌려서, 쓸데없는 반복을 하지 않도록 해야겠다. 수정한 코드는 먼 훗날 올리도록 하겠다. 빠셍~