3.txt

프로그래머스 : 더맵게 문제
priority queue : 알아서 정렬되어서 쌓아지는 구조, 입력과 동시에 정렬이 될 필요가 있는 경우

펑터 : 장점 : 인라인이 된다.
람다 : 요즘은 람다를 많이 쓴다.

라면공장 : 마찬가지로 정렬해서 풀면 효율성 떨어진다. 프라이어티 큐로 하면 좋다.

//====================정렬=============

정렬 하는 이유 : 검색하는 데 훨씬 빨라진다.
정렬을 하면 바이너리 서치가 가능하다 -> logN으로 서치가 가능
(오늘 다시 복습하는 정렬말고 다른 정렬 조금 더 찾아본다.)

현재로는 퀵소트가 가장 효율적임, 머지는 평균이 nlogN이다.
퀵소트가 캐시 히트율이 굉장히 높다. 값을 덜 바꾼다. 따라서 빅오 표기법으로는 비슷하거나 더 안 좋아 보여도 실제로는 더 좋다. 기준점을 잡는 것에 따라서 효율이 달라진다. ( 시간복잡도, 공간복잡도)


선택정렬 : n^2, 작은 데이터 정렬할 떄는 무방하지만 안 좋다. 

삽입정렬 : n^2

버블정렬 : 좌우로 두개씩 짝지어서, 큰거는 오른쪽으로 작은 적으로는 왼쪽

합병정렬 : nlogN 다 분할하고 분할 한 것 끼리 정렬, 컴퓨터 프로그래밍에서 분할과 합치기를 많이 사용한다. 이에 대표적인 방법. 캐시 히트율이 퀵정렬 보다 못하다

퀵정렬 : 기준점을 잡고, (ex 3이라고 하면) 3보다 작으면 왼쪽으로 3보다 큰건 오른 쪽으로, 기준점(3)에서 왼쪽을 퀵 정렬, 오른쪽에서도 퀵 정렬

42748


과제로 풀어오기
https://programmers.co.kr/learn/courses/30/lessons/42746



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

using namespace std;

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


string solution(vector<int> numbers) {
    string answer = "";
    vector<int> a;
    vector<pair<int,int>> v;
    int max;
    
    for(int i = 0; i < numbers.size(); i++) {
        
       
        if(numbers.size() >= 10) {
            v.push_back(pair<int,int>(numbers[i]/10, numbers[i]));
            
        } else {
            v.push_back(pair<int,int>(numbers[i], numbers[i]));
        }
    }
    
    
    sort(v.begin(), v.end(), cmp);
    
    for(int i = 0; i < numbers.size(); i++) {
        answer += to_string(v[i].second);
    }
    
    return answer;
}