[코테/프로그래머스] 정렬모음(K번째수, 가장 큰 수, H-Index)

이수진·2022년 7월 13일
0
post-custom-banner

문제1. K번째수 (난이도: Level 1)

문제는 다음과 같습니다.

제 코드는 다음과 같습니다.

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

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> ans;
    
    for(int i=0; i<commands.size(); i++){
        vector<int> tmp;
        for(int j=commands[i][0]-1; j<commands[i][1]; j++){
            tmp.push_back(array[j]);
        }
        sort(tmp.begin(), tmp.end());
        ans.push_back(tmp[commands[i][2]-1]);
    }
    
    return ans;
}

많은 투표를 받은 풀이는 다음과 같습니다.

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

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    vector<int> temp;

    for(int i = 0; i < commands.size(); i++) {
        temp = array;
        sort(temp.begin() + commands[i][0] - 1, temp.begin() + commands[i][1]);
        answer.push_back(temp[commands[i][0] + commands[i][2]-2]);
    }

    return answer;
}
  • 살펴볼 지점
    temp = array 로 반복문 이용 없이 바로 벡터 복사할 수 있음
    ✅ 벡터 정렬 수행 시, 벡터 범위 길이 지정할 수 있음

문제2. 가장 큰 수 (난이도: Level 2)

문제는 다음과 같습니다.

얼핏보면 너무 쉽지만 함정이 숨어있는 문제

두 번째 예시만 잘 보면 바로 알 수 있다!

그냥 내림차순으로 정렬을 해야 할 것 같지만,
"3", "30" 에서는 330 > 303 이므로, "3" 이 "30" 보다 크도록 정렬을 수행해줘야 합니다.

다른 경우에서는 그냥 내림차순으로 정렬을 진행해야하는데, 이 경우에 대해서는 따로 처리를 해줘야하나? 생각했었는데, 생각해보니 두 문자열을 더해서 이를 비교해주면 바로 끝나게 됩니다.

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

using namespace std;

bool cmp(const string &a, const string &b){
    return a + b > b + a;
}

string solution(vector<int> numbers) {
    vector<string> v;
    
    for(int i=0; i<numbers.size(); i++){
        v.push_back(to_string(numbers[i]));
    }
    sort(v.begin(), v.end(), cmp);
    
    string s = "";
    for(int i=0; i<v.size(); i++) s += v[i];
    
    if(s[0]=='0') return "0";
    else return s;
}

그리고 주의해야 할 점이
numbers의 원소는 0부터라는 점!
즉 "000000" 과 같은 문자열이 저장이 되면 -> 숫자로 되면 0이 반환 되겠지만,
우리는 숫자의 범위가 매우 커서 이를 문자열로 바꿔서 계산해주었으므로
문자열의 맨 앞이 "0" 으로 시작하는 경우 -> (이후에도 계속 0이므로) 이를 "0" 으로 반환을 해주어야합니다.

많은 투표를 받은 풀이는 다음과 같습니다.

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

using namespace std;

bool compare(const string &a, const string &b)
{
    if (b + a < a + b)
        return true;
    return false;
}

string solution(vector<int> numbers) {
    string answer = "";

    vector<string> strings;

    for (int i : numbers)
        strings.push_back(to_string(i));

    sort(strings.begin(), strings.end(), compare);

    for (auto iter = strings.begin(); iter < strings.end(); ++iter)
        answer += *iter;

    if (answer[0] == '0')
        answer = "0";

    return answer;
}

문제3. H-Index (난이도: Level 2)

문제는 다음과 같습니다.

솔직히 문제가 설명이 부족한 것 같습니다.
(문제풀다가 나 난독증이 있는 줄 😅)

질문하기에서 문제에 대해서 좀 찾아보다가 "함정에 빠지면 안되는거. h는 배열의 값중 하나가 아닙니다." 라는 말을 듣고 바로 다시 고쳐서 풀게 되었습니다.

중요한 건, h는 배열의 값 중 하나가 아니어도 된다는 것입니다!
즉 0부터 ~ 배열의 사이즈 중 가장 큰 값 이 사이 중 어느 하나의 값이 될 수 있다는 것입니다

먼저 제 풀이는 다음과 같습니다.

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

using namespace std;

int solution(vector<int> c) {
    sort(c.begin(), c.end(), greater<int>()); // 내림차순 정렬
    
    int ans = 0;
   
    for(int i=c.size(); i>=0; i--){
        for(int j=0; j<c.size(); j++){
            if(c[j] >= i && j+1 >=i){
                ans = i; break;
            } 
        }
        if(ans) break;
    }
    
    return ans;
}

많은 투표를 받은 풀이는 다음과 같습니다.

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

using namespace std;

int solution(vector<int> citations) {
    sort(citations.begin(), citations.end(), greater<int>());

    for (int i = 0; i < citations.size(); ++i) {
        if (citations[i] < i + 1) {
            return i;
        }
    }

    return citations.size();
}

위 풀이도 참고해서 개선한 풀이는 다음과 같습니다.

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

using namespace std;

int solution(vector<int> c) {
    sort(c.begin(), c.end(), greater<int>()); // 내림차순 정렬
    
    int ans = 0;
   
    for(int i=0; i<=c.size(); i++){ // max 값은 : c.size() -> 논문 수
        if(i+1 >= c[i]) return i;
    }
    
    return ans;
}

설명만 좀 더 친절했었다면 .. 좀 더 좋았을 텐데!

profile
꾸준히, 열심히, 그리고 잘하자
post-custom-banner

0개의 댓글