23.09.12. 풀었던 문제들

Leetcode 1647. Minimum Deletions to Make Character Frequencies Unique, 30분

첫 접근

 그냥 주는 대로 풀었다.

 일단 각 char이 몇 번 나오는지 알아둬야 하니까 map같은 걸 써야 하는데, 이 문제의 경우 알파벳 소문자만 나오기 때문에 vector(26, 0)을 map처럼 쓰면 된다.

 이후, 내림차순으로 정렬한다.

 정렬한 후, 만약 겹치는 값이 있는 경우에는 해당 값을 1 줄이고, 해당 문을 다시 반복한다. 이 접근이 문제될 때는, 2 2 2와 같은 예시를 보자. 2 2 2에서 index 1이 2 1 2로 바뀐다. index 1에서 같은 값의 비교는 앞의 값만 보기 때문에 pass. index 2에서 앞의 값만 보기 때문에 pass한다. 문제가 생긴다!

 때문에, 바로 앞의 index와 값이 같은지 + 앞의 값보다 값이 크면 1 줄이는 식으로 구현했다.

// Runtime 42 ms Beats 93.66%
// Memory 17.3 MB Beats 77.52%

class Solution {
public:
    int minDeletions(string s) {
        vector<int> f(26, 0); // f[i] : frequency of ith alphabet
        for(char c : s){
            f[c - 'a']++;
        }
        sort(f.begin(), f.end(), greater<int>());

        // f가 겹치는 것들이 있는 경우, 몇 개의 letter를 삭제해 겹치지 않게 바꿔야 함.
        // 내린 값이 겹치지 않게 설정해야 함. 그 중 제일 큰 값으로.
        int answer = 0;
        for(int i = 1; i<f.size(); i++){
            // 만약 겹치는 경우! i번째 char를 줄여야 함.
            if(f[i] == 0) continue;

            if(f[i-1] <= f[i]){
                f[i]--;
                answer++;
                i--;
            }
        }

        // print(f);

        return answer;
    }
};

 

시간복잡도

 frequency를 세는 데 O(n)

 정렬에 O(nlogn)

 이후 메인 로직인 for문에서 어떻게 시간이 걸릴 지 모르겠다. 그러나 worst case는 [모든 숫자가 똑같을 때] worst case이며, 이 경우에 25 * 26 / 2만큼 실행된다. (앞의 것과 비교하고, 만약 더 크면 1을 내리기 때문)

 그러나 이렇게 해도, 입력 문자가 26이기 때문에 충분히 풀린다.

 

 

두 번째 접근

 for loop로 돌리니까 뭔가 직관성이 떨어진다. for loop 대신 pq를 쓰는 방법도 있다.

 세 번째 로직만 조금 바뀌는데, pq의 top t를 뽑고, 이후의 pq.top()과 같은 경우는 pq.top()을 줄여야 한다. t를 1 줄이고 pq에 다시 넣는다. 만약 t와 pq.top()이 다른 경우에는 그냥 빼버리면 된다.

 이 경우를 pq.size() == 1이 될 때까지 반복한다. pq.size()가 1인 경우는 무조건 identical한 값이 튀어나오기 때문이다.

// Runtime 49 ms Beats 79.99%
// Memory 17.3 MB Beats 58%

class Solution {
public:
    int minDeletions(string s) {
        vector<int> f(26, 0); // f[i] : frequency of ith alphabet
        for(char c : s){
            f[c - 'a']++;
        }

        priority_queue<int, vector<int>, less<int>> pq;

        for(int e : f){
            pq.push(e);
        }

        int answer = 0;
        while(!pq.empty()){
            int t = pq.top(); pq.pop();
            if(t == 0 || pq.size() == 0) break;
            if(t > 0 && pq.top() == t){
                answer++;
                pq.push(t-1);
            }
        }

        return answer;
    }
};

 

시간복잡도

 pq를 써서 시간복잡도가 개선될 것 같지만, -- 연산의 회수는 동일하다. 그러나 pq의 push, pop 연산에서 logn을 추가로 소모하기 때문에 더 많은 시간이 걸린다! 아마 26log26쯤 더 걸리지 않을까 싶다.

 

 

 

Programmers Lv. 3 최고의 집합, 4분

 중앙값을 택하는 게 곱이 제일 커진다. 뭐... 고등학교 수학을 배운 이과라면 다들 아는 내용.

vector<int> solution(int n, int s) {
    // 만들 수 없는 경우 : 
    if(n > s) return {-1};
    
    // 중앙값일 때 곱이 최대
    int q = s/n;
    vector<int> answer(n, q);
    int diff = s % n;
    // answer 배열의 뒤에서부터 diff개에 1씩 더해주면 됨
    for(int i = n-1, cnt = 1; cnt <= diff; i--, cnt++){
        answer[i]++;
    }
    
    return answer;
}

 

시간복잡도

 n size 배열을 만들고 s%n만큼 순회한다. 배열 만들 때 O(n), 순회할 때 worst O(n)이다.

 

 

 

Programmers Lv. 3 야근 지수, 3분 30초

 pq를 사용할 줄 안다면 바로 풀리는 문제. n이 1,000,000으로 1백만인데, O(nlogn) 알고리즘은 5백만까지 커버 가능하다!

 2$^{10}$이 1000정도로 잡으면, 2$^{20}$이 1,000,000이다. 1,000,000에 20을 곱해봤자 2천만 정도로, 백만 정도는 O(nlogn)으로 풀린다!

 앞 문제와 마찬가지로, 제일 큰 값을 1 줄이는 게 야근 지수를 제일 많이 줄일 수 있다. 이를 위해 제일 큰 값을 항상 뽑아와야 하는데, 그러면 pq가 생각난다!

typedef long long ll;

long long solution(int n, vector<int> works) {
    priority_queue<int, vector<int>, less<int>> pq;
    for(int work : works) pq.push(work);
    
    while(1){
        if(n == 0 || pq.empty()) break;
        int t = pq.top(); pq.pop();
        if(t != 1) pq.push(t-1);
        n--;
    }
    
    long long answer = 0;
    while(!pq.empty()){
        int t = pq.top(); pq.pop();
        answer += (ll) t * (ll) t;
    }
    return answer;
}

 

시간복잡도

 pq의 각 연산은 works size 5만을 w로 두면 O(logw)이다. n은 operation 개수이므로, O(nlogw)이다.

 

 

 

Programmers Lv. 3 단어 변환, 12분 30초

 `최단 거리` -> BFS를 쓰면 된다. 단, 이 문제는 일반적으로 BFS하던 board가 아니라 string으로 하기 때문에 string에 대해 visited를 처리해야 하고, string에 대해 neighbor를 얻어와야 한다. 이건 구현 문제고.. 이것만 잘 처리하면 별 것 없다.

 

 int의 경우에는 vector로 선언해서 쉽게 풀 수 있지만 string의 경우에는 어렵다. 그렇다고 string to integer mapper를 넣기에는 모든 string을 쓰는 부분에 mapper를 call해야 하기 때문에 너무 번거롭다고 생각해 그냥 string을 쓰기로 했다. 이를 위해 map을 사용했는데, map을 쓰면 string을 key로 넣어 visited 여부와 neighbor vector를 쉽게 얻어올 수 있기 때문이었다.

 

 이 부분만 끝내면 뭐.. 나머지는 BFS다.

int len;
map<string, bool> visited; // visited[i] : string i를 사용했는지 여부
map<string, vector<string>> nextMap; // nextMap[i] : i에서 바꿀 수 있는 string vector

struct info{
    string s;
    int dist;  
};

// string a를 b로 바꿀 수 있는지 여부
bool canTransfer(string &a, string &b){
    int cnt = 0;
    for(int i = 0; i < len; i++){
        if(a[i] != b[i]) cnt++;
        if(cnt >= 2) break;
    }
    return cnt == 1;
}

int solution(string begin, string target, vector<string> words) {
    // init
    len = begin.length();
    words.push_back(begin);
    for(string word : words){
        visited[word] = false;
    }
    int wsize = words.size();
    for(int i = 0; i<wsize; i++){
        for(int j = i+1; j<wsize; j++){
            if(canTransfer(words[i], words[j])){
                nextMap[words[i]].push_back(words[j]);
                nextMap[words[j]].push_back(words[i]);
            }
        }
    }
    
    // solve : BFS
    queue<info> q;
    info i; i.s = begin; i.dist = 0;
    q.push(i);
    visited[begin] = true;
    while(!q.empty()){
        string cur_s = q.front().s;
        int cur_d = q.front().dist;
        q.pop();
        if(cur_s == target) return cur_d;
        
        for(string next_s : nextMap[cur_s]){
            if(!visited[next_s]){
                info i; i.s = next_s; i.dist = cur_d + 1;
                q.push(i);
                visited[next_s] = true;
            }
        }
    }
    
    return 0;
}

 

시간복잡도

 BFS 시간복잡도는 O(V+E). V = 50이고, worst case 각 vertex당 E = 50이 될 수 있다. 그래봤자 2500이므로 시간 내에 충분히 끝낼 수 있다.

 

 

 

Programmers Lv. 3 등굣길, 8분 30초

 길찾기 DP 문제. dp[i][j] = dp[i-1][j] + dp[i][j-1]이라는 bottom-up DP로 쉽게 풀 수 있다. 단, 물웅덩이가 있는 곳은 계산하지 않아야 하므로(0으로 두어야 하므로) 이 부분은 set으로 빨리 처리했다. 물론 초기화도 해 주고.

typedef pair<int, int> pii;
int MOD = 1000000007;

int solution(int m, int n, vector<vector<int>> puddles) {
    vector<vector<int>> dp(m, vector<int>(n, 0));
    
    set<pii> puddle_set;
    for(vector<int> puddle : puddles){
        puddle_set.insert({puddle[0]-1, puddle[1]-1});
    }
    
    // init
    for(int r = 0; r<m; r++){
        if(puddle_set.find({r, 0}) != puddle_set.end()) break;
        dp[r][0] = 1;
    }
    for(int c = 0; c<n; c++){
        if(puddle_set.find({0, c}) != puddle_set.end()) break;
        dp[0][c] = 1;
    }
    
    // dp
    for(int r = 1; r<m; r++){
        for(int c = 1; c<n; c++){
            if(puddle_set.find({r, c}) != puddle_set.end()) continue;
            dp[r][c] = (dp[r-1][c] % MOD + dp[r][c-1] % MOD) % MOD;
        }
    }
    
    return dp[m-1][n-1];
}

 

 

 

후기

 뭔가 생각과 타이핑의 속도가 엄청나게 빨라진 것 같다. 그만큼 안 덤벙거리게 잘 해야 겠다. 특히 마지막 문제도.. 로직은 다 맞았는데 % 연산을 까먹었다. 구현 자체는 안 덤벙대서 다행이다. 근데 이건 머릿속에 좌르르 흘러가는 느낌이 든다.!!! 물론 복잡한 문제도 아니고... 구현이 복잡한 문제를 30분컷 내야 하는데. 끄악