프로그래머스 고득점 키트 정렬

2020-09-06 · 배운 것 · 6분 읽기

programmers.co.kr/learn/courses/30/lessons/42748

간단하므로 풀이방법 생략하겠음.

코드

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

using namespace std;

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

    for (auto ele : commands)
    {
        int _i = ele[0] - 1;
        int _j = ele[1] - 1;
        int _k = ele[2];

        vector<int> temp;
        for (int i = _i; i <= _j; i++)
            temp.push_back(array[i]);
       
        //sort
        sort(begin(temp), end(temp));

        //k번째 구하기
        answer.push_back(temp[_k - 1]);
    }

    return answer;
}

programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

제한사항중

numbers의 원소는 0 이상 1,000 이하입니다.

sort의 비교함수를 작성할때 이 부분을 잘보면 간단하게 풀수있는 문제였다.

코드

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

using namespace std;

bool compare(const pair<int, string>& a, const pair<int, string>& b)
{
    return a.first > b.first;
}

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

    //1. int -> string
    vector<pair<int, string>> sortArr;
    for (int num : numbers)
    {
        string strNum = to_string(num);
        int key = 0;

        string temp;
        for (int i = 0; i < 4; i++)
        {
            temp += strNum;
        }

        string subTemp = temp.substr(0, 4);
        key = stoi(subTemp.c_str());

        sortArr.push_back({ key, strNum });
    }

    //2. sort
    sort(begin(sortArr), end(sortArr), compare);

    for (auto ele : sortArr)
        answer += ele.second;

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

    return answer;
}

programmers.co.kr/learn/courses/30/lessons/42747

코딩테스트 연습 - H-Index

문제 자체가 이해가 잘 안되는 문제였다.
문제 이해만 빠르게 한다면 이진탐색을 이용해서 간단하게 풀수있다.

코드

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

using namespace std;

void binarySearch(vector<int>&citations, int start, int end, int& answer)
{
    //탈출조건
    if (start > end)
        return;

    int mid = (start + end) / 2;
    int check = citations.end() - lower_bound(citations.begin(), citations.end(), mid);

    if (mid <= check)
    {
        answer = max(mid, answer);
        binarySearch(citations, mid + 1, end, answer);
    }
    else
    {
        binarySearch(citations, start, mid - 1, answer);
    }

}

int solution(vector<int> citations) {
    int answer = 0;
    
    //1. sort 
    sort(begin(citations), end(citations));

    //2. 이진탐색으로 최댓값 찾기
    int minValue = citations[0];
    int maxValue = citations[citations.size()-1];

    //binary search
    binarySearch(citations, 0, maxValue, answer);

    return answer;
}