[코딜리티] PassingCars - Python3

코딜리티의 Easy 문제 PassingCars

문제 요구 조건 이해하기

배열을 순회하면서 원소의 값이 1이라면 그 이전 인덱스까지의 원소들 중에 0이 몇 개나 존재하는지 세어야 한다.

내 풀이 방법

1. 문제 카테고리가 구간합인걸 보고 힌트를 얻었다. 누적합 배열을 만들고, 주어진 배열을 순회하며 값이 1인 곳의 index - 누적합[index] + 1이 이전까지의 원소들 중 0의 개수라는 것을 이용했다.

 def solution(A):
     sum_array = [A[0]]
     result = 0
 ​
     for i in range(1, len(A)):
         sum_array.append(A[i] + sum_array[i-1])
     
     for i, value in enumerate(A):
         if value == 1:
             result += i - sum_array[i] + 1
 ​
     if result > 1000000000:
         return -1
     return result

풀이 회고

1. 처음에는 위의 방법처럼 풀지 않았다. 예시로 주어진 쌍이 조합과 같아 보여서 조합 문제인 줄 알았다. 그런데 문제를 읽다 보니 동쪽과 서쪽으로 이동하는 조건을 보고 단순한 조합 문제가 아니라고 생각했다.
2. 처음 생각한 방법은 지금부터 말하는 방법이다. 값이 0인 원소의 인덱스를 담은 zeros 배열과 값이 1인 원소의 인덱스를 담은 ones 배열을 만들고 정렬한다. ones 배열을 순회하면서 zeros 배열에서 순회하는 원소의 값과 가장 근접하게 작은 부분의 인덱스를 이진탐색으로 찾는다.(생각할 땐 몰랐는데 이 부분이 엉터리다. 이진 탐색으로 근접하게 작은 부분을 탐색할 수 없다.) 해당 인덱스를 결과에 더해준다.
3. 위의 방법은 검증을 제대로 하지 않았다. 풀이 방법은 엉터리였다. 그걸 코드를 작성하면서 깨달았다.
4. 코드를 작성하면서 검증을 하는 버릇이 있다. 제한사항의 조건에 맞춰서 최소 크기, 최대 크기의 경우에 대해서 검증하고, 모든 방법에 대한 구현을 어떻게 할 것인지 생각하고 작성하도록 해야겠다. 생각으로 모든 풀이를 끝내놓고 키보드를 잡자.
5. 카테고리 힌트가 없었다면 누적합 문제라는 것을 전혀 생각하지 못했다. 왜 그랬을까? 이때까지 풀었던 누적합 문제는 구간의 합을 구하라는 힌트가 문제에서 파악하기 쉽게 주어졌다. 이 문제에서는 문제의 제한 조건들을 읽고 누적합 문제인걸 파악하지 못했다. 한 인덱스에 도달하기 전까지 동쪽으로 이동한 차량의 수를 찾기 위해서 누적합을 사용했다는 점(통찰)을 기억하자.

다른 사람의 풀이

 def solution(A):
     N = len(A)
     east_cars = 0  # 동쪽으로 이동한 차량 수
     passing_cars = 0  # 조합의 개수
 ​
     for i in range(N):
         if A[i] == 0:
             east_cars += 1
         else:
             passing_cars += east_cars
         
         if passing_cars > 1000000000:  # 조합의 개수가 1,000,000,000을 초과할 경우 -1 반환
             return -1
 ​
     return passing_cars

위의 코드는 ChatGPT가 제시한 코드다. 내 코드와 비교했을 때, 누적합을 저장하기 위해서 변수 하나만을 사용해서 메모리를 절약하고, 미리 누적합을 구하지 않음으로써 반복을 줄였다. 이건 내 코드에서도 누적합을 구함과 동시에 그 이전까지의 값을 알 수 있으니 사용할 수 있다. 누적합을 구할 때 반드시 배열을 사용해야 한다는 생각을 버리고, 반복을 최소화하자.