프로그래머스 큰 수 만들기

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

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

 

접근법 : 숫자의 위치는 그대로 두고 k개를 제거해서 읽었을때 가장 큰수를 만드는 문제입니다.

 

첫번째로 가장 쉽게 생각하자면 처음 숫자가 있을때  number[i]에 해당하는 숫자보다 작으면 뒤에 붙여주고

크다면 number[i]보다 같거나 큰숫자가 나올때까지 뒤에있는 숫자르 지워낸다음 뒤에서 붙여줍니다.

 

이렇게 생각만하면 

1,3번째 테스트케이스는 잘나오지만 

2번째 테스트 케이스에선 결과가 4밖에 나오질 않습니다.

 

두번째로 만들어야하는 사이즈는 number.size()-k가 됩니다. 즉

resultsize= number.size()-k 로 저장을해두면

2번째 테스트케이스에선 number="1231234" k=3 이라서 길이가 7-3이니 resultsize=4 가 되어야합니다.

 

세번째로 첫번째처럼 지워나간다고 생각하고 number[i]를 보면서 i가 커질수록 지워야 할수있는 기회는 줄어듭니다.

왜냐하면 resultsize를 맞춰줘야 하기때문에 그렇기에 현재 남아있는 공간을 

space라 할때 space= number.size()-i 가 성립하고 

현재 계속 결과물을 만들어낸 result.size()와 space의 합이 resultsize보다 커지면 pop을 해줘도 괜찮지만 그렇지않은경우 resultsize를 맞춰줘야하기때문에 그냥 뒤에 갖다 붙여야합니다.

 

소스코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

#include <bits/stdc++.h> using namespace std; string solution(string number, int k) {     string result;     //실제 결과가 되야하는 사이즈     int resultsize = number.size() - k;     for (int i = 0; i < number.size() ; i++)     {         //남은 여유공간         int space = number.size() - i;         //맨뒤에있는 값이 현재 숫자보다 크고 앞으로 밀어도 실제 결과 사이즈가 되도록 만족하는지         while (!result.empty() && result.back() < number[i]&& result.size() + space > resultsize)             result.pop_back();         if(result.size()<resultsize)             result += number[i];     }     return result; } Colored by Color Scripter

cs

 

 

모르는점 혹은 궁금한점 어떤 질문이든 댓글은 언제나 환영입니다.