23.07.26. 풀었던 문제들 복기

Leetcode 1870. Minimum Speed to Arrive on Time

 문제를 읽다 보니, binary search라는 느낌이 딱 왔다. 그리고 정리를 하다 보니, 아래와 같은 flow로 이건 무조건 binary search (parametric search)라는 생각이 들었다.

1. 불가능한 조건은 언제 나올까?
아무리 큰 speed로 dist[i]를 나누어도 올림한다. 즉, dist[i] 하나당 최소 1시간은 필요하다는 의미이다. (단, 마지막 dist[i]는 예외이다.) 따라서, hour 안에 도착하기 위해서는 n-1보다 큰 시간이 필요하다.
만약 hour <= n-1인 경우 불가능하다는 의미이다.
hour가 n-1보다 epsilon만큼 큰 경우는 speed를 매우 크게 설정해 달성할 수는 있다.

2. 가능한 조건을 어떻게 추릴까?
정답이 10^7을 초과하지 않는다. -> 최대 10^7로 잡으면 된다는 것 같다. 여기서 binary search가 맞다는 것을 확신했다.

 

첫 접근

// Runtime 473 ms Beats 14.39%
// Memory 101.5 MB Beats 67.19%

class Solution {
public:
    bool available(vector<int>& dist, int speed, double hour){
        double sum = 0;
        for(int i = 0; i<dist.size()-1; i++){
            sum += (dist[i] / speed);
            if(dist[i] % speed != 0) sum += 1;
        }
        // 마지막 element만이 hour의 소수점에 관여한다.
        int last = dist[dist.size()-1];
        sum += (double)last / speed;

        if(sum <= hour) return true;
        else return false;
    }
    int minSpeedOnTime(vector<int>& dist, double hour) {
        int n = dist.size();
        if(hour <= n-1) return -1;

        int start = 1, end = 10000000, mid;
        while(start < end){
            mid = (start + end) / 2;
            bool isAvailable = available(dist, mid, hour);
            if(isAvailable) end = mid;
            else start = mid + 1;
        }

        return end;
    }
};

 

시간복잡도

 dist length를 n이라고 했을 때, available() 함수는 모든 dist를 순회하므로 O(n)이다. 한편 binary search를 사용하는데 min값은 1, max값은 10$^7$이므로 O(10$^7$logn)이다.

 

공간복잡도

 추가로 array 형식의 공간을 사용하지 않는다. 따라서 O(1).

 

개선

 속도가 너무 느려 solution들을 보았다. 전체 flow는 동일했지만 딱 한 부분이 달랐다.

 나의 경우 availabile() 함수 내에 아래와 같이 / 연산을 하고 %를 사용해 있는 경우 +1을 했는데,

sum += (dist[i] / speed);
if(dist[i] % speed != 0) sum += 1;

 

 대부분 solution의 경우 아래와 같이 ceil() 함수를 사용했다. 이렇게 쓰니 속도가 매우 빨라졌다. 아마 내부적인 로직 차이가 있는 것 같다.

sum += ceil((double)dist[i] / speed);

// Runtime 327 ms Beats 64.60%
// Memory 101.5 MB Beats 67.19%

 

 

 

백준 25374. 등급 계산하기

 그냥 빡구현 문제... 오랜만에 손대니까 너무 오래 걸렸다. 1시간쯤,, 갈 길이 멀다.

 

 일단 풀이는, [0, 4, 7, 12, 17, 20, 17, 12, 7, 4]와 같이 각 등급별 할당될 인원을 1-indexing으로 만든다. 이후 [현재 등급]을 기록하고, 

• 현재 등급에 넣을 수 있는 경우, 넣는다.
• 넣을 수 없는 경우, 다음 등급을 탐색한다.
  • 단, 넣을 수 없는 경우이지만 이전 등수와 점수가 같은 경우 다음 등급에 있는 인원수를 하나 빼앗아 현재 등급에 할당한다.

 위 로직을 따라 풀었다.

void solve(){
	int N; cin>>N;
    vector<int> points(N); for(int i = 0; i<N; i++) cin>>points[i];

    sort(points.begin(), points.end(), greater<int>());

    vector<int> cuts = {0, 4, 7, 12, 17, 20, 17, 12, 7, 4}; // 차례대로 1등급 ~ 9등급에 할당될 인원. 1-indexing
    vector<int> answer(10, 0); // 1-indexing

    int grade = 1; answer[grade]++; cuts[grade]--; // *** 실수 : 1등을 넣었으면 1등급 할당 인원에서 1명 빼야 했다.
    for(int i = 1; i<N; i++){
        if(cuts[grade] > 0){ // 현재 등급에 넣을 수 있는 경우, 아무것도 하지 않고 넣으면 된다. 넣고, 할당량에서 1을 빼면 된다.
        }
        else{ // 넣을 수 없는 경우 다음 등급을 탐색한다.
            // 단, 이전 등수와 점수가 같은 경우 다음 등급에 있는 인원수를 하나 빼 와서 현재 등급에 할당해야 한다.
            if(points[i-1] == points[i]){ // 점수 같은 경우
                int nextGrade = grade + 1;
                while(cuts[nextGrade] == 0) nextGrade++; // 할당할 수 있는 등급이 나올 때까지 등급 뒤로 감.
                cuts[grade]++; // 인원수 하나 빼 옴
                cuts[nextGrade]--;
            }
            else{
                int nextGrade = grade + 1; // 점수 다른 경우 
                while(cuts[nextGrade] == 0) nextGrade++; // 할당할 수 있는 등급이 나올 때까지 등급 뒤로 감.
                grade = nextGrade;
            }
        }
        answer[grade]++;
        cuts[grade]--;
    }

    for(int i = 1; i<10; i++) cout<<answer[i]<<'\n';
}

 

 

후기

 오랜만에 푸니까 정신 나갈 것 같다. 문제도 안읽히고... 다시 익숙해져야겠지.