λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

πŸ“ μ•Œκ³ λ¦¬μ¦˜/Programmers

[C++/PGS] Lv.2 : 큰 수 λ§Œλ“€κΈ° (GREEDY)

728x90

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

 

문제 μ„€λͺ…

μ–΄λ–€ μˆ«μžμ—μ„œ k개의 수λ₯Ό μ œκ±°ν–ˆμ„ λ•Œ 얻을 수 μžˆλŠ” κ°€μž₯ 큰 숫자λ₯Ό κ΅¬ν•˜λ € ν•©λ‹ˆλ‹€.

예λ₯Ό λ“€μ–΄, 숫자 1924μ—μ„œ 수 두 개λ₯Ό μ œκ±°ν•˜λ©΄ [19, 12, 14, 92, 94, 24] λ₯Ό λ§Œλ“€ 수 μžˆμŠ΅λ‹ˆλ‹€. 이 쀑 κ°€μž₯ 큰 μˆ«μžλŠ” 94 μž…λ‹ˆλ‹€.

λ¬Έμžμ—΄ ν˜•μ‹μœΌλ‘œ 숫자 number와 μ œκ±°ν•  수의 개수 kκ°€ solution ν•¨μˆ˜μ˜ λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§‘λ‹ˆλ‹€. numberμ—μ„œ k 개의 수λ₯Ό μ œκ±°ν–ˆμ„ λ•Œ λ§Œλ“€ 수 μžˆλŠ” 수 쀑 κ°€μž₯ 큰 숫자λ₯Ό λ¬Έμžμ—΄ ν˜•νƒœλ‘œ return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μ™„μ„±ν•˜μ„Έμš”.

 

μ œν•œ 쑰건
  • numberλŠ” 2자리 이상, 1,000,000자리 μ΄ν•˜μΈ μˆ«μžμž…λ‹ˆλ‹€.
  • kλŠ” 1 이상 number의 자릿수 λ―Έλ§ŒμΈ μžμ—°μˆ˜μž…λ‹ˆλ‹€.

μ•Œλ§žμ€ μ•Œκ³ λ¦¬μ¦˜μ„ λ– μ˜¬λ¦¬κΈ° νž˜λ“€μ—ˆλ‹€.

κ·Έλ¦¬λ””λ‹ˆκΉŒ κ·Έλƒ₯ μ•žλ’€λ§Œ λΉ„κ΅ν•˜λ©΄ λ˜λ €λ‚˜?!ν•˜κ³  μ²˜μŒμ—λŠ” 숫자의 μ•ž/λ’€λ§Œ λΉ„κ΅ν•΄μ„œ 더 큰수λ₯Ό 남겨놓고,

μž‘μ€ 수λ₯Ό eraseν•˜λŠ” λ°©λ²•μœΌλ‘œ ν•˜μ˜€λŠ”λ°

μ–΄μ°Œμ €μ°Œ μ½”λ“œμ‹€ν–‰ ν…ŒμΌ€λŠ” λ‹€ λ§žμ•˜μ§€λ§Œ, μ±„μ μ˜ κ²°κ³ΌλŠ” μ²˜μ°Έν–ˆλ‹€....

 

κ·Έλž˜μ„œ λ­”κ°€ 이 방법이 μ•„λ‹Œλ“―ν•΄μ„œ κ΅¬κΈ€λ§ν–ˆμŒ. πŸ€“

μ„€λͺ…을 읽고도 이해가 λ°”λ‘œ μ•ˆλ˜μ–΄μ„œ μ—¬λŸ¬λ²ˆ 생각해보고 μ •λ¦¬ν•΄λ³΄μ•˜λ‹€.

 

 

1. numberκ³Ό answer은 μ•žμ—μ„œλΆ€ν„° μˆœμ„œκ°€ κ·ΈλŒ€λ‘œ 이어지고, number.size() - k 개의 μˆ«μžκ°€ ν•„μš”ν•˜λ―€λ‘œ

    i번째둜 number의 숫자λ₯Ό λ½‘μœΌλ €λ©΄ κ·Έ 뒀에 μ΅œμ†Œν•œ number.size()-k-i 개의 μˆ«μžκ°€ 더 μžˆμ–΄μ•Ό ν•œλ‹€.

 

2. number.size() - k - i = number.size() - ( k + i )

 

3. λ”°λΌμ„œ number인덱슀 탐색 μ‹œ 뽑을 숫자의 인덱슀 μ˜μ—­μ€ start ~ k+i κΉŒμ§€μ΄λ‹€.

 

 

 

 

λ‚˜μ˜ 풀이

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

string solution(string number, int k) {
    string answer = "";
    int answersize = number.size() - k;
    int idx = 0;
    for(int i = 0; i < answersize; ++i){
        
        char maxint = number[idx];
        int maxidx = idx;
        
        for(int j = idx; j <= k+i; j++){ // k + answersize = number.size()
            if(maxint < number[j]){
                maxint = number[j];
                maxidx = j;
            }
        }
        idx = maxidx + 1;
        answer += maxint;
    }
    
    return answer;
}
728x90