[알고리즘문제] 프로그래머스 큰수만들기

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

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

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

priority_queue<string> total;
vector<vector<int>> temp;

string ExtractString(string object, vector<int> position) {
    if (object.size() < position.size()) return "";
    int cnt = 0;
    string tmp;

    for (int n = 0; n < object.size(); n++) {
        if (cnt < position.size()) {
            if (n == position[cnt]) {
                cnt++;
                continue;
            }
        }
        tmp = tmp + object[n];
    }
    return tmp;
}

vector<int> finalPos;
vector<int> position;
void Permutation(string object, vector<int> pos) { 
    temp.push_back(pos);
    pos.back() = pos.back() + 1;
    if (pos.back() > (object.size() - 1)) {
        position = pos;
        position.back() = position.back() - 1;
        return;
    }
    Permutation(object, pos);
}

string solution(string number, int k) {
    int count = 0, it;
    for (int i = 0; i < k; i++) {
        position.push_back(i);
        finalPos.push_back(number.size() - k + i);
    }
    while (position[0] <= (number.size() - position.size())) {
        Permutation(number, position);
        for (int i = position.size() - 1; i >= 0; i--) {
            if (position[i] != finalPos[i]) {
                count = i;
                break;
            }
        }
        it = 0;
        for (int i = count; i < position.size(); i++) {
            if (i == count) {
                position[i] = position[i] + 1;
            }
            else {
                it++;
                position[i] = position[count] + it;
            }
        }
    }
    for (int i = 0; i < temp.size(); i++) {
        total.push(ExtractString(number, temp[i]));
    }
    
    string answer = total.top();
    return answer;
}

프로그래머스 탐욕법의 큰수만들기 문제이다.

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하라고 한다.

solution함수에서 number라는 문자열과 k를 parameter로 받아온다.

예를 들어 "1231234"라는 문자열과 3이라는 숫자를 주면 해당 문자열에서 3개를 제외할 때 나오는 모든 수 중 가장 큰값을 return하면 된다. 문자열이 "1231234"가 주어지고, 제외할 숫자를 3이라고 한다면 

 - 0번째 1번째 2번째 수를 제외하면 나오는 숫자는 1234

 - 0번째 1번째 3번째 수를 제외하면 나오는 숫자는 3234

 .

 .

 .

- n-2번째, n-1번째, n번째 수를 제외하면 나오는 숫자는 1231 이다.

이런식으로 나오는 모든 경우의 수를 확인했다.

 

1. solution함수에서 인자값으로 넘겨 줄 배열 position을 만들고(제외할 인덱스 값을 가지고 있는 배열),

제외할 인덱스 값별로 가장 마지막 값을 미리 구해놓는다.

 

 

2. 그리고 제외할 인덱스 값 중 가장 첫번째에 와야되는 숫자가 마지막 위치값보다 작을때 동안 아래 로직을 반복한다.

 

3. Permutation 함수에서는 잘라내야 되는 위치값을 각각 계산하며 재귀호출한다.

그리고 마지막 원소의 값이 대상 문자열의 길이에 다다르면 Permutation함수를 종료한다.

4. 그리고 position배열을 재배치 한 후 Permutation 함수를 다시 호출한다.

 

전체적으로 보면 아래의 그림과 같은 순서로 데이터를 뽑아내고 I Column의 내용을 2차원 배열 temp에 넣어둔다.

그리고 temp의 내용을 이용하여 문자열을 뽑아낸다.

 

대상문자열과 잘라내야 될 위치값이 들어있는 배열을 parameter로 문자열을 자르는 함수를 호출한 후 결과값을 priority_queue total에 push한다.

 

그럼 total에 아래의 값이 들어있게 된다.

 

그럼 total.top()에 가장 높은 값이 저장이 된다.

 

 

로직이 복잡해졌지만 한번 처음 생각이 든 해결방법으로 끝까지 풀어보기로 생각하고 문제를 풀었다.

3일 매일 10시간씩 투입해서 겨우겨우 풀었다,,, ^^ㅣㅂㅏ

시간 초과에 대한것은 다시 생각한 후 풀어봐야겠다.