정렬
정렬문제는 숫자 및 문자의 대소비교를 하는 문제다. 주로 sort 함수를 사용하여 대소비교를 할 수 있다. pair 형태로 인자를 받아 두번째 인자에 대한 대소비교를 추가적으로 하는 경우에는 compare 함수를 추가적으로 만들어 용도에 맞게 작성하는 것이 좋다.
문제
가장 큰 수
https://programmers.co.kr/learn/courses/30/lessons/42746?language=cpp
문제
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
제한사항
numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
예시
## numbers, return
[6, 10, 2] 6210
[3, 30, 34, 5, 9] 9534330
풀이
모든 경우의 수를 따지면 factorial(100,000) 이므로 경우의 수로 계산할 수 없다. 가장 큰 수를 만들기 위해서는 앞자리 수가 가장 큰 값부터 오면된다. 하지만 단순히 숫자를 비교하면 이상하다는 것을 알 수 있다. 예를들어 [3, 32, 356, 321]이 있다고 해보자. 가장 큰 값은 356이고 그 다음 값은 310인데, “356,321,32,3” 보다 “356,3,32,321”이 더 큰 값이라는 것을 알 수 있다. 이는 전체 숫자의 비교를 하면 안되고 다음에 오는 자리의 숫자를 비교해야한다는 뜻이다. 즉, 모든 숫자의 자리수를 맞춰주면 된다. 가장 큰 값은 1000이므로 4자리 수로 맞춰주면 된다.
하지만 주의할 점이 있다.
단순히 0을 사용하여 [3000, 3200, 3560, 3210] 으로 맞춰주면 3200보다 3210이 먼저 나오게 되는데, “321,32”보다 “32,321”이 더 크기 때문에 다른 방법으로 적용해주어야 한다. 맨앞자리 수로 나머지 4자리 수로 맞춰주면 이 문제를 해결할 수 있다.
[3333, 3233, 3563, 3213] 으로 맞춰주면, “356, 3, 32, 321” 순서가 되어 가장 큰 값을 갖는다는 것을 알 수 있다.
위에 조건으로만 풀면 정답이 달라서 예외 경우를 생각해보았다. 첫번째는 number의 요소가 0인 경우는 무한 loop를 돌 수 있기 때문에 예외처리 해줘야한다. 두번째 반례는 다음과 같다. [30, 303]이 input으로 들어가면 4주로 변환하는 과정에서 [3033, 3033]으로 같아지게 되고 같은 값이기 때문에 정렬이 따로 되지 않는다. 그래서 원래 숫자를 반복하여 4자리 숫자를 만들어야 한다. 왜냐면 특정 숫자 다음에 와야할 숫자가 자기 자신보다 커야하기 때문이다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair <string, string> a, pair <string, string> b){
return a.first > b.first;
}
string solution(vector<int> numbers) {
string answer = "";
// 4자리 수로 채워진 vector
vector <pair <string, string>> filled_numbers;
for(auto number:numbers){
// 4자리수로 만들기 (맨 앞에있는 숫자로 뒤에서부터 채우기)
string k = to_string(number);
int i = 0;
while(k.length() < 4){
k += k[i];
i++;
}
filled_numbers.push_back(make_pair(k, to_string(number)));
}
sort(filled_numbers.begin(), filled_numbers.end(), compare);
// 큰 수부터 정렬된 numbers 숫자 뽑아내기
for(auto pair:filled_numbers){
answer += pair.second;
}
// 0000과 같은 수가 나오면 그냥 0으로 출력
if(answer[0] == '0'){
answer = "0";
}
return answer;
}
H-index
https://programmers.co.kr/learn/courses/30/lessons/42747
문제
H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.
어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.
어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.
제한사항
과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
논문별 인용 횟수는 0회 이상 10,000회 이하입니다.
예시
## citations, return
[3, 0, 6, 1, 5] 3
풀이
문제가 조금 헷갈리지만 예시를 쓰면서 손으로 풀어보면 이해가 간다. 제한 조건이 1,000과 10,000 이므로 1억이 넘지 않아 완전탐색을 하면 될 것이라고 생각했지만 그것보다 더 깔끔한 풀이가 생각났다. h 보다 크거나 같은 요소의 개수를 찾으면 되므로 sort 를 이용하여 정렬한 뒤 h 번째에 있는 수가 h 보다 큰지 검사하면된다. 예를들어 [3, 0, 6, 1, 5] 를 정렬하면 [6, 5, 3, 1, 0] 이고 3번째 수가 3보다 크거나 같으므로 최대값은 3이 된다. 인덱스는 0부터 시작한다는 것을 감안하면 된다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(int a, int b){
return a > b;
}
int solution(vector<int> citations) {
int answer = 0;
sort(citations.begin(), citations.end(), compare);
for(int h=0; h<=citations.size(); h++){
if(citations[h] < h+1) return h;
}
return answer;
}