[leetcode] Time Needed to Buy Tickets

문제

• 문제 링크
• 배열 tickets와 정수 k가 주어진다. tickets[i]는 i번째에 있는 사람이 사고 싶은 티켓 개수를 의미한다. 0번째에 있는 사람부터 티켓을 한 장씩 사기 시작한다. 티켓을 산 후에 아직 사려는 티켓을 다 못 샀다면 맨 뒤로 가서 다시 순서를 기다린다. 티켓을 모두 샀다면 다시 기다리지 않고 떠난다. 이때 k번째에 있는 사람이 티켓을 모두 다 사는 데에 걸리는 시간을 구해야 한다.
• 제약 조건
  • 배열 길이: 1 <= tickets.length <= 100
  • 배열 값 범위: 1 <= tickets[i] <= 100
  • k 범위: 0 <= k < tickets.length

풀이

풀기 전

• 조건에 따라 나눠서 생각하면 쉽게 풀린다.
  • k번째 사람보다 더 적은 티켓을 사고 싶은 사람
    -> 사고 싶은 만큼 순회한다.
  • k번째 사람과 같거나 더 많은 티켓을 사고 싶은 사람
    -> k보다 앞에 있는 경우 -> k번째 사람이 모두 구매하는 k번만큼만 순회한다.
    -> k보다 뒤에 있는 경우 -> k번째 사람이 모두 구매하고 끝나기 때문에 k-1번만큼만 순회한다.

코드

class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        int ans = 0;
        for (int i=0; i<tickets.length; i++) {
            ans += Math.min(tickets[i], tickets[k]);
            if (k < i && tickets[k] <= tickets[i])
                ans--;
        }
        return ans;
    }
}

푼 후

• 처음에는 k번째 값이 0이 될 때까지 반복문 돌렸었는데, 그럴 필요 없이 조건에 따라 더해주면 됐다. 제약 조건이 약해서 실행 시간에 큰 차이는 없었다.
• tickets 길이만큼만 순회하기 때문에 시간 복잡도는 O(tickets.length)이고, 추가로 크게 사용하는 메모리는 없어서 공간 복잡도는 O(1)이다.