22.05.09. 풀었던 문제들

프로그래머스 lv.3

​

1. 야근 지수

priority queue를 이용하는 방법, set과 map을 이용해 조금 더 최적화시킨 2가지 방식으로 풀었는데, 후자의 경우 뭔지 모르겠는데 안된다. (시간적 이득은 분명히 있다)

#include <string>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;
typedef long long ll;

long long solution(int n, vector<int> works) {
    priority_queue<int> pq;
    
    for(int i : works) pq.push(i);
    
    while(n > 0 && !pq.empty()){
        ll max_value = pq.top(); pq.pop(); n--;
        if(max_value == 1) continue;
        pq.push(max_value-1);
    }
    
    
    long long answer = 0; ll pqtop;
    while(!pq.empty()){
        pqtop = pq.top(); pq.pop();
        answer += pqtop * pqtop;
    }
    
    return answer;
}

 

2. 줄 서는 방법

k번째 순열을 가져오는 방법. 재밌었다. 오름차순으로 정렬된 people vector가 있을 때, i번째 자리에 오는 index는 k / (n-1)!이다. 왜냐하면 순열의 특성상 i번째 자리의 index는 (n-1)!의 경우의 수마다 바뀌기 때문이다. people vector에서 해당 index를 가져오고, 가져온 것이니 삭제. 이를 반복하면 풀리는 문제다. 다만 유의할 점. k는 자연수이고, 우리는 arr에서 index를 가져오고 싶기 때문에 k도 index처럼 0부터 시작하게 바꿔줘야 했다. 이걸 안해서 시간을 태워먹었다.

 

// 줄 서는 방법

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

using namespace std;
typedef long long ll;

vector<int> solution(int n, long long k) {
    vector<ll> factorial(21); factorial[0] = factorial[1] = 1;
    for(int i = 2; i<=20; i++){
        factorial[i] = factorial[i-1] * i;
    }
    
    vector<int> people(n);
    for(int i = 1; i<=n; i++){
        people[i-1] = i;
    }
    
    vector<int> answer;
    k--; // k번째 방법 : index로 바꾸면 k-1임. 이걸 안해줬음!
    for(int i = 1; i<n; i++){
        int idx = k / factorial[n-i];
        k = k % factorial[n-i];
        answer.push_back(people[idx]); people.erase(people.begin() + idx);
    }
    answer.push_back(people[0]);

    
    return answer;
}
​