22.03.30. 풀었던 문제들

1. 구명보트

greedy / two-pointer느낌도 난다. vector를 정렬해서 max값 + min값이 limit보다 크면 둘다 보트에 태우고, 그렇지 않다면 max값만 보트에 태우면 된다.

​

​

2. 삼각 달팽이

규칙 찾기 + 구현 문제다.

​

​

3. 주식가격

pq를 잘 이용해 보는 문제였다. -> 같은 방법으로 stack으로도 풀린다...

prices를 앞에서부터 하나씩 pq에 넣는다. (pq의 top은 넣은 값 중 최댓값이 올라오게 한다)

prices[i] < pq.top()이라면 가격이 떨어졌다는 것 -> 이에 따른 처리를 해 주면 된다. prices[i] >= pq.top()이 될 때 까지 pq.pop()을 해 주고, pq.top()에 있는 것의 index와 prices[i]와의 index 차이를 계산해 주면 될 것이다.

prices[i] >= pq.top()이라면 가격이 떨어지지 않았다는 것이므로 바로 push한다.

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

using namespace std;

typedef pair<int, int> pii;

vector<int> solution(vector<int> prices) {
    priority_queue<pii, vector<pii>, less<pii>> pq; // {price, idx}
    
    int size =prices.size();
    pii temp;
    vector<int> answer(size, 0);
    for(int i = 0; i<size; i++){
        /*if(pq.empty() || pq.top().first <= prices[i]){
            pq.push({prices[i], i});
        } else{
            while(!pq.empty() && pq.top().first > prices[i]){
                temp = pq.top();
                answer[temp.second] = i - temp.second;
                pq.pop();
            }
            pq.push({prices[i], i});
        }*/
        // 위 주석친 코드를 아래와 같이 간단히 바꿀 수 있다.
        // 어차피 if-else에 상관없이 pq에 값은 push하고, 조건에 따라 while문을 돌기 때문이다.
        
        while(!pq.empty() && pq.top().first > prices[i]){
            temp = pq.top();
            answer[temp.second] = i - temp.second;
            pq.pop();
        }
        pq.push({prices[i], i});
    }
    
    while(!pq.empty()){
        temp = pq.top();
        answer[temp.second] = size - 1 - temp.second;
        pq.pop();
    }
 
    return answer;
}

/*

앞에서부터 하나씩 pq에 넣음. (pq의 top은 현재 있는 것들 중 최댓값)
prices[i] < pq.top()이라면 가격이 떨어졌다는 것 -> 이에 따른 처리를 해 주면 됨
prices[i] >= pq.top()이라면 가격이 떨어지지 않았다는 것

*/

* 참고로 이 문제는 pq가 아니라 stack으로 푸는 문제다 ! stack.top() > arr[i]라면 stack.top()의 가격이 떨어진 것이므로 이에 해당되지 않을때까지 stack top을 pop하면 된다. 내 코드에서 pq만 stack으로 바꾸면 된다... 뭔가 허망하다 ㅠㅠ

​

​

4. 카펫

O(nlogn)은 최대 500만까지 input을 풀 수 있다. 반면 이 문제의 경우 input이 200만.. 이기도 하고, 약수 구하는 알고리즘은 O(sqrt(n))이다. 기억하자 !

​

​

5. 오픈채팅방

string 관련 문제다. string parsing을 외워버리니까 아주 편하다. + 예전보다 늘었다는 생각이 든다. delimiter가 필요한 버전, 필요없는 버전 둘 다 외우긴 하자. 아마 후자를 자주 쓸 것 같긴 하다...