[고득점Kit][그리디] 큰 수 만들기 ⭐⭐

[그리디] 큰 수 만들기

난이도 ⭐⭐

문제

내 풀이

1차 풀이 ❌ (시간 초과)

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool compare(pair<char, int> & a, pair<char, int> & b)
{
    if (a.first == b.first)
        return a.second < b.second;
    else
        return a.first > b.first;
}

string solution(string number, int k) {
    string answer = "";
    
    vector<pair<char, int>> sorted_number;
    for(int i = 0; i < number.size(); i++)
        sorted_number.push_back(pair<char, int> (number[i], i));
    sort(sorted_number.begin(), sorted_number.end(), compare);
    
    int i = 0;
    int indexOflastNum = -1;
    int n = sorted_number.size();
    int remainSize = n - k;
    
    while(answer.length() < n - k)
    {
        if (sorted_number[i].second + remainSize <= n && sorted_number[i].second > indexOflastNum)
        {
            answer.append(1, sorted_number[i].first);  // char 타입인 sorted_number[i].first 를 1 번 반복하여 answer 문자열의 뒤에 붙임
            indexOflastNum = sorted_number[i].second;
            remainSize--;
            i = 0;
        }
        else
            i++;
    }
    
    return answer;
}

이 풀이는 테스트 케이스 9, 10번에서 시간 초과⏰가 발생하는 풀이입니다!

정답을 도출하지만 시간이 너무 많이 걸리는 풀이라 사실상 틀린 풀이다.

• 큰 수로 만들되 원래의 순서는 지켜야 한다.
  • 7보다 8이 앞에 위치해 있다면 큰 수로 만들 때 8이 7보다 앞설 수는 없다.
• 이 풀이의 아이디어
  • sorted_number라는 벡터를 선언했다.
    • 이 벡터에 number 문자열 각각의 원소인 문자(char)와 함께 정렬 전 인덱스(int)를 함께 pair로 저장한다.
  • number 문자열을 내림차순 정렬하되 같은 값이라면 인덱스 오름 차순 정렬을 기준으로 sorted_number를 정렬시킨다. 같은 값이라면 원래대로 인덱스 빠른게 더 앞에 오도록!
    • 정렬이 되었더라도 원소(pair)의 second에 정렬 전 number상에서의 인덱스(위치)를 기억하고 있는 상태.
  • k개를 number로부터 떼내므로 최종적인 answer의 길이는 number.size() - k가 되야 한다.
    • 편의상 n을 number.size()라고 정의했다.
  • 반복문은 answer가 완성될 때까지 돈다. 즉 answer의 길이가 n - k가 될 때까지!
    • sorted_number는 내림 차순 정렬이 되어 있으므로 큰 수들이 먼저 검사를 받게 된다.
    • 정렬된 sorted_number 원소들을 차례 차례 순회하며 1️⃣정렬 전 원래의 인덱스(second)에서 앞으로 `answer`를 다 채우기 까지 얼만큼 더 채워야 하는지를 더한 값이 `n`을 넘어버리면 안되고, 2️⃣정렬 전 원래의 인덱스(second)가 `answer`에 가장 최근에 추가된 문자의 정렬 전 원래의 인덱스보다 같거나 작으면 안된다.(같다는건 완전히 동일한 값이라서 안되는 것이고 작다는건 현재의 `answer`의 가장 마지막에 있는 원소보다 `number`상에서 더 앞에 위치해 있는 원소라는 뜻이므로 삽입이 불가능하다. 위 두 가지 조건이 answer에 삽입될 조건이다!
      • answer가 비어있는 경우
      • i은 sorted_number를 순회할 포인터.
      • indexOflastNum은 answer에 가장 최근에 추가된 문자의 정렬 전 원래의 인덱스(second). 처음엔 answer이 빈 문자열로 시작되므로 초기값은 -1로 해준다.
      • remainSize는 answer를 다 채우기 까지 현재 시점에서 얼만큼 더 채워야 하는지를 나타낸다. answer의 최종 길이가 될 n - k값에서 시작하되 answer에 적합한 원소를 삽입할 때마다 1 씩 감소한다.
      • sorted_number[i]가 1️⃣2️⃣ 후보를 만족하는 원소라면
        • answer의 뒤에 원소를(first) 붙이고
        • indexOflastNum을 업데이트 하고
        • remainSize를 1 줄이고
        • 다시 sorted_number의 처음부터 검사하기 위해 i = 0한다.
      • sorted_number[i]가 1️⃣2️⃣ 후보를 만족하는 원소가 아니라면
        • 다음 원소를 검사하기 위해 i++

2차 풀이 ⭕

#include <string>
#include <vector>
#include <iostream>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    int n = number.size();
    
    int start = 0;
    int end = k;
    
    int max = 0;
    int lastMaxIndex = 0;
    
    for(int i = 0; i < n - k; i++)
    {
        for(int j = start; j <= end; j++)
        {
            if(max < number[j])
            {
                max = number[j];
                lastMaxIndex = j;
            }
        }
        answer.append(1, max);
        start = lastMaxIndex + 1;
        end++;
        max = 0;
    }
    
    return answer;
}

이 풀이는 시간 초과 되지 않고 모든 테스트 케이스를 통과합니다.

1차 풀이의 시간 초과를 해결하지 못해 1차 풀이는 폐기하고 결국 구글링하여 다른 분들의 풀이를 참고하여 풀이했다.. 이 풀이가 더 그리디 알고리즘에 적합한 풀이다.

그리디 알고리즘 👉 순간 순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식

• answer원소를 결정할 때마다 그때 그때 answer[i]가 될 수 있는 범위 내에서 최대값(최적해)를 찾는다.

• 첫 번째 for문
  • answer[i] 문자를 결정한다. answer는 최종적으로 n - k길이가 되야하므로 n - k번 돈다.
    • answer는 빈 문자열로 시작하므로 answer[i] = 땡땡으로 접근하면 런타임 에러가 발생한다는 것에 주의하기! append를 사용하여 answer뒤에 하나씩 붙여주었다. +=를 사용해도 좋다.
• 두 번째 for문
  • answer[i] 문자는 start ~ end 인덱스를 가진 number 원소들 범위 내에서 최대값이 되야 한다.
  • 이 최대값을 찾기 위한 역할을 함
  • 최대값(max)과 그의 인덱스(lastMaxIndex)도 저장한다.
    • 다음 범위의 최대값을 찾기 위해선 max = 0초기화를 해주어야 한다.
    • if(max < number[j])에서 < 가 아닌 <=를 사용하면 값이 같을 때 뒤에 있는 원소가 앞으로 올 수 있어서 안된다.
  • start 👉 범위 내의 최대값을 찾을 범위 시작 인덱스. 해당 범위내의 최대값을 다 찾고나면 다음 범위의 시작 인덱스는 최대값이 위치했던 인덱스의 다음 인덱스다.
  • end 👉 범위 내의 최대값을 찾을 범위 끝 인덱스. 초기값은 k에서 시작한다. 처음부터 인덱스가 k를 넘는 곳에 위치한 문자를 answer[0]에 넣어버리면 n - k개까지 다 채울 수가 없다. 인덱스가 k를 넘는 곳에 위치한 문자의 뒤에 위치한 문자들만 앞으로 넣을 수가 있기 때문이다. 그리고 answer를 하나씩 채워갈 수록 아직 남은 빈 자리들도 1씩 줄어들기 때문에 end는 1씩 증가하게 된다.

1차 풀이와 2차 풀이의 시간 복잡도 비교

• 1차 풀이의 실행시간
  • 
  • 확인해본 결과 “4177252841” (answer의 길이는 n-k이므로 10-4 = 6이 됨)을 number으로 넣었을시 while 반복문을 총 26번 돌았다.
    • 매번 연산 횟수 👉 최선일 땐 1번 (적합한게 맨 앞에 위치할 때), 최악일 땐 10번 (적합한게 맨 뒤에 위치할 때)
      • 매번 i = 0 ~ n - 1 번 내에서 돌기 때문에 마치 순차탐색처럼 적합한게 앞에 위치하다면 일찍 찾고 빠져나오지만 계속해서 맨 뒤에 위치한다면 매 반복마다 O(n)이 되는것이나 마찬가지다.
        • 최악의 경우 (n-k) * n 시간 복잡도가 소요 됨
    • answer[0]을 결정하는데 반복문 돌았던 횟수 👉 2
    • answer[1]을 결정하는데 반복문 돌았던 횟수 👉 3
    • answer[2]을 결정하는데 반복문 돌았던 횟수 👉 4
    • answer[3]을 결정하는데 반복문 돌았던 횟수 👉 1
    • answer[4]을 결정하는데 반복문 돌았던 횟수 👉 6
    • answer[5]을 결정하는데 반복문 돌았던 횟수 👉 10
      • 이와 같이 n만큼 다 돌아야하는 경우가 매번 생긴다면 끔찍쓰
• 2차 풀이의 실행시간
  • 
  • 확인해본 결과 “4177252841”을 number으로 넣었을시 이중 for문까지 합하여 총 15번 돌았다.
    • start ~ end까지의 범위만 돈다. 매번 연산 횟수 👉 end - start + 1
      • end는 1 씩 증가하고 start또한 answer원소를 결정한 그 다음 위치를 가리키기 때문에 후반부로 갈수록 범위가 줄어드는 경향이 있다.
      • 시간 복잡도가 (n - k) * 땡땡 이 되지만 이 땡땡은 절대 `n`을 넘지 않는다. `n`보다 작으며 심지어 줄어드는 경향을 보임
        • 따라서 1차 풀이보다 시간복잡도가 좋을 수 밖에 없다.
    • answer[0]을 결정하는데 반복문 돌았던 횟수 👉 5
    • answer[1]을 결정하는데 반복문 돌았던 횟수 👉 3
    • answer[2]을 결정하는데 반복문 돌았던 횟수 👉 3
    • answer[3]을 결정하는데 반복문 돌았던 횟수 👉 2
    • answer[4]을 결정하는데 반복문 돌았던 횟수 👉 1
    • answer[5]을 결정하는데 반복문 돌았던 횟수 👉 1

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기