[큰 수 만들기] - 그리디 ★★★☆ / 복습 ○

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

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

---

[ 문제 접근 ]

 

노트에 인덱스 계산 해가면서 꾸역꾸역 풀었던 문제.

풀고나서 다른 사람 풀이 보니깐 다들 비슷비슷하게 푼거 같긴 하다.

 

나는 string을 int로 바꿔서 max_element로 대소 비교를 해줬는데, char 끼리 비교해도 동일한 대소 비교 결과가 나오기 때문에 굳이 int로 변환할 필요가 없었다.

 

이런 문제는 그리디라는걸 알았으면 그때 부터는 구현 문제라고 생각한다.

특별한 접근 과정은 없었고, 예제 케이스를 보면서 구현했다.

---

[ 최종 코드 ]

 

#include <string>
#include <vector>
#include<algorithm>
#include<iostream>
 
using namespace std;
 
 
string solution(string number, int k) {
	string answer = "";
 
	int i = 0;
	while (k) {
		int start = i;
		vector<int> temp;
		for (i; i <= start+k; i++) {
			temp.push_back(number[i] - '0');
		}
		vector<int>::iterator temp_itr = max_element(temp.begin(), temp.end());
 
		i = start + (temp_itr - temp.begin()) + 1; // 가장 큰 수 다음 수를 i로
		k -= temp_itr - temp.begin(); // 선택한수랑 시작한수 거리만큼 제거한거다.
		answer += to_string(*temp_itr);
 
		if (number.length() - i <= k) return answer;  // 이거 안하면 테스트케이스 12번 통과 X   ("1111",2) 일때 통과하게끔. 버려야되는 문자랑 남은 문자랑 같아질 때 리턴.
	}
	for (int j = i; j < number.length(); j++) { // k가 0이라서 빠져나왔는데 number에 나머지 문자들 있을때. ( "4177252841",4)
		answer += number[j];
	}
 
 
	return answer;
}

 

---

[ Key Point ]

 

👉 

---

[ 다른 사람 풀이 ]

 

ref :: https://devje8.tistory.com/4

[프로그래머스] 42883_큰 수 만들기(c++)

 

와..!! 이 분은 stack으로 풀었는데 monotone stack 개념과 비슷하게 푸신것 같다.

 

복습할때는 꼭 이렇게도 풀어봐야겠다!!