22.03.31. 풀었던 문제들

1. 큰 수 만들기

greedy 문제다.

앞에서부터 str[i] < str[i+1]인 경우 str[i]를 지우는 방식으로 반복한다. string의 모든 substr가 monotonic decreasing을 만족한다면 제일 작은 char부터 지워나가면 된다.

​

​

2. 기능개발

size가 작기 때문에 simple하게 queue로 돌려도 되고 (brute-force하게)

아니면 최적화해서 풀 수도 있는 문제였다. 이 경우에는 남은 일자를 계산하고,

예를 들어 3 1 1 4 2 1 5 이라면 3 1 1을 하나로 묶어 배포하고 4 2 1을 하나로 묶고, 5를 묶어 배포해야 된다. 규칙은, 남은 일자가 오름차순이라면 따로 배포해야 한다는 것이다.(<=> 남은 일자가 단조 내림차순인 것들을 찾아 묶으면 된다)

// 기능개발

using namespace std;

typedef pair<int, int> pii;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    queue<pii> q; // .first에는 progresses가, .second에는 speed가 있음.
    
    int size = speeds.size(), completed_work;
    
    for(int i = 0; i<size; i++){
        q.push({progresses[i], speeds[i]});
    }
    
    vector<int> answer;
    
    while(!q.empty()){
        size = q.size();
        while(size--){
            int temp = q.front().first + q.front().second;
            q.push({temp >= 100 ? 100 : temp, q.front().second});
            q.pop();
        }
        
        completed_work = 0;
        while(!q.empty() && q.front().first >= 100){
            completed_work++;
            q.pop();
        }
        if(completed_work != 0)
            answer.push_back(completed_work);
    }

    return answer;
}

// 이렇게 직접 q를 돌려가면서 찾아도 되고

// stack으로도 풀 수 있음. (아래 코드)
// 남은 작업일수를 계산하고
// 예를 들어 5 10 1 1 20 1이라면
// 5 다음에는 10이므로 5만 배포
// 10 다음에는 1 1 20 이므로 20은 배포 못하고, 10 1 1만 배포 가능
// 20 다음에는 1이므로 20 1 같이 배포 가능
// 이렇게 제일 앞에 있는 것의 값보다 더 작은 경우에만 같이 묶을 수 있음

 

3. 더 맵게

pq.size()는 항상 1보다 크다는 것을 증명할 수 있다. 그러므로 while문의 조건이 pq.size() > 1일 때 true로 돌린다. 만약 이 때 pq.top() >= K면 pq의 모든 element가 K보다 크거나 같은 것이 되므로 break, 답을 return한다. 만약 pq.size()가 1인데 pq.top()이 K보다 작다면 못 만드는 것이므로 false이다.

시간복잡도는 1백만 개의 input을 pq에 넣고, "섞는" 연산을 최대 1백만 번 하는 것을 O(nlogn)으로 풀기 때문에 충분하다.

​

​

4. 프린터

circular queue로 푸는 문제다. 예전 코드 보니까 진짜 개판이다 ㅋㅋ 발전해 가고 있다 !

​

​

5. h-index

arr이 내림차순 정렬일 때, arr[i] > i의 의미를 생각해 보자. 귀납적으로

- arr[0] > 0은 1번 이상 인용된 논문이 1편 이상

- arr[1] > 1은 2번 이상 인용된 논문이 2편 이상

- arr[2] > 2는 3번 이상 인용된 논문이 3편 이상

즉 arr[i] > i는 (i+1)번 이상 인용된 논문이 (i+1)편 이상이라는 것이다! 이는 h-index의 조건을 만족한다.

이런 i의 최댓값 k을 찾는다. 이 순간, arr[k+1] <= (k+1)를 만족한다. 그렇지 않다면 arr[k+1] > (k+1)이기 때문에 k가 최댓값이 아니기 때문이다. 한편 이 순간은 arr[k+1](>=arr[k+2] >= arr[k+3] >= ...)부터는 모든 논문이 (k+1)번 이하로 인용되었다는 것이다. (arr[k+1] <= k+1)

따라서, 위 코드가 답이다!

// H-index

using namespace std;

int solution(vector<int> citations) {
    sort(citations.begin(), citations.end(), greater<int>());
    int size = citations.size();
    int h_index = -1;
    for(int i = 0; i<size; i++){
        if(citations[i] > i) h_index = max(h_index, i);
    }
    return h_index + 1;
}

// 0 1 3 5 6
// 6 5 3 1 0
// arr[i] > i인 i값들 중 max값을 찾아서 +1하면 됨

​

​6. 위장

unordered_map(hash table)을 쓰면 쉽게 풀 수 있는 문제!

​

​

​

​

남은 문제 아래 8개 정도 있는데... 내일 슥삭 끝내버리자! 주말에는 지금까지 밀린 알고리즘들 증명 및 정리, 유용했던 STL들 정리를 하면 될 것 같고, 다음 주부터는 이제 안 푼 문제 시작하면 될 것 같다!

공부한 지 이제 10일밖에 안됐다! 천천히, 천천히 오래 가자. 전역까지 16개월(...) 남았다. 프로그래머스 lv 2, lv 3 다 푼 다음에는 usaco, 백준(단계별 -> 잘 못푸는 거는 문제 반복해서 돌리기 해서 MCMF까지는 해 보자!), 그 다음에는 프로그래머스 lv4나 codeforce 돌려보자.