정렬 알고리즘 풀이 정리

알고리즘 개요

문자열을 통한 정렬 , 탐색 ,bfs, dfs 에도 이용되는 범용성 높은 알고리즘이다

• vector를 주로 이용
• temp, for를 이용한 풀이
• sort 메소드를 파악해야 수월하게 풀수 있다.
• 중복 제거 메소드
  • unique(v.begin(), v.end()) :unique는 연속된 중복 원소를 vector의 제일 뒷부분으로 쓰레기값으로 보내버린다.
  • v.erase(v , v.end()): vector에서 필요없는 (iter가 할당되지 않은 원소)를 제거한다.
  • unique와 erase를 함께 쓰면 해당 중복배열의 중복을 제거할 수 있다.
• 배열,문자열,벡터 원소 비교 알고리즘
  • 이중 for문 : 가장 직관적이면서 구현하기 편하다 . but 시간복잡도가 높음. 코드가 복잡
  • 1번배열 원소가 2번배열에 있는지 판단: for문 한번으로 시간복잡도와 코드가 비교적 간편. but 상황이 제한적

sort 의 종류

예제

프로그래머스 - 가장 큰수

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

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

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> temp;
    for(int i=0;i<numbers.size();i=i+1){
        temp.push_back(to_string(numbers[i]));
    }
    sort(temp.begin(),temp.end(),cmp);
    if(temp.at(0)=="0") return "0"; 
    for(int i=0;i<temp.size();i=i+1){
        answer+=temp[i];
    }
    return answer;
}

프로그래머스 - H-index

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    vector<int> temp;
    for(int i=citations.size();i>=1;i=i-1){
        int cnt=0;
        for(int j=0;j<citations.size();j=j+1){
            if(citations[j]>=i) cnt+=1;
        }
        if(cnt<=i) 
            answer=cnt;
        //return answer;
    }
    return answer;
}

카카오 2019 blind recruit

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

bool cmp(pair<int,double> a, pair<int, double> b){
    if (a.second==b.second)
        return a.first < b.first;
    else
        return a.second>b.second;
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    
    vector<pair<int, double>> vv;
    int failure=0;
    for(int i=1; i<N+1; i++){
        int cnt=0;
        pair<int, float> temp;
        for(int j=0; j<stages.size(); j++){
            if(i==stages[j]) {
                cnt++;
            } 
        }
        if(cnt==0) {
            temp=make_pair(i, 0);
        }
        else {
            temp=make_pair(i,(double)cnt/(double)(stages.size()-failure));
        }
        failure=failure+cnt;
        vv.push_back(temp);
    }
    sort(vv.begin(), vv.end(), cmp);
    for(int i=0; i<vv.size(); i++) {
        answer.push_back(vv[i].first);
    }
    return answer;
}