[프로그래머스/C++] 큰 수 만들기

picture of programmer's problem

---

#include <string>
#include <algorithm>
using namespace std;

string solution(string number, int k) {
    string arr = "";
    arr.push_back(number[0]);
    int idx = 0;
    for(int i = 1; i < number.length(); i++) {
        if(idx == k) {
            arr.push_back(number[i]);
            continue;
        }
        if(arr.back() < number[i]) {
            arr.pop_back();
            if(!arr.empty() && arr.back() < number[i])i--;
            else arr.push_back(number[i]);
            idx++;
        } 
        else {
            arr.push_back(number[i]);
        }
    }
    for(int i = 0; i < arr.length(); i++)
        if(arr.length() > number.length() - k) arr.pop_back();
    
    return arr;
}

---

이 문제는 가장 큰 수를 만들어 내는 문제인데, 같은 자리수 내에서 가장 큰 수라하면 맨 앞에서부터 숫자가 큰 숫자라고 생각했습니다.

 

그렇다면 맨 앞에서부터 바로 앞에 있는 숫자와 뒤에 있는 숫자의 크기를 비교해서 지금 가진 숫자가 더 작다면 버리고 새로운 숫자를 취하고 지금 숫자가 크다면 보관해놓는 방식(Stack)의 방식을 생각했습니다.

 

구현한 코드를 설명하자면 문자열은 1자리 이상 주어지므로 첫번째 문자열을 미리 받아서 1번~마지막번까지의 숫자를 비교하도록 하였고

내가 가진 스택 상단 숫자가 다음 숫자보다 작다면 버리고 새 것을 취하고, 내가 가진 숫자가 크다면 숫자를 저장하고 새 숫자를 넣는 형식으로 구현하였습니다.

 

만약 버려야하는 갯수를 모두 버린 뒤라면 뒤에 있는 문자열을 모두 받아오도록 하였습니다.

 

TEST CASE (테스트케이스)

1.  [ "213332111" 5 "3332" ] : 배열의 마지막부근에 버릴 숫자가 일괄적으로 있는 경우 + 같은 크기의 숫자를 비교할 경우

2. [ "21323451" 4 "3451" ]   : 앞에서 4자리를 이미 버린 경우 + 3이 2보다 커서 저장했지만 뒤에 4보다 작은경우 (스택 1개 빼기)

3. [ "77777" 1 "7777" ]           : 같은 숫자 중에서 1자리만 버릴 경우

4. [ "12345" 0 "12345" ]       : 아무 숫자도 버리지 않을 경우

5. ["010103" 4 "13"]               : 110이 담긴 상태에서 3을 넣어야하는 경우 (스택에서 2개 빼기)

 

처음 4번까지 테스트를 통과하고 제출하였더니 테스트 11번, 12번이 자꾸 불통과하여 어떤 경우의 수가 있나 생각했습니다.

테스트 11번 같은 경우 테스트케이스 5번에서 생각한 벡터에서 숫자를 여러개 빼야하는 경우가 생겼습니다.

테스트 12번 같은 경우 버릴 숫자만큼 버렸다면 모든 숫자를 넣어라 라는 문구를 한 번만 실행하여 두 개 이상 over해서 담을 경우를 상정하지 못했던 것 같습니다. 

 

picture of success

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

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