23.03.07. 풀었던 문제들

Leetcode 2187. Minimum Time to Complete Trips

문제를 딱 보면 parametric serach로 풀어야 할 것 같은 문제.

time의 범위는 아주 넓지만
time이 정해졌을 때 totalTrips는 구하기 쉽고(O(n))
정답이 연속적이다. (어떤 t가 답이면 t보다 큰 모든 값은 답이 될 수 있다)

다만 유의해야 할 점은 time의 상한을 어떻게 두느냐이다. totalTrips가 $10^{7}$, time[i]가 $10^{7}$일 때 정답은 $10^{14}$, 만약 time.len이 더 커지면 정답은 더 작아진다. 따라서 상한을 $10^{14} + 1$로 두었다. (근데 이렇게 안하고 LLONG_MAX로 두어도 된다. 다만 이 경우는 overflow 나지 않게 start를 0부터 잡아야 할 것이다.

첫 풀이

// Runtime 421 ms Beats 52.72%
// Memory 94.5 MB Beats 76.55%

typedef long long ll;

class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        ll start = 1, end = 100000000000001, mid = -1;
        while(start < end){
            mid = (start + end) / 2;

            ll cnt = 0; // number of trips
            for(int t : time){
                cnt += mid / t;
            }

            if(cnt >= totalTrips){
                end = mid;
            }
            else start = mid + 1;
        }
        return end;
    }
};

개선

어떻게 더 개선할 수 있을까? for문에서 cnt가 totalTrips보다 크거나 같아지는 경우 binary search의 방향은 정해진 것이다. 따라서 정해진 순간 break를 해 준다.

// Runtime 225 ms Beats 98.69%
// Memory 94.5 MB Beats 33.40%

typedef long long ll;

class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        ll start = 0, end = LLONG_MAX, mid = -1;
        while(start < end){
            mid = (start + end) / 2;

            ll cnt = 0; // number of trips
            for(int t : time){
                cnt += mid / t;
                if(cnt >= totalTrips) break;
            }

            if(cnt >= totalTrips){
                end = mid;
            }
            else start = mid + 1;
        }
        return end;
    }
};

시간복잡도

parameteric search이다. binary search에 $O(log2^{64)$, 각 binary search할 때 worst O(n)이 걸린다. 이 두 개의 곱이며, $O(log2^{64)$는 O(1)로 치환되기 때문에 O(logn)에 풀린다고 봐도 무방하다.

공간복잡도

추가 공간을 사용하지 않는다. O(1)이다.

후기

별다른 힌트 없이 parameteric search임을 알아냈다. + 범위 때문에 조금 고생하긴 했다. XXX_MAX에 1을 더하면 overflow가 난다는 걸 알고 있었는데도 무지성으로 썻다. 반성하자.

최적화 코드는 한 줄로 간단하게 나타낼 수 있었다.

프로그래머스 유사 칸토어 배열

정답률이 낮길래 진짜 이상한 문제겠구나 생각했는데 하... 이거만 2시간을 디버깅했다. 진짜 너무 짜증난다.

접근 자체는 맞았다. 다만 해석을 다르게 했을 뿐.

일단 [어떤 숫자 앞에 있는 1이 몇 개인지] 세면 된다. n=1, 2, ... 로 올라가면서 1은 이전 1 개수의 4배가 되고, 추가로 더해진 부분에 존재하는 1을 더해주면 된다. 예를 들어 17인 경우 n=1일 때 3 -> n=2일 때 17이 된다. 3에서 5를 곱하면 15가 되고, 남는 부분인 16 위치에 있는 1만 더해주면 된다는 것이다.

다만 여기서 몇 가지 함정이 있다.

1. 1은 11011로 바뀌기에 남는 부분 길이가 x일 때 [0, 1, 2, 2, 3]으로 늘게 된다.
2. 이건 어떻게보면 진수 변환이다. 5진수로의 변환.
- k번째 진수 자리에는 $4^{k}$개의 1이 있다.
- 여기서 함정이 생긴다. 남는 부분이 0인 경우가 생긴다... 그러니까 진수변환을 했을 때 123과 같은 경우일 때 120으로 계산해야 한다는 얘기이다
- 이걸 몰라서 2시간을 삽질했다.
이 두가지를 유의해서 짜야 한다

typedef long long ll;
// 어떤 경로를 거쳐서 number까지 도달하는지
vector<ll> getHistory(int n, ll number){
    vector<ll> history;
    if(number == 0){
        history.push_back(0);
        return history;
    }
    while(number > 0){
        history.push_back(number%5);
        number /= 5;
    }
    reverse(history.begin(), history.end());
    
    // 2가 나오면 그 뒤의 것은 지워야 함
    // 전부 0이기 때문
    for(int i = 0; i<history.size(); i++){
        if(history[i] == 2){
            i++;
            while(i < history.size()){
                history[i] = 0;
                i++;
            }
        }
    }
    return history;
}

// 경로 역추적하며 1개수 계산
ll cal(vector<ll> history){
    // 해당 숫자 "앞에 있는" 1개수를 찾아줌
    ll count = history[0] - (history[0] > 2);
    for(int i = 1; i<history.size(); i++){// 1개수 : 이전 1개수 * 4
        count *= 4L;
        count += history[i] - (ll)((history[i]) > 2);    
    }
    return count;
}

int solution(int n, long long l, long long r) {
    vector<ll> historyL = getHistory(n, l-1), historyR = getHistory(n, r);

    ll left = cal(historyL);
    ll right = cal(historyR);
    return right - left;
}

후기

처음부터 진수라는 개념으로 접근했으면 좀 더 편했을 것 같다...... 아아악 너무빡쳐

프로그래머스 혼자서 하는 틱택토

조건만 잘 배분하면 끝나는, 생각보다 별 거 아닌 문제.

O 개수는 항상 X보다 크거나 같아야. (조건 하나)
X 개수 +1는 항상 O보다 크거나 같아야 한다. (조건 둘)
- (X개수 <= O <= X개수+1)이어야 한다.
만약 X가 게임을 끝냈으면 O개수는 X개수와 같아야 한다.(조건 셋)
만약 O가 게임을 끝냈다면 O 개수는 X개수보다 많아야 한다. (조건 넷)

이렇게 간단하게 표현할 수 있는 이유는 잘못 두는 경우가

게임이 끝났는데 계속 진행한 경우
돌을 잘못 놓은 경우(OX 개수가 바뀜)

이렇게 2개 뿐이기 때문이다.

int SIZE = 3;

// 끝나는 조건 : 세로 3줄, 가로 3줄, 대각 2개
bool isEnd(vector<string> &board, char c){
    string s = "";
    for(int i = 0; i<SIZE; i++) s += c;
    
    for(int i = 0; i<3; i++){
        if(board[i] == s) return true;
    }
    
    for(int i = 0; i<3; i++){
        string vertical = "";
        for(int j = 0; j<3; j++){
            vertical += board[j][i];
        }
        if(vertical == s) return true;
    }
    
    string digonal1 = "", digonal2 = "";
    for(int i = 0; i<3; i++){
        digonal1 += board[i][i];
        digonal2 += board[2 - i][i];
    }
    if(digonal1 == s) return true;
    if(digonal2 == s) return true;
    
    return false;
}
int solution(vector<string> board) {
    // 둔 수 계산
    int ocount = 0, xcount = 0;
    for(int i = 0; i<SIZE; i++){
        for(int j = 0; j<SIZE; j++){
            if(board[i][j] == 'O') ocount++;
            if(board[i][j] == 'X') xcount++;
        }
    }

    if(!(xcount <= ocount && ocount <= xcount+1)) return 0;

    // 끝남 여부 계산
    bool isOEnd = isEnd(board, 'O'), isXEnd = isEnd(board, 'X');

    // 조건 셋. X가 완성시킨 시점에서 O가 한 수 더 놓는 것은 불가능
    if(isXEnd && ocount != xcount){
        return 0;
    }
    
    // 조건 넷. O가 완성시킨 시점에서 X가 한 수 더 놓는 것은 불가능
    if(isOEnd && ocount <= xcount){
        return 0;
    }
    
    return 1;
}

저작자표시 (새창열림)

'PS > PS Log' 카테고리의 다른 글

23.03.09. 풀었던 문제들 (0)	2023.03.09
23.03.08. 풀었던 문제들 (0)	2023.03.08
23.03.06. 풀었던 문제들 (0)	2023.03.07
23.03.05. 풀었던 문제들 (0)	2023.03.06
23.03.04. 풀었던 문제들 (0)	2023.03.05