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

프로그래머스 문제 정복기

 

난이도 : lv2 

 

---

🔗 Link

---

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

코딩테스트 연습 - 큰 수 만들기

 

 

📑 Summary

---

 문자열로 된 숫자와 제거할 수 있는 개수인 k 가 주어질 때, 해당 숫자에서 k개만큼 뺐을 때, 나올 수 있는 가장 큰 숫자가 몇인지 출력하는 문제이다.

 

🔑 How to solve? 

---

이 문제를 처음엔 무식하게 풀고 틀렸던 것 같다. itertools의 combinations를 이용하면 될 줄 알고, 가볍게 코드를 짜고 제출하면, 1/3점이라는 무시무시한 점수가 나온다.😂😂 숫자가 최대 1,000,000자리 이므로, 조합으로 풀면 당연히 안 되는 문제다.(역시나지만, 혹시나 하고 한번 돌려봤다.)

 

🤔 어떻게 하면 큰수를 만들 수 있는가? 

 해당 문제를 해결하기 위해 많은 방법들을 사용해본 것 같다. 이중 반복문으로 조합보단 효율적으로도 생각을 해봤고, DP도 이용해봤다. 결론부터 이야기하자면, dp에 개념이 어느 정도 들어가긴 했다. 자, 본격적으로 큰 수를 어떻게 만드는지부터 생각해보자. 큰 수가 되려면, 어떻게 해야 할까? 우선 가장 왼쪽에 있는 숫자를 크게 만들어야 한다. 이게 이 문제의 핵심이고 끝이다. 가장 왼쪽에 있는 수를 최대로 만드는 방법을 고려하면 된다.

 

 

그래서 말 돌리지 말고, 방법을 내놓으라고!! 🤬😡

그냥 말 그대로다, 왼쪽 숫자가 최대가 되어야 한다. 그럼 왼쪽에서부터 하나씩 꺼내어, 가장 큰 수가 앞으로 올 수 있도록 판단해야 한다. 나보다 왼쪽이 작다면, 뺄 수 있는 한 최대한 빼야 한다는 의미이다.  K가 존재하는 한, 왼쪽에서 부터 숫자를 빼서 가장 큰 값을 만드는 탐욕적인 방법이 필요한 문제이다. 즉, 그리디 알고리즘에 관한 문제라고 할 수 있다.

 

해당 문제에 대해 왜 그리디인지, 혹은 어떻게 그리디가 적용되는지 감이 오지 않는다면, 아래 접은 글을 참고하자.

 

예제인 3번째 입출력을 시도해보자. 숫자는 "4177252841"이고, K = 4 인 입력이라면, 다음과 같이 생각할 수 있다.

 

1. 먼저, 왼쪽 숫자를 가져온다. 아직 비교대상이 없으므로 4를 입력한다.

4    < ---- > 177252841

현재 뺀 숫자 개수 : 0

 

2. 다음 오른쪽 숫자를 가져온다. 왼쪽과 비교한 결과 1이 작으므로, 그냥 넣는다.

4 1 < ---- > 77252841

현재 뺀 숫자 갯수 : 0

 

3. 또 다음 오른쪽 숫자를 가져온다. 왼쪽과 비교한 결과 1보다 7이 크다. K의 여유가 있으므로, 1을 빼고 7을 그 자리에 넣는다.  

4 7 < ---- > 7252841

현재 뺀 숫자 개수 : 1

 

3-1. 그런데 4도 7보다 작다. K의 여유를 확인해보니, 뺄 수 있다. 4도 날리고 7을 그 자리에 넣는다.

7  < ---- > 7252841

현재 뺀 숫자 개수 : 2

 

4. 다음 숫자를 가져온다. 숫자가 작거나 같으니, 뺄 필요가 없다. 그냥 넣는다.

77  < ---- > 252841

현재 뺀 숫자 갯수 : 2

 

5. 다음 숫자를 가져온다. 숫자가 작거나 같으니, 뺄 필요가 없다. 그냥 넣는다.

772  < ---- > 52841

현재 뺀 숫자 갯수 : 2

 

6. 다음 숫자를 가져온다. 다음 숫자가 더 크다. K의 여유가 있으므로 2를 빼고 그 자리에 넣는다.

775  < ---- > 2841

현재 뺀 숫자 개수 : 3

 

7. 다음 숫자를 가져온다. 숫자가 작거나 같으니, 뺄 필요가 없다. 그냥 넣는다.

7752  < ---- > 841

현재 뺀 숫자 갯수 : 3

 

8. 다음 숫자를 가져온다. 다음 숫자가 더 크다. K의 여유가 있으므로 2를 빼고 그 자리에 넣는다.

7758  < ---- > 41

현재 뺀 숫자 개수 : 4

 

9. 더 이상 K를 뺄 수가 없다. 싹 다 몰아넣자

775841

 

푸는 순서를 보면서, 반복되는 부분을 볼 수 있었을 것이다. 왼쪽으로 숫자를 하나씩 가져오는 반복성을 느낄 수 있으며, 오른편보다 작은 왼편 숫자를 제거하면서, 큰 수를 만드는 것을 볼 수 있다. 뒤에 어떤 더 큰 수가 있던지 간에 자신이 뺄 수 있는 숫자를 왼편부터 빼면서, 만들 수 있는 최대의 숫자를 만드는 것이다. 부분최대가 최대의 최대가 되는 그리디 알고리즘을 요구하는 것을 알 수 있다.

 

 

🤔 그리디를 어떻게 적용하는가?

 K라는 뺄 수 있는 값을 이용하여, 큰수를 최대한 왼편으로 세우는 것이다. 즉 문자열로 보았을 때, 내림차순 형식이 될 수 있도록 빼는 것이다.

 

💊 주의할 점 

 만약, 문자열이 내림차순으로 정렬이 되어있을 경우, 위 로직대로 구현하였을 때, 뺄 수 있는 값이 없다. 왼편이 가장 크도록 설계되었으므로, K만큼 빼지 않았다는 의미는 오른편이 왼편보다 작게 정렬되어있다는 의미이다. 즉 큰 수를 만들려면, 해당 그리디 알고리즘이 끝나고, 남은  K만큼은 오른편에서 빼주면 가장 큰 수가 된다.

 

 

📜 정리 

---

1.  해당 문제는 그리디 알고리즘을 통해 가장 큰 수를 구할 수 있다.
2.  그리디를 적용하기 위해서 왼편부터 하나의 문자씩 확인한다.
3.  왼편보다 오른편의 숫자가 더 클 경우, K의 한도 내에서 이전 숫자들을 빼고, 현재 숫자를 더해준다. 
4.  모든 문자를 확인 한 뒤, K가 남았다면 오른편에서부터 남은 K만큼 빼준다. 

 

이를 적용하면 아래와 같은 코드가 된다.

 

 

 

💡 Code

---

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

# 옮긴 숫자들 중 K개의 한하여 왼편에 가장큰 숫자를 배치하는 코드
def getResult(answer, num, k):

	#answer 리스트 내에 값이 존재하며, 왼편이 작고, K의 여유가 있을경우
    while (answer) and (int(answer[len(answer)-1]) < num) and (k > 0):
    	#리스트 맨 뒷값 제거
        answer.pop()
        #K갯수 감소 
        k-=1
    #현재 숫자를 담는다
    answer.append(num)
    return answer,k

def solution(number, k):
    answer = []
	#왼편부터 숫자를 하나씩 꺼낸다
    for num in number:
        answer,k = getResult(answer,int(num),k
        
        
	#만약 K의 여유가 남았다면, 맨뒤에서 부터뺀다(왼편이 크도록 설계되었으므로)
    for _ in range(k):
        answer.pop()
    result=""
    #출력용
    for atom in answer:
        result+=str(atom)
    return result

 

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.