[P4] 백준 1422번 숫자의 신 C++ 문자열, 정렬, 그리디 알고리즘

리뷰

 

https://www.acmicpc.net/problem/1422

백준 16496번 큰 수 만들기 파이썬

백준 16496번 큰 수 만들기 파이썬

 

위 문제의 응용 버전인 문제, 유사 문제를 접근한 적이 있어 쉽게 풀 수 있었다

 

 

전역 변수

• k : 자연수의 개수를 저장할 변수
• n : 뽑아낼 수의 개수를 저장할 변수
• S : 뽑아낼 수의 우선 순위를 정의하기 위한 구조체, 정렬용 문자열을 기준으로 내림차순 정렬한다.
• s1 : 각 수를 저장하고 정렬하기 위한 S타입 벡터

 

함수

없음

 

 

문제풀이

1. k, n값을 입력 받고, 변수 mv를 0으로 초기화 후 k개의 정수를 입력 받아준다.
2. 각 정수는 변수 def에 문자열로 입력 받고, mv를 def를 정수로 변경한 값 중 최대값을 저장해 준다.
3. 변수 cmp에 def를 복사해 주고, cmp의 길이가 10보다 작다면 cmp를 복사하여 이어 붙여준다.
4. s1에 cmp, def를 추가해 주고, 모든 정수를 입력 받았다면 sort함수를 통해 s1을 정렬해 준다.
5. 변수 mvs에 mv를 문자열로 치환한 값을 저장해 주고, 변수 ans를 빈 문자열로 초기화 해준다.
6. 변수 dup에 n-k값을 저장해 주고, 정렬된 s1을 순회해 준다.
7. ans에 현재 요소의 def값을 더해주고, dup가 0보다 크면서 def가 mvs와 같다면 dup개수만큼 ans에 def를 추가로 더해준다.
8. s1순회를 마친 후 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. mvs가 처음 혹은 마지막에만 올 줄 알았으나 중간에 들어와야 하는 케이스도 존재했다.
2. 현재 요소가 mvs일 경우 n-k횟수만큼 현재 요소를 더해주는 방법을 구현하여 AC를 받았다.

 

참고 사항

1. 문자열 cmp는 정렬을 위한 비교용으로만 사용한다.
2. 최소 길이 10을 맞춰주는 이유는 각 수는 1,000,000,000보다 작거나 같은 자연수이다. 라는 조건 때문이다.
3. 모든 정수를 한번씩 사용하되 n이 k보다 클 경우 가장 큰 수를 n-k번 추가로 사용해 주면 된다.
4. 사용해 주는 위치는 동일한 수가 추가되는 시점이다.

 

정답 코드

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

int k, n;
struct S {
	string cmp, def;
	bool operator<(const S& other) const {
		return cmp > other.cmp;
	}
};
vector<S> s1;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> k >> n;

	int mv = 0;
	for (int i = 0; i < k; ++i) {
		string def; cin >> def;
		mv = max(mv, stoi(def));
		string cmp = def;
		while (cmp.size() < 10) cmp += cmp;
		s1.push_back({cmp, def});
	}

	sort(s1.begin(), s1.end());
	string mvs = to_string(mv);
	string ans = "";
	int dup = n - k;
	for (const S& s : s1) {
		ans += s.def;
		if (dup > 0 && s.def == mvs) {
			while (dup--) ans += s.def;
		}
	}

	cout << ans;
}