23.03.04. 풀었던 문제들

프로그래머스 디펜스 게임

 앞에서부터 priority queue를 써서 제일 큰 값을 줄여가면 되는 문제. 단순 구현이다.

typedef long long ll;
int solution(int n, int k, vector<int> enemy) {
    priority_queue<ll> pq;
    int i = 0;
    ll sum = 0;
    
    while(1){
        if(i < enemy.size()){
            if(n >= sum + enemy[i]){ // 이번 wave 감당 가능하면 넣음
                sum += enemy[i];
                pq.push(enemy[i]);
                i++;
            }
            else if(k > 0){ // 이번 wave 감당 불가면 무적건 써야 함. 없으면 불가
                sum += enemy[i];
                pq.push(enemy[i]);
                i++;
                k--;
                sum -= pq.top();
                pq.pop();    
            }
            else break;
        }
        else break;
    }
    
    return i;
}

 

시간복잡도

 전체 array를 순회하고, pq를 쓰므로 O(nlogn)

 

 

프로그래머스 시소 짝꿍

 상당히 귀찮은 문제. 처음에는 lower_bound로 구할려 했는데 이러면 내가 원하는 값이 있는지 없는지가 아니라 그거보다 큰 값이 나온다. 그리고 indexing도 귀찮고. 그래서 map을 쓰는 게 좋다.

• map에 무게가 i인 사람 명수를 저장한다.
• weights를 순회하면서 해당 몸무게를 가진 사람과 짝궁이 될 수 있는 후보군을 추린다.
  • setAbles 함수를 사용한다. 만약 % 결과가 0이라면 해당 몸무게는 존재한다(정수값이니까) 그렇지 않으면 존재하지 않음.
  • 그 후보군의 무게 명수를 answer에 더한다. 단, 후보군 무게 == 현재 탐색중인 사람 몸무게인 경우에는 그 사람을 빼야 하므로 -1을 한다.
• answer / 2를 리턴한다.(중복되는 경우의 수가 있기 때문)

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
 
using namespace std;
 
map<int, int> m; // m[i] : 무게가 i인 사람 명수
 
// w에 해당하는 배율이 가능한 위치 찾음
typedef pair<int, int> pii;
vector<pii> positions;
vector<int> ables(7);
void setAbles(int w){
    for(int i = 0; i<positions.size(); i++){
        int left = positions[i].first * w;
        if(left % positions[i].second){
            ables[i] = -1;
        }
        else{
            ables[i] = left / positions[i].second;
        }
    }
}
 
long long solution(vector<int> weights) {
    positions =  {{2, 2}, {2, 3}, {2, 4}, {3, 2}, {3, 4}, {4, 2}, {4, 3}};
    for(int w : weights){
        if(m.find(w) == m.end()) m[w] = 1;
        else m[w]++;
    }
    
    long long answer = 0;
    for(int i : weights){
        setAbles(i);
        for(int a : ables){
            if(a == -1) continue;
            if(m.find(a) != m.end()){
                answer += m[a] - (a == i);
            }
        }
    }
    
    return answer/2;
}

 

시간복잡도

 map insert, search는 O(logn). for문은 O(n). O(nlogn)이다.

 

 

프로그래머스 미로 탈출

 간단한 BFS 문제. 항상 그렇듯 BFS에서 visited는 q에 넣는 순간이다. 그리고 좌표평면에서 탐색할 때는 dr[4], dc[4]를 쓰자. 편하다.

 문제는 [시작점 - 레버], [레버 - 도착점]의 최단거리를 찾는 것이다. 좌표평면에서 최단거리 탐색이기 때문에 BFS를 사용하면 된다.

int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
bool visited[101][101];
vector<string> Maps;
int maxr, maxc;
struct Search{
    int r, c, dist = 0;  
};
 
void initVisited(){
    for(int r = 0; r<maxr; r++){
        for(int c = 0; c<maxc; c++){
            visited[r][c] = false;
        }
    }
}
 
int BFS(Search start, Search end){
    queue<Search> q;
    q.push(start);
    visited[start.r][start.c] = true;
    
    while(!q.empty()){
        Search cur = q.front(); q.pop();
        int cr = cur.r, cc = cur.c, cd = cur.dist;
        if(cr == end.r && cc == end.c) return cd;
        for(int i = 0; i<4; i++){
            int nr = cr + dr[i], nc = cc + dc[i];
            if(0 <= nr && nr < maxr && 0 <= nc && nc < maxc && !visited[nr][nc] && Maps[nr][nc] != 'X'){
                Search next; next.r = nr; next.c = nc; next.dist = cd + 1;
                visited[nr][nc] = true;
                q.push(next);
            }
        }
    }
    return -1;
}
 
int solution(vector<string> maps) {
    Maps = maps;
    maxr = maps.size(); maxc = maps[0].size();
    
    Search start, lever, exit;
    for(int r = 0; r < maxr; r++){
        for(int c = 0; c<maxc; c++){
            if(maps[r][c] == 'S'){
                start.r = r; start.c = c;
            }
            else if(maps[r][c] == 'E'){
                exit.r = r; exit.c = c;
            }
            else if(maps[r][c] == 'L'){
                lever.r = r; lever.c = c;
            }
        }
    }
    
    initVisited();
    int start2lever = BFS(start, lever);
    
    initVisited();
    int lever2exit = BFS(lever, exit);
    
    if(start2lever == -1 || lever2exit == -1) return -1;
    
    return start2lever + lever2exit;
}

 

시간복잡도

 BFS는 O(V + E)인데 E = 4V이므로 O(V)

 

 

Leetcode 2444. Count Subarrays With Fixed Bounds

 첫 접근은 [범위 밖에 나가는 것들을 다 빼고 생각하자] 였다. 그러나 이렇게 해도 [1, 1, 1, 1]과 같은 경우를 처리하기 힘들었다. 어찌저찌 two-pointer 같다는 생각은 했으나... 잘 모르겠어서 solution을 봤다. 처음에는 보고도 "대체 왜 이게 답임" 이 생각을 했다.

 조금 풀어서 보자. 앞에서부터 순회한다고 생각하자.

 

 일단 nums[i]가 maxK보다 크거나, nums[i]가 minK보다 작다면 i는 무조건 subarray에 속하지 않는다. 이건 문제 조건에 의해 이렇게 될 수 밖에 없다. i+1부터 subarray를 만든다고 가정하자. 이 때 index를 start라고 하자.

 

 그러면 나머지 경우는 어떨까? minK <= nums[i] <= maxK인 경우. 이 때 array는 무조건 start+1부터 시작일 것이다.

• minK, maxK가 둘 중 하나라도 발견되지 않은 경우, subarray가 만들어지지 않으므로 더 탐색해야 한다.
• minK, maxK가 발견되어 있는 경우
  • 새로 들어온 수(nums[i])가 minK 또는 maxK인 경우 : 이 경우 새로운 subarray를 구성할 수 있다.
    • nums[i]가 minK인 경우, 원래 maxK부터 nums[i]까지가 subarray를 구성한다.
      • start | start + 1 , ... , [lastMax, ... , i]
      • 괄호 친 부분이 꼭 들어가야 하는 subarray이고, 괄호 왼쪽부터 start + 1까지 넣을 수 있다. 연속되어야 하므로 lastMax- start이다.
    • nums[i]가 maxK인 경우, 원래 minK부터 nums[i]까지 subarray를 구성한다.
      • start | start + 1 , ... , [lastMin, ... i]
      • 괄호 친 부분이 꼭 들어가야 하는 subarray이고, 괄호 왼쪽부터 start + 1까지 넣을 수 있다. 연속되어야 하므로 lastMin- start이다.
  • 새로 들어온 수가 minK < nums[i] < maxK인 경우
    • start | start + 1 , ... , [[minK와 maxK가 있는 subarray], nums[i]]
    • 위와 같이 표현할 수 있다. 이미 minK와 maxK가 발견되어 있기 때문에 원래 subarray에 nums[i]를 포함시킨다. 이 때, min(lastMin, lastMax) - start값을 더해야 한다.
      • 예를 들어 2 1 3 5 2, minK = 1, maxK = 5라 하자.
      • 2 1 3 5가 탐색된 상황에서 2를 추가로 탐색했다. 이 때 [minK와 maxK가 있는 subarray]는 [1 3 5]이다.
      • 따라서 2 [1 3 5]로 표현할 수 있다.
      • 이 때 2를 추가로 탐색했는데, 이를 [minK와 maxK가 있는 subarray]에 포함하고 그 앞에 있는 element를 순차적으로 포함해야 한다.
      • 2 [1 3 5 2] , 그리고 [2 1 3 5 2] 이렇게.
  • 간단하게 표현할 수 있다. nums[i]가 minK인 경우 lastMin를 i로 갱신하고, nums[i]가 maxK인 경우 lastMax를 i로 갱신한다.
  • lastMin과 lastMax가 둘 다 있는 상황이라면 min(lastMin, lastMax) - start를 한다. 이는 [minK와 maxK가 있는 subarray의 제일 앞의 index] - start를 의미한다.

 

 위와 같은 pseudo code로 표현할 수 있다. 코드로 나타내면 아-주 간단하다.

// Runtime 114 ms Beats 84.8%
// Memory 70.4 MB Beats 57.55%
 
class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        long long answer = 0;
        int lastMax = -1, lastMin = -1, n = nums.size(), start = -1;
        for(int i = 0; i<n; i++){
            if(nums[i] > maxK || nums[i] < minK){
                start = i;
                lastMax = -1; // not found
                lastMin = -1; // not found
            }
            else{
                if(nums[i] == minK) lastMin = i;
                if(nums[i] == maxK) lastMax = i;
 
                if(lastMin != -1 && lastMax != -1){
                    answer += min(lastMax, lastMin) - start;
                }
            }
        }
        return answer;
    }
};

 

 솔직히 면접에서 이거 물어보면 GG다. 좋은 경험 했다고 생각하자... i번째 index가 array에 추가되었을 때 몇 개의 추가 array가 생기는지를 고민해 보았으면 쉽게 풀렸을 것 같다. ㅠㅠ

 

 

시간복잡도

 앞에서부터 뒤로 순회만 하니 O(n)이다.

 

공간복잡도

 추가 공간을 사용하지 않으니 O(1)이다.