23.03.10. 풀었던 문제들

Leetcode 382. Linked List Random Node

 어떤 singly linked list의 head가 주어졌을 때 모든 index를 같은 확률로 리턴하는 함수를 만드는 문제이다.

 

첫 접근 : 1번의 순회, O(n) 공간

 별다른 제약이 없는 초기 조건에서 아래와 같이 작성했다. linked list의 전체 node를 vector에 넣고 rand() v.size() index를 리턴한다.

class Solution {
public:
    vector<ListNode*> v;
    Solution(ListNode* head) {
        while(head != NULL){
            v.push_back(head);
            head = head->next;
        }
    }
    
    // 추가 공간을 사용해서 rand() index 리턴
    int getRandom() {
        return v[rand() % v.size()]->val;
    }
};

 

 follow up으로 space complexity O(1)로 효율적인 알고리즘을 만들라고 제시한다.

 

2번의 순회, O(1) 공간

 O(1)의 space complexity를 사용한다면 linked list를 처음부터 순회해 size를 알아내고, 또 한번의 순회로 rand() % size만큼의 index만큼 전진한다.

class Solution {
public:
    int size = 1;
    ListNode* h;
    Solution(ListNode* head) {
        this->h = head;
        while(head->next != NULL){ // head는 linked list의 마지막
            head = head->next;
            this->size++;
        }
        head->next = this->h;
    }
    
    int getRandom() {
        int random = rand() % (this->size);
        while(random--){
            this->h = h->next;
        }
        return this->h->val;
    }
};

 

 그러나 solution에는 1번의 순회로 탐색할 수 있는 reservoir sampling을 제시한다. 게시글에 작성했다.

 

1번의 순회, O(1) 공간

 reservoir sampling으로 단 1번의 순회로 풀 수 있다.

// Runtime 15 ms Beats 97.69%
// Memory 16.6 MB Beats 57.94%

class Solution {
public:
    ListNode* h;
    Solution(ListNode* head) {
        this->h = head;
    }
    
    int getRandom() {
        ListNode* cur = this->h;
        int curval;
        int count = 1;
        while(cur){
            if(rand() % count == 0){
                curval = cur->val;
            }
            cur = cur->next;
            count++;
        }
        return curval;        
    }
};

 

 단 1번 순회하기 때문에 2번 순회하는 알고리즘보다 시간도 조금 올라간 것을 볼 수 있다.

 

후기

 재밌는 접근이었다. 물론 reservoir sampling은 solution을 보고 안 것이긴 하지만...

 

 

프로그래머스 억억단을 외우자

 1부터 5백만의 숫자가 억억단에서 몇 번 등장하는지 구하는 문제. 몇 번 등장하는지만 알고 있다면 나머지는 순서대로 sweeping을 통해 풀 수 있다. n이 5백만이기 때문에 조금 효율적인 알고리즘이 필요하다.

 

 문제를 잘 살펴보면 어떤 숫자 k는 k의 약수번 등장한다는 것을 알 수 있다. 예를 들어 k가 8이라면 1단에서 8, 2단에서 4, 4단에서 2, 8단에서 1 이렇게 4번 - k의 약수번 등장한다. 따라서 1부터 5백만까지 약수의 개수를 알 수 있어야 한다.

 

 단순히 한 숫자의 약수만 구하면 O($n^{0.5}$)의 시간이 걸린다. 그러나 에라토스테네스의 체를 조금 변형한다면 모든 수의 약수의 개수를 O(nlogn)에 구할 수 있다.

 

 에라토스테네스의 체는

• 만약 탐색했던 숫자라면 탐색하지 않고
• 탐색하지 않은 숫자라면 해당 숫자를 소수로 표기한다.
  • 동시에 그 수의 배수를 모두 소수가 아니라고 표현한다.
  • 변형해야 하는 부분은 이 부분이다.

 

 모든 수에 대해 그 수의 모든 배수에 count를 1 더해버린다면 그 수의 모든 약수의 개수만큼 count가 나올 것이다.

 

 이 경우 시간복잡도는 O(nlogn)이다. 2일 때는 전체 n 중 1/2개에 대해 count++ 연산을, 3일 때는 n개 중 1/3에 대해 count++연산을, ... , n일 때는 n 중 n/n개에 대해 count++ 연산을 한다. 이 때 (1/2 + 1/3 + ... + 1/n) = logn이기 때문에 nlogn의 시간이 나온다.

 

 다음으로 sweeping은 O(n), 또는 O(nlogn)으로 풀 수 있다.

 

 

O(nlogn) sweeping

 내가 처음으로 푼 코드다. 

typedef pair<int, int> pii; // .first : starts의 index / .second : starts[i]의 값
bool cmp(pii &a, pii &b){
    return a.second > b.second; // 내림차순 정렬
}

vector<int> solution(int e, vector<int> starts) {
    vector<int> counts(e+1, 1);
    // counts[i].first : 숫자 i
    // counts[i].second : number i가 억억단에서 나온 회수 = 약수 개수 
    
    // 모든 숫자에 대해 그 수의 약수 개수를 구함
    // [1/2 + 1/3 + 1/4 + ... + 1/n] * n = nlogn
    for(int i = 2; i<=e; i++){
        for(int j = i; j<=e; j += i){
            counts[j]++;
        }
    }
    
    vector<pii> startWithIndex(starts.size());
    for(int i = 0; i<starts.size(); i++){
        startWithIndex[i] = {i, starts[i]};
    }
    sort(startWithIndex.begin(), startWithIndex.end(), cmp);
    
    // 정답 넣기
    vector<int> answer(starts.size());
    int sidx, i = e; // sidx : starts의 순회 index / i : 숫자 iterator
    pii maxValue = {counts[e], e}; // .first : 숫자 개수, e
    for(sidx = 0; sidx<starts.size(); sidx++){
        for(; i >= startWithIndex[sidx].second; i--){
            if(counts[i] >= maxValue.first){
                maxValue = {counts[i], i};
            }
        }
        answer[startWithIndex[sidx].first] = maxValue.second;
    }
    // startWithIndex : 내림차순 되어있음


    return answer;
}

 starts 배열을 [starts index, starts[i]]로 표현하고 starts[i]로 내림차순 정렬한다. 시간복잡도는 O(nlogn)이다. 이후 e부터 내림차순 순회하면서 starts[i]와 같은 sidx가 발견되면 그 값을 answer에 넣는다.

 

 

O(n) sweeping

 그러나 이렇게 풀 필요 없다. 굳이 복잡하게 sort할 필요도 없고. 다음 코드를 보자.

vector<int> solution(int e, vector<int> starts) {
    vector<int> counts(e+1, 1);
    // counts[i].first : 숫자 i
    // counts[i].second : number i가 억억단에서 나온 회수 = 약수 개수 
    
    // 모든 숫자에 대해 그 수의 약수 개수를 구함
    // [1/2 + 1/3 + 1/4 + ... + 1/n] * n = nlogn
    for(int i = 2; i<=e; i++){
        for(int j = i; j<=e; j += i){
            counts[j]++;
        }
    }
    
    vector<int> answer(starts.size()), largestCounts(e+1);
    largestCounts[e] = e;
    // answer : 정답 배열, largestCounts[i] : e부터 i까지 제일 많이 등장하는 수
    for(int i = e-1; i>=1; i--){
        if(counts[i] < counts[i+1]){
            counts[i] = counts[i+1];
            largestCounts[i] = largestCounts[i+1];
        }
        else largestCounts[i] = i;
    }
    
    for(int i = 0; i<starts.size(); i++){
        answer[i] = largestCounts[starts[i]];
    }

    
    return answer;
}

 새로운 array largestCounts를 하나 선언한다. 이 array는 e부터 i까지 제일 많이 나온 숫자를 저장한다.

 그러면 counts 배열을 순회하면서 만약 counts[i] < counts[i+1]이라면 i번째 숫자가 나온 회수 i+1번째 숫자가 나온 회수보다 작으므로 largestCounts[i] 값을 largestCounts[i+1]의 값으로 설정한다. counts 배열도 동일하게 설정하는데, 4 2 9와 같이 줄었다가 늘어나는 경우가 있기 때문이다.

 이렇게 sweeping을 해 버리면 largestCounts[i]는 e부터 i까지 제일 많이 나온 숫자를 저장할 수 있다. 그러면 start 배열을 순회하며 largestCount 배열에서 값을 가져와 버리면 그만이다.

 

 

시간복잡도

 O(nlogn)

 

 

후기

 문제 알고리즘 잘 접근한 문제. 다만 아쉬운 점이 있다면 sweeping을 O(nlogn)으로 한 점 ?