23.03.06. 풀었던 문제들

Leetcode 1539. Kth Missing Positive Number

 증가수열 arr과 숫자 k가 주어질 때 arr에 있지 않은 k번째 배열을 찾는 문제. O(n)으로 풀면 바로 풀린다.

 

O(n) solution

// Runtime 6 ms Beats 53.33%
// Memory 9.7 MB Beats 38.5%

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        vector<int> missings;
        int num = 1, arridx = 0;
        while(1){
            if(arridx < arr.size() && num == arr[arridx]){ // not missing
                num++;
                arridx++;
            }
            else{ // missing
                k--;
                if(k <= 0) break;
                num++;
            }
        }
        return num;
    }
};

 위 코드와 같이 앞에서부터 시뮬레이션 해 가면 쉽게 풀린다.

 

O(logn) solution

 그러나 이 문제는 이게 본 문제가 아니다. O(logn)으로 푸는 게 진짜인 문제. 이딴 게 easy..? binary search를 써야 하는 건 알겠는데 어떻게 써야 할지 감도 오지 않았다.

 어떤 수 n이 몇 번째 missing 숫자인지 찾는 것은 쉽다. n - index이며 이 때 index는 array에서 n의 upper bound이다. index가 n의 upper bound일 때 n - ub(n) = k인 n을 찾아야 했다. 이렇게 풀면 n을 조작해야 하기 때문에 O(logn)으로 풀 수 없다. 잘못된 접근.

 

 한참을 고민하다 solution을 봤다.

 arr[i] - i - 1은 arr[i] 이전에 오는 missing element 개수이다. 이건 당연히 쉽게 나오는 게, 문제 정의기 때문이다. arr[i]까지는 arr[i]개의 숫자가 있고, arr[i]의 index인 i는 존재하는 element이다. 따라서 arr[i] - i - 1은 arr[i] 이전에 오는 missing element 개수이다.

예를 들어
2, 3, 4, 7, 11인 경우
1, 1, 1, 3, 6이다.

 

 이 식을 이용해서 문제에 접근한다. 이 정보를 이용해서 어떤 element가 missing인지 알 수 있나? 우리는 k번째 missing element를 찾고 싶고, missing element 개수의 increasing array를 가지고 있다. (arr[i] - i - 1)

• lower bound로 이 i를 찾았다고 하자. k의 lower bound이기 때문에 arr[i] - i - 1 >= k이다. 또한, arr[i - 1] - i < k이다.
  • upper bound 하면 missing element 개수가 k일 때 찾지 못하므로 lower bound를 쓴다.
• arr[i-1] - i < k <= arr[i] - i - 1이고, arr[i-1] <= k < arr[i]이다.
  • 이 때 arr[i-1]은 missing value가 아니므로 arr[i-1] < k < arr[i]이다.
• arr[i-1] 이전에 오는 missing element 개수 = arr[i-1] - i개이다.
• arr[i-1]부터 k번째 missing value까지 k - arr[i-1] + i개이다.
• 따라서 k번째 missing vlaue = arr[i-1] + k - arr[i-1] + i = k + i이다.

 그러면 arr[i] - i - 1의 lower bound만 찾으면 된다. 새로운 배열을 만들면 O(n)이고, 굳이 새로운 배열도 만들 필요 없다. arr[i] - i - 1도 monotonic increasing되어있기 때문.

// Runtime 4 ms Beats 73.18%
// Memory 9.5 MB Beats 94.95%

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int start = 0, end = arr.size();
        while(start < end){
            int mid = (start + end) / 2;
            if(arr[mid] - mid - 1 >= k){ // k가 더 작으므로 앞쪽을 탐색해야 함
                end = mid;
            }
            else start = mid + 1;
        }
        return end + k;
    }
};

 

시간복잡도

 binary search이므로 O(n)

 

공간복잡도

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

 

후기

 대체 이런 걸 어떻게 생각해 내는거지..? bsearch인 걸 알아도 접근할 수가 없다... arr[i] - i - 1가 arr[i] 이전에 오는 missing element 개수임을 알아도 한 단계 접근이 더 필요했다.

 

 

 

프로그래머스 부대 복귀

 전형적인 BFS 문제. 시작점으로부터 찾을 생각 하지 말고 끝에서부터 거리를 찾으면 된다.

 이 문제의 경우

• edge weight가 1이므로 BFS가 적합하다.
• BFS의 경우 dist 값 갱신은 q에 넣는 순간에 하면 된다.
• 탐색 시 unvisited로만 간다.

만 조심해 주면 된다.

int UNVISITED = -1;

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    // initialize
    vector<int> dist(n + 1, UNVISITED);
    map<int, vector<int>> edges; // edges[i] : i를 출발점으로 하는 edge
    for(vector<int> road : roads){
        edges[road[0]].push_back(road[1]);
        edges[road[1]].push_back(road[0]);
    }
    
    // BFS init
    queue<int> q;
    q.push(destination);
    dist[destination] = 0; // dist 초기화는 q에 넣는 순간
    
    // BFS
    while(!q.empty()){
        int cur = q.front(); q.pop();
        for(int next : edges[cur]){
            if(dist[next] == UNVISITED){
                dist[next] = dist[cur] + 1;
                q.push(next);
            }
        }
    }
    
    // get answer
    vector<int> answer;
    for(int s : sources){
        answer.push_back(dist[s]);
    }
    return answer;
}


// weight가 1이니까, BFS가 적절할 것 같다.
// destination부터 탐색

 

시간복잡도

 BFS이므로 O(V + E), V = 10만, E = 50만이므로 시간제한 내에 풀린다.

 

 

 

프로그래머스 인사고과

 정렬에 대해 잘 알고 있어야 하는 문제. 트릭trick이 하나 있다.

 먼저 strictly 더 작은 element는 무조건 삭제해야 한다. 예를 들어 [[4, 1], [2, 4], [3, 5]]와 같은 예외가 있을 수 있기 때문이다. [2, 4]는 [4, 1]보다 점수가 더 높지만 [3, 5]보다 strictly 더 작아서 없어져야 하고, 그러면 등수가 바뀐다.

 이제 이걸 어떻게 삭제하느냐? 생각보다 간단한 트릭이 있다. 두 점수를 [a, b]라고 하면

• a는 내림차순 정렬, b는 오름차순 정렬 한다.
  • 따라서 arr[i].a >= arr[i+1].a는 보장된다.
• 이 때 arr[i].b > arr[i+1].b라면 a의 값이 바뀌었다는 뜻. 즉슨 arr[i].a > arr[i+1].a이다.
  • 문제 조건에 따라서 strictly 더 작다. 해당 원소는 pass.
• 따라서 이전 element의 b 값을 저장해 두고, 앞에서부터 순회한다.
  • 탐색한 element.b가 더 작은 경우 -> 해당 원소는 strictly 더 작다. pass
  • 그렇지 않은 경우 -> element b 값을 저장해 둔다.

 이 트릭이 말도 안됐다.

 

 참고로 조건이 3개인 경우는 seg tree를 써야 한다고 한다.

예시)
3, 1
3, 2
2, 1
2, 2
1, 4

bool cmp1(vector<int> &a, vector<int>& b){ // a[0] 내림차순, b[0] 내림차순
    if(a[0] == b[0]){
        return a[1] < b[1];
    }
    return a[0] > b[0];
}

bool cmp2(vector<int> &a, vector<int> &b){
    if(a[0] + a[1] == b[0] + b[1]){
        return a[0] > b[0];
    }
    if(a[0] + a[1] > b[0] + b[1]) return true;
    else return false;
}

int solution(vector<vector<int>> scores) {
    vector<int> target = scores[0];
    
    // 1차 : 못 받는 애들 다 자름
    sort(scores.begin(), scores.end(), cmp1);
    // first는 내림차순, second는 오름차순.
    // a, b가 있을 때 a.first > b.first는 보장됨
    // a.second > b.second면 둘 다 작은 거임. 그건 pass
    vector<vector<int>> sieve;
    int prevSecond = scores[0][1];
    for(int i = 0; i<scores.size(); i++){
        if(prevSecond > scores[i][1]){
            if(target[0] == scores[i][0] && target[1] == scores[i][1]) return -1;
            continue;
        }
        else{
            prevSecond = scores[i][1];
            sieve.push_back(scores[i]);
        }
    }
    
    // 2차 : 등수 매김
    sort(sieve.begin(), sieve.end(), cmp2);
    for(int i = 0; i<sieve.size(); i++){
        if(sieve[i][0] + sieve[i][1] == target[0] + target[1]) return i+1;
    }
    

    return -1;
}

 

시간복잡도

 sort는 O(nlogn), 순회는 O(n)이므로 O(nlogn)이다.

 

후기

 죽고싶다. 인센 못 받는 애들을 다 잘라야 하는 건 알고 있었는데 어떻게 자를지 감도 못 잡고 있어서 solution을 봤다. 자괴감들고 괴로워...

 그리고 2차로 등수 매길 때도 [현 등수, 해당 등수에 몇 명이 있는지] 이렇게 쓰고 for문으로 순회했는데 그럴 필요가 없다.동석차의 수만큼 건너뛴다는 건, 등수가 바뀐 순간에는 무조건 i+1등이라는 거다. 그래서 [완호의 점수 == 현재 탐색 중인 사람 점수 합]이 되는 순간에 i+1을 리턴하면 그게 답이다.