[C++] 정렬 모음

42747 H-Index [문제 바로가기]

 

solution

1. 내림차순으로 citations 배열을 정렬한다.

2. citations의 크기에서부터 0까지 i를 감소시키면서 for문을 돈다.

2-1. 가능한 h의 최대는 citations의 크기이다. (ex. [2, 2])

 

3. 이때의 i값이 가능한 h값인지 탐색한다.

3-1. citations의 값이 i보다 크거나 같으면 정렬이 안되어 있으므로 탐색 인덱스를 증가시킨다.

3-2. 이때 같은 경우에도 증가시키는 이유는 문제 조건이 "이상" 이기 때문에 값에 포함되기 때문이다.

3-3. citations 값이 맨 처음으로 i보다 크거나 같아지는 순간이 정답이다.

 

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

int solution(vector<int> citations) {
    int answer = 0;
    
    sort(citations.begin(), citations.end(), greater<>());
    for(int i = citations.size();i >= 0;i--) {
        int idx = 0;
        while(idx < citations.size() && citations[idx] >= i)
            idx++;
        
        if (idx >= i) {
            answer = i;
            return answer;
        }
    }
    
    return answer;
}

---

42746 가장 큰 수 [문제 바로가기]

 

solution

1. numbers의 원소를 string으로 바꾼다.

2. string으로 변환된 원소를 큰 수를 만들 수 있는 내림차순으로 정렬한다.

3. 정렬된 배열을 돌면서 answer 문자열에 차례대로 추가한다.

4. answer 문자열이 모두 0이라면 0을 하나로 만들어준다.

 

2-1. 이때 문자열의 자릿수마다 배열을 돌면서 int(or char)로 변환하여 크기를 비교한다. (c++는 ascii 코드고 char == int)

2-2. 자릿수가 다르다면 가장 앞의 문자와 비교한다.

즉 89, 899 를 비교할 때는 => 898, 899 를 비교하도록 만든다.

이 경우 899 > 898 이기 때문에 정렬하면 [899, 89] 이 된다.

2-3. 만약 길이가 달라서 가장 앞의 문자를 붙였더니 두 문자열이 같아진다면 가능한 경우의 수를 따진다.

즉 89, 898 을 비교할 때 2-2 을 적용하면 => 898, 898 으로 두 문자열이 같아진다.

이 경우 가능한 경우의 수인 89898, 89889 를 비교한다.

이때 89898 > 89889 이기 때문에 정렬하면 [89, 898] 이 된다.

2-4. 2-3으로 만든 두 문자열이 같다면 return false 한다.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(string str1, string str2) {
    int idx1 = 0, idx2 = 0;
    
    while(idx1 < str1.size() || idx2 < str2.size()) {
        // 길이가 다르면 맨 앞자리 문자와 비교
        int char1 = (idx1 >= str1.size()) ? str1[0] : str1[idx1];
        int char2 = (idx2 >= str2.size()) ? str2[0] : str2[idx2];
        
        if (char1 != char2) {
            return char1 > char2;
        }
            
        idx1++;
        idx2++;
    }
    
    // 맨 앞자리를 붙여도 문자열이 같으면 가능한 경우의 수 비교
    string temp1 = str1+str2, temp2 = str2+str1;
    
    // 그래도 문자열이 같으면 return false
    if(temp1 == temp2)
        return false;

    return compare(temp1, temp2);
}
string solution(vector<int> numbers) {
    string answer = "";
    
    vector<string> result;
    for(int i = 0;i < numbers.size();i++) {
        result.push_back(to_string(numbers[i]));
    }
    
    sort(result.begin(), result.end(), compare);
    
    string temp = "";
    for(int i = 0;i < result.size();i++) {
        answer += result[i];
        temp += "0";
    }
    
    // 문자열이 모두 0이면 하나의 0으로 만들어준다.
    if (answer == temp)
        answer = "0";
    
    return answer;
}

 

 

 

사실 이렇게 풀긴 했는데 이 부분을 true로 만들면 segfault 가 발생한다.,..

    // 그래도 문자열이 같으면 return false
    if(temp1 == temp2)
        return false;