프로그래머스 문제 풀이 큰 수 만들기
이 문제는 이시윤 강사님의 프로그래머스 강좌 "파이썬을 무기로, 코딩테스트 광탈을 면하자!"를 보고 정리한 내용입니다.
문제 URL 큰 수 만들기
Contents
- 문제 지문 파악하기
- 강사님의 알고리즘 풀이
- 구르미의 알고리즘 풀이
문제 지문 파악하기
문제에 따르면, 입력 numbers에 대해서 해당 문자열이 가장 큰 수를 만들게끔 k개를 빼야 합니다. 예제 입력을 살펴보죠.
numbers = "4177252841" k = 4
어떻게 가장 큰 수를 만들 수 있을까요? 먼저, 일단 숫자가 나오면 저장합니다. 그리고 그 보다 큰 숫자가 나오면 저장했던 수를 빼보면 어떨까요? 자 시작해봅시다. 처음 숫자인 4를 넣습니다.
collected = ["4"] ( k = 4 )
그 후 1을 넣습니다. 1은 4보다 작기 때문에 뺄 필요가 없지요.
collected = ["4", "1"] ( k = 4 )
이제 7을 넣습니다. 그런데, 7은 마지막으로 저장된 1 보다 큽니다. 1을 빼줍니다.
collected = ["4"] ( k = 3 )
다시 collected에 저장된 마지막 수 4와 7을 비교합니다. 역시 7이 더 크니 4를 빼줍니다.
collected = [] ( k=2 )
이제 비교할 수 가 없으니 7을 넣습니다.
collected = ["7"] ( k=2 )
이제 다시, 7, 2 를 순서대로 넣습니다.
collected = ["7", "7", "2"] ( k = 2 )
이제 5를 넣습니다. 이때, 이전에 마지막으로 저장되었던 2는 5보다 작습니다. 따라서 빼줍니다.
collected = ["7", "7"] ( k = 1 )
이제 마지막으로 저장된 7보다 작기 때문에 빼지 않고 5를 넣습니다.
collected = ["7", "7", "5"] ( k = 1 )
이제 2를 넣습니다. 마지막으로 저장된 5보다 작기 때문에 빼기는 일어나지 않습니다.
collected = ["7", "7", "5", "2"] ( k = 1 )
이제 8을 넣습니다. 이 때 이전에 마지막으로 저장된 2보다 큽니다. 따라서 2를 빼줍니다.
collected = ["7", "7", "5"] ( k = 0 )
물론 8 이전에 저장된 5 역시 8보다 작지만, 이제 더 이상 뺄 k가 없기 때문에, 8을 넣어줍니다.
collected = ["7", "7", "5", "8"] ( k = 0 )
이제 k=0 이기 때문에 뒤에 숫자들을 모두 넣어주면 됩니다.
collected = ["7", "7", "5", "8", "4", "1"] ( k = 0 )
이 문자열들을 하나로 합쳐줍니다. 그럼 원하는 결과가 나옵니다.
result = "775841"
예를 한 번 더 살펴봅시다. 다음 입력이 있다고 가정해봅시다.
numbers = "54321" k = 2
5를 넣죠
collected = ["5"] ( k = 2 )
4를 넣습니다. 마지막으로 저장된 5보다 작기 때문에 빼기는 일어나지 않습니다.
collected = ["5", "4"] ( k = 2 )
numbers를 모두 순회해도 앞 수보다 작기 때문에 결국 이렇게 됩니다.
collected = ["5", "4", "3", "2", "1"] ( k = 2 )
k 가 남았을 때는 collected에서 뒤부터 k개만큼 잘라주면 됩니다.
collected = ["5", "4", "3"] ( k = 0 )
즉 답은 이렇게 됩니다.
result = "543"
이런식으로 풀어도 되는 이유는 "앞자리 숫자가 가장 큰 수가 큰 수"이기 때문입니다. 뭔 뜬금없이 당연한 소리야?라고 하실지 모르겠습니다. 문자열 어느 부분을 쪼갠다 하더라도, 앞자리가 높은 수가 되게끔 뽑으면, 무조건 높은 숫자가 된다는 것이죠. 즉, "앞자리를 최고 큰 수로 만들기 전략"이 부분해를 만족함과 동시에 전체의 해가 될 수 있는 것이지요.
강사님의 알고리즘 풀이
강사님의 알고리즘을 순서대로 표현하면 다음과 같습니다.
- 큰 수를 만드는 문자들을 모으는 배열 collected를 생성합니다.
- number를 다음과 같이 순회합니다.
- 아래 조건을 만족시키면 다음을 순회합니다.
- 조건
- collected에 원소가 있어야 한다.
- 마지막 원소가 순회 수 num보다 작아야 한다.
- k가 0보다 커야 한다.
- collected의 가장 맨 뒤의 원소를 제거합니다.
- k를 1 줄입니다.
- 조건
- k가 0이라면 numbers 인덱스 i부터 끝까지 collected에 이어 붙이고 반복문을 탈출합니다.
- 순회 수 num을 collected 맨 뒤에 넣습니다.
- 아래 조건을 만족시키면 다음을 순회합니다.
- 만약 k가 0보다 크다면 collected를 뒤에서 k개 자릅니다.
- collected를 이어 붙여 하나의 문자열로 만듭니다.
코드로 표현하면 다음과 같습니다.
def solution(number, k):
collected = []
for (i, num) in enumerate(number):
while collected and collected[-1] < num and k > 0:
collected.pop()
k -= 1
if k == 0:
collected += number[i:]
break
collected.append(num)
collected = collected[:-k] if k > 0 else collected
answer = "".join(collected)
return answer
이 알고리즘의 시간 복잡도는 O(N)입니다.
구르미의 알고리즘 풀이
저도 강사님과 비슷한 방식으로 풀었습니다. 대신 저는 스택을 이용하여 풀었습니다. 제가 세운 알고리즘은 다음과 같습니다.
- 스택을 생성합니다.
- number를 다음과 같이 순회합니다.
- 스택의 원소가 있고 k가 0보다 크다면 다음을 반복합니다.
- 스택에 순회 수 elem을 집어넣습니다.
- k가 0이 될때까지 다음을 반복합니다.
- 스택에서 가장 위의 데이터를 뺍니다.
- k를 1 줄입니다.
- 그렇게 해서 만들어진 스택을 하나의 문자열로 만들어줍니다.
이렇게 보니까 별반 다를게 없는 방식이네요. 파이썬 코드는 다음과 같습니다.
def solution(number, k):
# 1. 스택 생성
st = []
# 2. 큰 수가 앞자리가 되게끔 스택에 저장합니다.
for elem in number:
while st and st[-1] < elem and k > 0:
st.pop()
k -= 1
st.append(elem)
# 3. k가 남았다면 뒤에서부터 뺍니다.
while k > 0:
st.pop()
k-=1
answer = "".join(st)
return answer
if __name__ == '__main__':
number = "1924"
k = 2
print(solution(number, k))
CPP 코드는 다음과 같습니다. 여기서는 추후에 스택을 0부터 순회해야하기 때문에, 벡터를 스택처럼 사용하였습니다.
#include <string>
#include <vector>
#include <iostream>
using namespace std;
string solution(string number, int k) {
// 1. 스택 생성
vector<char> st;
// 2. 앞자리가 가장 큰 수가 되게끔 스택에 데이터 저장
for (const auto & elem : number) {
while (!st.empty() && st.back() < elem && k > 0) {
st.pop_back();
k -= 1;
}
st.push_back(elem);
}
// 3. k가 남았다면, 스택 뒤에서 k개 빼줌
while (k > 0) {
st.pop_back();
k -= 1;
}
string answer = "";
for (const auto & elem : st) {
answer += elem;
}
return answer;
}
int main() {
string number = "1924";
int k = 2;
cout << solution(number, k) << endl;
return 0;
}