23.04.04. 풀었던 문제들

Leetcode 2405. Optimal Partition of String

첫 접근

 greedy로 풀었다. 어떤 index i를 탐색할 때, 지금까지 본 char가 아니라면 지금 string에 push, 한 번이라도 봤던 char라면 다음 string에 push하는 방법이다. 만약 이게 optimal이 아니라면 string의 길이가 더 길어져야 한다는 것인데, 그렇다면 한 string에서 모든 char가 unique하지 않게 되므로 모순. 따라서 optimal이다.

// Runtime 325 ms Beats 5.4%
// Memory 88 MB Beats 8.67%

class Solution {
public:
    int partitionString(string s) {
        int answer = 0, i = 0, len = s.length();

        while(i < len){
            unordered_map<char, int> um;
            while(i < len && um.find(s[i]) == um.end()){
                um[s[i]] = 1;
                i++;
            }
            answer++;
        }

        return answer;
    }
};

 

시간복잡도

 map에 접근할 때 O(1), worst case while문이 n번 loop하므로 O(n).

 

공간복잡도

 worst case n번의 loop에 대해 um을 생성하므로 O(n).

 

 

두 번째 접근

 solution을 보고 알게 된 것. 위와 같은 로직으로 two pointer를 이용해 풀 수 있다. 하나는 [현재 substring의 시작 index], curSubstrIdx로 표기하겠다. 하나는 s를 순회하는 i이다. 여기에 추가로 [어떤 char이 마지막에 등장했던 위치를 저장하는 배열] lastCharIdx로 표기하겠다. 그러면 아래의 로직을 통해 3개의 변수로 답을 낼 수 있다.

• 모든 s를 순회하면서 s[i]가 마지막에 등장했던 위치인 lastCharIdx[s[i]]가 curSubstrIdx보다 크거나 같다면 현재 substring에 s[i]가 존재하는 것이다. 따라서, i를 새로운 substring의 시작으로 표기한다.
• 이후 lastCharIdx[s[i]]를 i로 갱신한다.

// Runtime 23 ms Beats 90.1%
// Memory 10.2 MB Beats 98.68%

class Solution {
public:
    int partitionString(string s) {
        int answer = 1, len = s.length(), curSubstrIdx = 0;
        vector<int> lastCharIdx(26, -1);

        for(int i = 0; i<len; i++){
            if(lastCharIdx[s[i] - 'a'] >= curSubstrIdx){
                answer++;
                curSubstrIdx = i;
            }
            lastCharIdx[s[i] - 'a'] = i;
        }

        return answer;
    }
};

 

시간복잡도

 for loop로 순회만 하므로 O(n)이다.

 

공간복잡도

 추가 공간을 사용하긴 하지만 변수 29개만 사용한다. 따라서 O(1).