[프로그래머스] 큰 수 만들기 / Swift
[문제 보기]
어떤 숫자에서 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" |
https://programmers.co.kr/learn/courses/30/lessons/42883
코딩테스트 연습 - 큰 수 만들기
programmers.co.kr
풀이 과정
프로그래머스에서의 문제조건에는 number와 k는 모두 1이상이라고 적혀있는데, 같은 경우는 어떤건지 싶어 실제 문제 출처에서 확인해보니 바로 이해가 갔다.
문제를 여러번 다른 방법으로 시도했다.
처음에 풀었을 때는 조건에 맞는 가능한 모든 조합을 전부 구해서 그중 가장 큰 값을 반환하는 방법으로 구현했다.
1. DFS 재귀로 조합을 구함 -> 시간 초과 + 실패(signal: illegal instruction (core dumped))
(signal: illegal instruction (core dumped))라는 오류를 처음 겪었는데, 찾아보니 인덱스 범위 오류 또는 옵셔널 오류 등이라고 해서 다시 코드를 살펴 봤는데 긴 String이 주어졌을 때 Int로 바꾸는 과정에서 오류인가 싶어 그 부분을 고쳐보니 테스트 2번은 해결되었다. 그 전에 재귀 깊이 제한 때문인건가 싶어서 DFS 스택으로 바꿔서 풀어보기도 했다. (2번째 시도)
[1번 시도 코드 보기]
// 1. DFS 재귀 조합 버전
import Foundation
var combinationResult = [Int]()
var numbers = [Int]()
var needToRemove = [[Int]]()
func combinationDFS(phase: Int, startIndex: Int, k: Int) {
if phase == k {
needToRemove.append(combinationResult)
return
} else {
for i in (startIndex..<numbers.count) {
combinationResult[phase] = i
combinationDFS(phase: phase + 1, startIndex: i + 1, k: k)
}
}
}
func combination(_ number: String, _ k: Int) {
numbers = number.map { Int(String($0))! }
combinationResult = [Int](repeating: 0, count: k)
combinationDFS(phase: 0, startIndex: 0, k: k)
}
func solution(_ number:String, _ k:Int) -> String {
combination(number, k)
// needToRemove에 있는 원소들 값에 해당하는 위치를 지워준다.
var result = [Int]()
needToRemove.forEach { (indices) in
let remainder = numbers.enumerated()
.filter { !indices.contains($0.offset) }
.reduce(0) { $0 * 10 + $1.element }
result.append(remainder)
}
return "\(result.max()!)"
}2. DFS 스택으로 조합을 구함 -> 시간초과
(signal: illegal instruction (core dumped))오류 때 재귀 깊이 때문인건가 싶어 스택을 이용한 방법으로 바꾸었다.
실제 오류 원인은 String->Int 변환 부분이었다.
// 2. DFS 스택 조합 버전
import Foundation
var needToRemove = [[Int]]()
func combinationWithStack(length: Int, k: Int) {
var stack = [Int]()
var temp = 0
stack.append(0)
while !stack.isEmpty {
if stack.count == k {
needToRemove.append(stack)
temp = stack.removeLast()
continue
}
if temp + 1 == length {
temp = stack.removeLast()
if temp + 1 == length {
continue
}
}
temp += 1
stack.append(temp)
}
}
func solution(_ number:String, _ k:Int) -> String {
let numbers = number.map { Int(String($0))! }
combinationWithStack(length: numbers.count, k: k)
// needToRemove에 있는 원소들 값에 해당하는 위치를 지워준다.
var result = [Int]()
needToRemove.forEach { (indices) in
let remainder = numbers.enumerated()
.filter { !indices.contains($0.offset) }
.reduce(0) { $0 * 10 + $1.element }
result.append(remainder)
}
return "\(result.sorted(by: >)[0])"
}
3. 2번 코드를 C++로 바꿈 -> 시간초과
C++은 좀 다른가 싶어 바꿔봤는데 역시나 시간초과가 나옴. 이때부터 새로 다시풀어야겠다고 생각함.
// 3. 2번에서 구현(DFS 스택 조합)한 것을 C++로 컨버팅한 버전
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> numbers;
vector<int> needToRemove;
string maxValue = "";
void combinationWithStack(int length, int k) {
vector<int> stack;
int temp = 0;
string remainder = "";
stack.push_back(temp);
remainder.push_back('0' + numbers[temp]);
while (stack.size() != 0) {
if (stack.size() == k) {
if (maxValue < remainder) {
maxValue = remainder;
}
remainder.pop_back();
temp = stack.back();
stack.pop_back();
continue;
}
if (temp + 1 == length) {
temp = stack.back();
stack.pop_back();
remainder.pop_back();
if (temp + 1 == length) {
continue;
}
}
temp += 1;
stack.push_back(temp);
remainder.push_back('0' + numbers[temp]);
}
}
string solution(string number, int k) {
for (int i = 0; i < number.size(); i++) {
int tmp = number.at(i) - '0';
numbers.push_back(tmp);
}
combinationWithStack(number.size(), number.size() - k);
string answer = maxValue;
return answer;
}
4. 최종코드 (그리디)
그리디의 기본 개념인 각 단계에서 최선의 선택을 하는 방법으로 해결했다.
여기서 각단계는 무엇을 이야기하는 걸까?
나는 아래와 같이 풀었다.
예를들어 입력값이 각각 [1,2,3,1,2,3,4], 제거할 횟수k = 3으로 주어졌을 때,
k는 전체 빼야 할 횟수(단계)라고 보고 1개씩 뺄때마다 가장 큰 값이 되도록 구했다.
어차피 빼야할 횟수(모든 뺀 다음의 수의 자릿수)는 정해져있으므로 가장 앞자리가 제일 크게 유지하도록 (각 단계에서 가장 최선의 선택을 유지) 했다.
스택을 이용해서 앞자리가 가장 큰 상태를 유지하도록 했다.
(코드에서 phase 1 부분)
[1,2,3,1,2,3,4] 에서 스택에 맨 위의 원소와 현재 비교하는 원소를 비교한다. 빈 스택일 경우에는 단순히 append해주기만 하고, 만약에 스택의 맨 위 원소가 비교원소보다 작다면, 그리고 아직 제거횟수(count == k)가 남아있다면 (앞자리가 클수록 큰 수가 되므로 ) pop해준다. 이 비교하는 과정을 스택의 맨 밑바닥까지 반복하거나 아니면 비교원소보다 큰 수가 나올때까지 반복한다. 이 과정의 결과로 스택에는 가장 큰 앞자리수가 차곡차곡 쌓이게 된다.
가장 바깥 반복문은 입력받은 [1,2,3,1,2,3,4]를 계속순회를 하는데, 반복문이 끝날 때까지 count가 0이 아니게 될 경우가 발생할 때가 있다. ( [1,0,1,0,1,0], k = 4 ) 이 경우는 실제로 문제에서 요구하는 k개의 숫자를 제거하지 못한 경우다. ( 스택에는 1110이 남아있어 4자리수지만 실제로 문제조건에 맞추려면 2자리수를 반환해야함 )
스택에는 아래서부터 위쪽 방향으로 내림차순으로 정리가 되어있는 상태이므로 아래보다는 위쪽에 상대적으로 작으므로 스택의 위쪽에서 부터 남은 갯수만큼 지워나간다. (코드에서 phase 2, 3 부분)
미처 지우지 못한 남은 갯수만큼 지운 결과로 문제 조건에 맞는 자릿수의 수가 확실하게 나오게 된다.
// 4. 최종 버전
import Foundation
func solution(_ number:String, _ k:Int) -> String {
let numbers = number.map { Int(String($0))! }
var count = k
var stack = [Int]()
var lastIndex = numbers.count - 1
// phase 1
for (i, element) in numbers.enumerated() {
while true {
if let last = stack.last, last < element, count > 0 {
stack.removeLast()
count -= 1
} else {
stack.append(element)
break
}
}
if count == 0 {
lastIndex = i
break
}
}
// phase 2
let start = number.index(number.startIndex, offsetBy: lastIndex + 1)
let range = start..<number.endIndex
// phase 3
for _ in (0..<count) {
stack.removeLast()
}
return stack.reduce("") { $0 + String($1) } + number[range]
}
생각 정리
계속 시간초과가 떠서 최댓값을 구하는 과정같은 부분에서 자잘한 부분에서 최적화를 시도해보았는데 그다지 소용이 없었다.
결국에는 방법 자체를 바꾸어서 해결했다.
알고리즘 자체를 다른 방법으로 접근하려고 했으면 좀 더 빨리 풀었을 것 같다.