[프로그래머스] 큰 수 만들기 / 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

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

---

풀이 과정

프로그래머스에서의 문제조건에는 number와 k는 모두 1이상이라고 적혀있는데, 같은 경우는 어떤건지 싶어 실제 문제 출처에서 확인해보니 바로 이해가 갔다.

https://hsin.hr/coci/archive/2011_2012/contest4_tasks.pdf

 

 

문제를 여러번 다른 방법으로 시도했다.

처음에 풀었을 때는 조건에 맞는 가능한 모든 조합을 전부 구해서 그중 가장 큰 값을 반환하는 방법으로 구현했다.

 

 

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]
}

 

---

생각 정리

계속 시간초과가 떠서 최댓값을 구하는 과정같은 부분에서 자잘한 부분에서 최적화를 시도해보았는데 그다지 소용이 없었다.

결국에는 방법 자체를 바꾸어서 해결했다.

알고리즘 자체를 다른 방법으로 접근하려고 했으면 좀 더 빨리 풀었을 것 같다.