23.09.11. 풀었던 문제들

Leetcode 1282. Group the People Given the Group Size They Belong To, 30분

 문제 자체는 빨리 풀었는데, 여러 개선을 한다고 시간이 좀 걸렸다.

 

첫 번째 접근

 최대한 생각나는 대로 구현했다.

 groupMap은 특정 size를 가지고 있는 모든 group의 정보를 가지고 있다. 때문에 구현은 단순하다.

1. 입력으로 받은 size의 group이 없는 경우 생성한다.
2. 입력으로 받은 size의 group이 있는 경우,
   1. 해당 group이 존재하지만 아직 size만큼 차지 못하는 경우 - 해당 group에 현재 인원을 넣어준다.
   2. 해당 group이 있고, size만큼 찬 경우 - 새로운 group을 넣어준다.

 

 이렇게 푸니까 runtime 22ms, beats 8.5%가 나왔다.

 시간복잡도로 따지면, 입력 size를 n이라고 하면 O(nlogn)이다. 시간이 상대적으로 느리게 나온 이유는 vector를 계속 추가적으로 할당해서 그런 것 같다.

// Runtime 22 ms Beats 8.50% 
// Memory 15.3 MB Beats 5.29%

class Solution {
public:
    map<int, vector<vector<int>>> groupMap; // groupMap[i] : i명짜리 group
    // i번째 사람을 groupSize 크기의 group에 넣는 함수
    void insertIntoGroup(int i, int groupSize){
        // 아직 해당 size의 group이 없는 경우 - 생성
        if(groupMap.find(groupSize) == groupMap.end()){
            vector<int> newGroup(1, i);
            groupMap[groupSize].push_back(newGroup);
            return;
        }

        // 해당 size의 group이 있는 경우
        // 1. group이 있지만 아직 그만큼 차지 못한 경우
        // 2. 기존에 존재하는 group size가 groupSize여서 새로운 group을 만들어야 하는 경우
        vector<int> &lastGroup = groupMap[groupSize].back();
        
        // case 2
        if(lastGroup.size() == groupSize){
            vector<int> newGroup(1, i);
            groupMap[groupSize].push_back(newGroup);
        }
        // case 1
        else{
            lastGroup.push_back(i);
            // groupMap[groupSize].back().push_back(i);
        }
        
    }
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        int len = groupSizes.size();
        for(int i = 0; i<len; i++){
            insertIntoGroup(i, groupSizes[i]);
        }

        vector<vector<int>> answer;
        for(auto &[groupSize, groups] : groupMap){
            for(vector<int> group : groups){
                answer.push_back(group);
            }
        }
        return answer;
    }
};

 

 

두 번째 접근

 첫 번째 버전을 조금 개선했다. answer vector를 미리 선언해 두고, insertIntoGroup() 함수에서 groupMap을 다루는데, 만약 group이 가득차게 되면 answer에 넣는 방식으로 구현했다. 이렇게 하니 runtime 12ms가 나왔다.

 시간복잡도 자체는 동일하다! 다만 2차원 vector를 1차원으로 줄였고 같은 vector에 계속 접근해 cache쪽에서 성능이 향상된 것이 아닐까 싶다.

// Runtime 12 ms Beats50.27% 
// Memory 13.4 MB Beats 37.1%

class Solution {
public:
    map<int, vector<int>> groupMap; // groupMap[i] : i size짜리 group
    vector<vector<int>> answer;
    // i번째 사람을 groupSize 크기의 group에 넣는 함수
    void insertIntoGroup(int i, int groupSize){
        // 아직 해당 size의 group이 없는 경우 - 생성
        if(groupMap.find(groupSize) == groupMap.end()){
            vector<int> newGroup(0);
            groupMap[groupSize] = newGroup;
        }

        // 해당 size의 group이 있는 경우 - 거기다가 넣음.
        vector<int> &group = groupMap[groupSize]; // groupSize짜리 group
        group.push_back(i);

        if(groupSize == group.size()){
            answer.push_back(group);
            vector<int> newGroup(0);
            group = newGroup;
        }
    }
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        int len = groupSizes.size();
        for(int i = 0; i<len; i++){
            insertIntoGroup(i, groupSizes[i]);
        }
        return answer;
    }
};

 

 

세 번째 접근

 두 번째 접근에서 아이디어를 얻어, 어차피 입력이 정확하다는 것은 보장되므로 groupMap에 모두 다 넣고, 해당 group의 size만큼 파싱하는 방법이다. 이 경우 3ms로 매우 실행시간이 빨라졌는데, 두 번째 접근보다 cache 접근 쪽에서 더 향상된 것이 아닐까 싶다.

// Runtime 3 ms Beats 98.93%
// Memory 13.9 MB Beats 17%

class Solution {
public:
    map<int, vector<int>> groupMap;
    vector<vector<int>> answer;
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        int len = groupSizes.size();
        for(int i = 0; i<len; i++){
            groupMap[groupSizes[i]].push_back(i);
        }

        for(auto &[size, group] : groupMap){
            vector<int> temp;
            int cnt = 0;
            for(int i : group){
                temp.push_back(i);
                cnt++;

                if(cnt == size){
                    answer.push_back(temp);
                    cnt = 0;
                    temp.clear();
                }
            }
        }

        return answer;
    }
};

 

시간복잡도

 입력 size가 n일 때, for loop에 O(n)이고, insertIntoGroupMap()에서 O(logn)이 필요하므로 O(nlogn)이다. 세 번째 접근도 동일한 과정을 거치므로 O(nlogn)이다.

 

 

 

Programmers Lv. 2 Jadencase 문자열 만들기, 12분

 코테 푸는 느낌 내려고 2시간 내에 lv2 문제 1개(1번 느낌으로) + lv3 문제 3-4개 푸려고 한다. 나중에 가면 lv3가 장난 아니게 어려워지니까 천천히 폼 올려서 감당해 보자.

 

첫 접근

 일단 처음에는 딱 보자마자 생각난, delimiter로 string parsing 후 upper/lower 쓰는 방식을 택했다. string parsing은 해당 포스팅 참조.

 단, 이렇게 풀었더니 하나가 틀렸다. 뭐지 뭐지 고민하다가 다음 문제 풀고 다시 돌아왔는데, 이렇게 풀면 맨 마지막에 있는 공백을 처리하지 못한다. 때문에 예외 케이스로 하나 추가해 줬다.

#include <string>
#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

vector<string> split(string s){
    vector<string> result;
    istringstream iss(s);
    string buffer;
    
    while(getline(iss, buffer, ' ')){
        result.push_back(buffer);
    }
    
    return result;
}

string tolower(string s){
    for(char &c : s){
        if(isupper(c)) c = tolower(c);
    }
    return s;
}

string toJadenCase(string s){
    if(islower(s[0])){
        s[0] = toupper(s[0]);
    }
    return s;
}

string solution(string s) {
    vector<string> parsed_string = split(s);
    for(string &s : parsed_string){
        s = tolower(s);
        s = toJadenCase(s);
    }
    
    string answer = "";
    int len = parsed_string.size();
    for(int i = 0; i<len-1; i++){
        answer += parsed_string[i] + " ";
    }
    answer += parsed_string[len-1];
    if(s[s.length()-1] == ' ') answer += " ";
    
    return answer;
}

 

 

두 번째 접근

 그러나 이렇게 풀면 맘에 안들긴 하다. 그래서 다른 풀이를 생각해 냈다.

 단어의 시작은 공백 뒤에 오기 때문에, 뒤에서부터 검색한다. 만약 s[i]가 문자이고 s[i-1]이 공백이면 upper해주면 된다. 나머지는 모두 tolower() 하면 된다. 끝!

#include <string>
#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

string solution(string s) {
    int len = s.length();
    for(int i = len-1; i>=1; i--){
        if(isupper(s[i])) s[i] = tolower(s[i]);
        if(s[i-1] == ' ') s[i] = toupper(s[i]);
    }
    if(islower(s[0])) s[0] = toupper(s[0]);
    return s;
}

 

시간복잡도

 string s.length()를 n이라고 했을 때 처음부터 끝까지 순회만 하므로 O(n)

 

 

 

Programmers Lv. 3 정수 삼각형, 10분

 간단한 DP 문제. 8분만에 풀고 넘겼고, 이후 제출 후 틀려서 다시 풀었다.

 실수했던 점은, edge case는 처리 잘 했는데 일반 case를 처리할 때 for문의 제일 마지막 element가 돌지 않게 설정했음.

for(int i = 1; i<h-1; i++)로 풀었었다.
for(int i = 1; i<=h-1; i++)로 풀어야 한다.

 

#include <string>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int n = triangle.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    dp[0][0] = triangle[0][0];
    for(int h = 1; h<n; h++){ // height
        // 양쪽 끝 edge case 처리
        dp[h][0] = dp[h-1][0] + triangle[h][0];
        dp[h][h] = dp[h-1][h-1] + triangle[h][h];
        for(int i = 1; i<h; i++){ // 각 layer는 위에 2개 보고 큰 것으로 결정 가능
            dp[h][i] = max(dp[h-1][i], dp[h-1][i-1]) + triangle[h][i];
        }
    }
    
    return *max_element(dp[n-1].begin(), dp[n-1].end());
}

 

시간복잡도

 n by n size를 모두 탐색하므로 O(n$^2$)

 

 

 

Programmers Lv. 3 이중우선순위큐, 12분

 몇 가지를 알아둬야 한다.

 일단 nlogn 알고리즘의 경우 5백만까지 커버할 수 있다.

 

 문제 접근은, 최대/최소값 둘 다를 nlogn으로 처리해야 하기 때문에 tree 구조인 map, set을 고려했다. set의 경우 element가 중복되지 않기 때문에 multiset을 써야 한다는 것은 알았지만 STL 이름을 잊어서 map으로 풀었다.

 

#include <set>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <iostream>

using namespace std;

map<int, int> m;

void insertIntoQueue(int n){
    m[n]++;
}

void removeMax(){
    int number = m.rbegin()->first, count = m.rbegin()->second;
    if(count == 1) m.erase(number);
    else m[number]--;
}

void removeMin(){
    int number = m.begin()->first, count = m.begin()->second;
    if(count == 1 || count == 0) m.erase(number);
    else m[number]--;
}
vector<int> solution(vector<string> arguments) {
    vector<int> answer;
    multiset<int> que;

    string sub;

    for(auto s : arguments) {
        sub =s.substr(0, 2);
        if(sub=="I ") que.insert(stoi(s.substr(2,s.length()-2))); 
        else if(s.substr(2,1)=="1"&&que.size()>0) { que.erase(--que.end()); }
        else if(que.size()>0) { que.erase(que.begin()); }
    }

    if(que.size()==0) { answer.push_back(0); answer.push_back(0); }
    else { 
       answer.push_back(*que.rbegin()); 
        answer.push_back(*que.begin());
    }

    return answer;
}

 

시간복잡도

 한 operation에 O(logn)이고 operation이 n개이므로 O(nlogn)

 

 

후기

1. map iterator에 접근하는 방법. begin().first로 접근하는 게 아니라 begin()->first로 접근한다.
   1. .first는 key, .second는 value
2. rbegin() - --end()라고 생각하면 된다. 제일 뒤에 있는 element.
3. istringstream으로 정해져 있는 input 받는 방법 - 기억해 두자.

 

 

 

Programmers Lv. 3 네트워크, 10분

 BFS를 쓸 줄 알면 풀리는 간단한 문제. 뭐.. 딱히 설명할 것도 없다. indexing만 주의하면 된다.

#include <string>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int maxn;
vector<int> visited; // visited[i] : i번 computer 썼는지 여부
vector<vector<int>> connected; // connected[i][j] : i번과 j번이 연결되어 있으면 true, else false

// n번째 computer에서 BFS
void BFS(int n){
    queue<int> q;
    q.push(n);
    visited[n] = true;

    while(!q.empty()){
        int cur = q.front(); q.pop();
        visited[cur] = true;

        for(int next = 0; next<maxn; next++){
            if(!visited[next] && connected[cur][next]){
                q.push(next);
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    vector<int> visited_init(n+1, false); 
    visited = visited_init;
    connected = computers;
    maxn = n;

    int answer= 0;
    for(int i =0; i<n; i++){
        if(!visited[i]){
            visited[i] = true;
            BFS(i);
            answer++;
        }
    }
    return answer;
}

 

시간복잡도

 BFS 시간복잡도는 O(V+E)