← 전체 글로 돌아가기

competitive-programming2022년 2월 11일1분 분량

[LEETCODE] 2167. Minimum Time to Remove All Cars Containing Illegal Goods 풀이

수정일: 2022년 2월 11일

Two pointersDynamic programming

지원 언어:enko

#Problem

2167. Minimum Time to Remove All Cars Containing Illegal Goods

#Approach

#Two pointers를 떠올려 봅시다.

left: s[0]부터 s[i]까지의 '1'들을 제거하는 최소 시간
right: s[i+1]부터 s[n-1]까지의 '1'들을 제거하는 최소 시간

#왼쪽에서 오른쪽으로 순회하면서,

left 값을 다음 두 값 중 최솟값으로 갱신합니다:

left+2 (앞부분을 제거하지 않고 s[i]를 제거하는 비용)
i+1 (s[i]까지 앞부분 전체를 제거하는 비용)

right 값을 다음 값으로 갱신합니다:

n - 1 - i (오른쪽에서 모든 차량을 제거하는 비용)

#순회 중에 `ans`를 갱신합니다.

$ans = \min_{\rm i} (left_i + right_i)$

#Code

/**
 * written: 2022. 02. 11. Fri. 16:57:01 [UTC+9]
 * jooncco의 mac에서.
 **/

class Solution {
public:
    int minimumTime(string s) {
        int n= s.length(), l= 0, ans= n;
        for (int i=0; i < n; ++i) {
            l= min(l + 2*(s[i] == '1'), i+1);
            ans= min(ans, l + n-1-i);
        }
        return ans;
    }
};

#Complexity

Time: $O(n)$
Space: $O(1)$