13주차. 알고리즘 3문제 풀기

13주차를 시작하며

이상하게 꼭 세문제를 풀겠다고하면 그냥 임의로 3문제 뽑는건데도 꼭 세번째 문제는 잘 안풀린다. 알 수 없다. 3월부터 계속 알고리즘 공부를 하는 내가 자랑스럽다. 무슨 알고리즘 기본만 해도 된다는데, 난 그만큼만 공부하면 안되던데 어떤 사람은 되나보다. 재수없는 사람들이 세상에 참많은가보다. 여튼 나는 내 할일을 해야하는데, 꿋꿋이 세문제나 그보다 더 많이 풀어온 내자신이 자랑스럽다. 

 

추석 트래픽(쫄면 못풀지만, 안쫄면 풀수있다)

programmers.co.kr/learn/courses/30/lessons/17676

코딩테스트 연습 - [1차] 추석 트래픽

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

pair<int, int> converter(string lines){
    string end = lines.substr(11, 12);
    string duration = lines.substr(24);
    
    int endnum = stoi(end.substr(0,2)) * 60 * 60 * 1000;
    endnum += stoi(end.substr(3,2)) * 60 * 1000;
    endnum += stoi(end.substr(6,2)) * 1000;
    endnum += stoi(end.substr(9));

    int startnum = stoi(duration.substr(0, 1)) * 1000 - 1;
    if(duration[1] == '.'){
        int c = 0; 
        for(int i = 2; i < duration.size(); i++){
            if(duration[i] == 's'){
                break;
            }
            c++;
        }
        startnum += stoi(duration.substr(2, c));
    }
    
    pair<int, int> a;
    a.first = endnum - startnum;
    a.second = endnum;
    return a;
}

int solution(vector<string> lines) {
    int answer = 0;
    
    int mmin = 100000000;
    int mmax = -1000000000;
    vector<pair<int, int>> con;
    for(int i = 0; i < lines.size(); i++){
        pair<int, int> a = converter(lines[i]);
        con.push_back(a);
        if(mmin > a.first){
            mmin = a.first;
        }
        if(mmax < a.second){
            mmax = a.second;
        }
    }
     
    for(int i = 0; i < con.size(); i++){
        con[i].first = con[i].first - mmin;
        con[i].second = con[i].second - mmin;
    }
    
    // 0초부터 1초깢, 0.001초에서 1.001초까지
    vector<int> checker(mmax - mmin + 1001, 0);
    
    for(int i = 0; i < con.size(); i++){
        int start = con[i].first;
        int end = con[i].second + 999;
        for(int j = start; j <= end; j++){
            checker[j]++;
        }
    }
    
    for(int i = 0; i < checker.size(); i++){
        if(answer < checker[i]){
            answer = checker[i];
        }
    }
    return answer;
}

프로그래머스에서 3단계 문제를 풀다보면, 어떤 문제는 정말로 어려운 문제라 3단계이고 어떤건 겁을 줘서 못푸는거지만 사실은 그렇게 어려운문제가 아닌 경우가 있다. 이 경우가 딱 후자의 경우이다. 내가 숫자가 좀 약하다보니까(진짜 약한지는 모르겠다, 대학은 수리논술 100프로에 논술은 항상 잘해서.. 그냥 수능 수학을 잘 못한거같기두하고..) 이런 숫자 다루는 문제는 좀 쫄아서 잘 못푼다. 

 

하지만 이 문제는 단순히 for문을 여러개 잘 쓰면 풀수 있는 문제이다(더 효율적으로 푸는 방법도 있겠지만!!)

 

1. 일단 시간은 숫자로 변환해서 인덱스로 쓸수 있게만든다 ->  이부분이 좀 아리까리했다. 좀 노가다스럽기도하고. 

모든 숫자는 ms 를 1인 것으로 변환한다. 

 

 

2. 끝시간과 처리 시간을 숫자화 한다음 시작시간을 구하는데, 이때 시작시간 = 끝시간 - 처리시간 + 1 이다. 왜냐하면 양끝시간은 포함한다고 했기 때문에. 

 

3. 그다음 그냥 배열을 만들어도 되지만, 나는 최소값을 구해서 제일 작은 시작시간을 0으로 한번 변환해줬다(내 정신건강을 위해서)

 

4. 그다음 checker라는 벡터를 생성했다. 이건 각 구간을 표시하려고 하는거다. 해당하는 부분에 1을 더해줘서 최종에 제일많이 겹치는 부분을 구하려고 한다. 

 

그런데 이때 end는 999ms를 더해준다. 왜냐하면 1초동안이라고 했는데, 나는 다 ms로 구해놨기때문에, 

만약 end가 0001 ms면, 0001ms 부터 0005 ms 랑은 1초 내에있는건데, end를 0001로 끝내버려미녀 0002ms에서부터 확인하면 구간이 겹치지 않아서 갯수가 빠지기 때문이다. 

 

 

 

설명을 잘 써보려고하는데, 아직 설명능력은 조금 부족한것 같다!!! 

 

 

2Xn타일링

programmers.co.kr/learn/courses/30/lessons/12900

코딩테스트 연습 - 2 x n 타일링

 

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

int solution(int n) {
    int answer = 0;
    int ddiv = 1000000007;
    
    vector<int> d(n+1, 0);
    d[1] = 1;
    d[2] = 2;
    for(int i = 3; i <= n; i++){       
        d[i] = (d[i-2] + d[i-1])%ddiv;
    }
    answer = d[n] % ddiv;
    return answer;
}

 

거의 뭐 다이나믹 프로그래밍의 교과서적인 문제다. 

 

 

브라이언의 고민

programmers.co.kr/learn/courses/30/lessons/1830

코딩테스트 연습 - 브라이언의 고민