[Programmers] 큰 수 만들기 (C++)

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

Try 1

1. K번째까지 탐색하며 가장 큰 수 전까지 제거
2. 확정된 처음 수 이후부터 끝까지 탐색하면서 
   다음 수와 비교했을 때 수가 증가한 경우 해당 수 제거
3. 제거함에도 불구하고, k가 남은 경우 k만큼 끝 자리 수 제거ㅌ

테스트 케이스는 다 맞았지만, 채점 결과 하나만 통과,,,
스택구조로 다시 풀어보겠다.

string solution(string s, int k) 
{
    int f_val = 0;
    int f_inx;
    
    for(int i=0; i<=k; i++) // 1. 과정
    {
        if(f_val < s[i] - '0')
        {
            f_val = s[i] - '0';
            f_inx = i;
        }
        
        
    }
    
    s = s.substr(f_inx, s.size() - f_inx); 
    k = k - f_inx;
    
    while(k > 0) // 2. 과정, 지워야할 숫자가 없다면 종료
    {
        vector<int> idx;
        
        for(int i=0; i<s.size()-1; i++) //다음 수가 커지는 경우 인덱스 저장
        {
            if(s[i] < s[i+1] && idx.size() < k)
                idx.push_back(i);
        }
        
        for(int i=0; i<idx.size(); i++) // 저장된 인덱스의 수 제거
        {
            s = s.erase(idx[i]-i,1);
        }
        
        k = k - idx.size(); //지워야 할 숫자들의 수 갱신
        if(idx.size() == 0) //다음 수가 커지는 경우가 없다면 끝내기
            break;
    }
    
    if(k > 1) // 3. 과정
        s = s.substr(0, s.size() - k);
    return s;
}

Try 2

테스트 케이스를 안 알려줘서 직접 다 쥐어짜내면서 하느라 죽는줄 알았다...

오름차순, 내림차순 섞으면서 해보고 오름차순으로만도 해보고, 내림차순만으로도 해보고

두자리 숫자에 하나만 지워보기도 하고, 테스크 케이스를 최대한 많이 굴려보는게 접근하기 좋다.

특히나 프로그래머스는 불친절한 감이 없지않아 있다...

 

아이디어는 아래 블로그를 적극적으로 활용했다.

큰 수 만들기(그리디, 탐욕법)[프로그래머스]

string solution(string s, int k) 
{
    int f_val = 0;
    int f_inx = 0;
    string ans;
    
    for(int i=0; i <= k; i++) //처음 큰 수까지 추출 과정
    {
        if(f_val < s[i] - '0')
        {
            f_val = s[i] - '0';
            f_inx = i;
        }  
    }
    
    
    s = s.substr(f_inx, s.size() - f_inx); //추출한 값까지 제거
    
    ans += s[0];
    k = k - f_inx;
    
    f_inx = 1; //첫 자리는 정했으므로 그 다음 자리부터 시작
    
    while(k>0 && f_inx< s.size()) 
    { //더 이상 지울 수가 없거나 탐색 인덱스가 범위를 초과하면 중단
        f_val = 0; //수 비교 초깃값 0
        int tmp = f_inx; //탐색 시작점 저장
        
        for(int i=0; i<=k && tmp+i < s.size(); i++) 
        { //가장 큰 수의 인덱스를 찾는 과정
            if(f_val < s[tmp+i] - '0')
            {
                f_val = s[tmp+i] - '0';
                f_inx = tmp+i;
            }
        }
        
        ans += s[f_inx]; // 찾은 큰 수를 추가
        k -= (f_inx - tmp); 
        //큰 수의 인덱스와 시작점의 차이는 지운 숫자의 수임
        
        f_inx ++;  //큰 수의 인덱스 다음 인덱스부터 탐색 시작      
    }
    
    if(k>0) //k가 남아있는 경우 끝에서 k만큼 지워 주면 됨
      ans = s.substr(0, s.size()-k);
    else //다 지운 경우 탐색 인덱스 부터 끝부분까지 마저 채워주면 됨
      ans += s.substr(f_inx, s.size() - f_inx);
       
    
    return ans;
}