9주차 알고리즘 매주 세문제 풀기(튜플, 다음 큰 숫자, 땅따먹기, 포켓몬)

이번주 풀 문제!

튜플, 다음 큰 숫자, 땅따먹기 문제 풀기

요즘에는 운동하느라 퇴근하고 공부할시간이 많이 없는데 그래도 최대한 주말을 이용해서라도 풀어보려고 노력중이다. 

그래도 9주차까지 온 내가 대견하다! 그래도 몇달째 주말이든 평일이든 알고리즘을 계속 공부한다는게 중요한거니까!

튜플

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool comp(pair<int, int> a, pair<int, int> b){
    return a.second > b.second;
}

vector<int> solution(string s) {
    vector<int> answer;
    vector<pair<int, int>> arr(100001, {0, 0});

    for(int i = 0; i < 100001; i++){
      arr[i].first = i;
    }
    
    string temp = "";
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '}' || s[i] == '{' || s[i] == ',' ){
            if(temp != ""){
                arr[stoi(temp)].second++;
            }
            temp = "";
        }else{
            temp += s[i];
        } 
        
    }
    
    sort(arr.begin(), arr.end(), comp);

    for(int i = 0; i < arr.size(); i++){
        if(arr[i].second == 0)
            break;
        answer.push_back(arr[i].first);
    }
    
    return answer;
}

이문제는 문제가 이해가 안되서 고생했다. 

어찌됬든 각원소가 등장한 횟수를 체크해서 내림차순으로 배열에 넣어주면 정답이 된다. 

문자열을 자를때는 } , { 는 무시하고 숫자만 누적해서 숫자를 구해준다(stoi 함수를 통해 string으로 int 로 변환)

 

 

다음큰숫자

뭔가 이상한거 같다. 인터넷에 있는 답변도 다 안됨

시간초과 날게 없는데도 시간초과가 계속난다. 근데 숫자범위가 적어서 이해가 안된다. 진짜 브루트포스적으로 풀어도 풀려야하는데.

 

땅따먹기

#include <iostream>
#include <vector>
using namespace std;

int comp(int a, int b, int c){
    int answer = a;
    if(answer < b)
        answer = b;
    if(answer < c)
        answer = c;
    return answer;
}

int solution(vector<vector<int> > land)
{
    int answer = 0;
    vector<vector<int>> d(land.size(), vector<int> (4, 0));
    
    d[0][0] = land[0][0];
    d[0][1] = land[0][1];
    d[0][2] = land[0][2];
    d[0][3] = land[0][3];
    
    for(int i = 1; i < land.size(); i++){
        d[i][0] = comp(d[i-1][1], d[i-1][2], d[i-1][3]) + land[i][0];
        d[i][1] = comp(d[i-1][0], d[i-1][2], d[i-1][3]) + land[i][1];
        d[i][2] = comp(d[i-1][0], d[i-1][1], d[i-1][3]) + land[i][2];
        d[i][3] = comp(d[i-1][0], d[i-1][1], d[i-1][2]) + land[i][3];
    }
    
    answer = d[land.size()-1][0];
    if(answer < d[land.size()-1][1])
        answer = d[land.size()-1][1];
    if(answer < d[land.size()-1][2])
        answer = d[land.size()-1][2];
    if(answer < d[land.size()-1][3])
        answer = d[land.size()-1][3];
    return answer;
}

전형적인 다이나믹 프로그래밍 문제. 다이나믹 프로그래밍 문제의 경우에는 쉬워도 헤멜때가 많은데, 오늘은 잘 풀어서 기분이 좋다.

이렇게 문제를 잘풀면 기부니 조크든요.

 

 

포켓몬

 

 

#include <vector>
using namespace std;

int solution(vector<int> nums)
{
    int answer = 0;
    vector<int> a(200001, 0);
    
    for(int i = 0; i < nums.size(); i++){
        a[nums[i]]++;
    }
    
    int n = nums.size() / 2;
    int c = 0; 
    for(int i = 0; i < 200001; i++){
        if(a[i] > 0){
            c++;
        }
    }
    
    if(n <= c)
        answer = n;
    else
        answer = c;
    
    return answer;
}

 

이문제는 뭐... 레벨2는 이상한게 어려운건 진짜 레벨2가 맞나 싶다가, 쉬운건 또 엄청 쉽다. 최대 n개를 가져갈수 있고, 종류 수(c)가 n보다 작아도 가져갈 수 있는 종류는 c, n보다 커도 n개 밖에 못가져간다.

 

후기

이번주는 화요일에 문제를 다 풀었다. 쉬운 문제들이라 가능했지만, 당분간은 보안 공부를 더 열심히 하려고 하루정도 몰아서 알고리즘을 하고 나머지날에는 다른 공부를 하려고 한다. 

알고리즘 공부가 좋은건 확실히 코드를 생각할때 좀 더 분명해지는것이 있다는거다. 많은 개발자분들이 단순히 뭔가 구현만 되면 끝이라고 생각하기도 하는것같은데, 사실 그냥 아무렇게 만드는건 아무나 하지만 잘하는게 어려운것 아니겠나. 잘하기 위해서는 알고리즘이 꼭 필요하다고 생각한다. 이런 능력을 키워야 자잘한 버그도 잡아낼수 있을 것이다.