23.02.18. 풀었던 문제들

리트코드 daily challenge - 226. Invert Binary Tree

 처음 풀었을 때 3ms가 나왔다. DFS라는 함수를 따로 정의했기 때문인 것 같은데... 굳이 새로운 함수 안 짜고 바로 풀면 0ms가 나온다.

 

프로그래머스 lv 1 삼총사

 3sum 문제인데, 여기서는 제한 조건이 널널해서 3중for문으로 풀어도 된다.

 

프로그래머스 lv 1 크기가 작은 부분 문자열

 substring을 활용하는 문제

 

프로그래머스 lv 1 콜라 문제

반복문 쓰면 되는 수학 문제

 

프로그래머스 lv 1 푸드 파이트 대회

반복문 + reverse 쓰는 문제

 

프로그래머스 lv 1 가장 가까운 같은 글자

char c의 [이전 위치]를 기억해 두면 쉬운 문제. DP의 일종.

 

프로그래머스 lv 2 귤 고르기

크기별 귤 개수를 map으로 정렬하고, 귤 개수가 적은 것부터 정렬한 후, 귤 개수가 적은 귤부터 더 뺄 수 없을 때까지 빼면 됨

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

using namespace std;

typedef pair<int, int> pii;

bool cmp(const pii &a, const pii &b){
    if(a.second == b.second) return a.first < b.first;
    else return a.second < b.second;
}

int solution(int k, vector<int> tangerine) {    
    // 크기별 귤 개수 정렬
    map<int, int> m;
    for(int t : tangerine){
        if(m.find(t) == m.end()) m[t] = 1;
        else m[t]++;
    }
    
    // 귤 개수 적은 것 부터 오름차순 정렬
    vector<pii> v(m.begin(), m.end());
    sort(v.begin(), v.end(), cmp);
    
    // 개수 작은 것부터 뺌
    int total = tangerine.size();
    for(int i = 0; i<v.size(); i++){
        if(total - v[i].second < k) return v.size() - i;
        total -= v[i].second;
    }
    
    int answer = 0;
    return answer;
}