📚 algo-wiki

Appearance

✅ Passing Cars 문제 해결 (Codility) ​

📌 문제 설명 ​

배열 A가 주어졌을 때, 동쪽(0)과 서쪽(1)으로 이동하는 차들의 교차 횟수를 계산하는 문제입니다. 즉, 0이 나오고 이후에 1이 나오면 그 두 차는 페어를 이룹니다.

🔹 입력 ​

  • A: 0과 1로 이루어진 정수 배열 (0은 동쪽으로 가는 차, 1은 서쪽으로 가는 차)

🔹 출력 ​

  • 총 0 → 1 페어의 개수 (1,000,000,000을 초과하면 -1 반환)

📍 예제 분석 ​

typescript
A = [0, 1, 0, 1, 1]

👉 쌍을 이루는 경우:

  • 첫 번째 0은 뒤의 1, 1, 1과 페어링 가능 → 3개
  • 두 번째 0은 뒤의 1, 1과 페어링 가능 → 2개

✅ 출력: 5

🚀 코드 (O(N)) ​

typescript
function solution(A: number[]): number {
  let answer = 0
  let eastCars = 0

  for (let car of A) {
    if (car === 0) {
      eastCars++ // 동쪽으로 가는 차 카운트 증가
    } else {
      answer += eastCars // 서쪽으로 가는 차를 만났을 때 동쪽 차 수만큼 더함
    }
    if (answer > 1_000_000_000) return -1 // 제한 초과 처리
  }

  return answer
}

💡 해결 방법 ​

  1. 동쪽(0)으로 가는 차의 개수를 저장 (eastCars 변수 사용)
  2. 서쪽(1)으로 가는 차를 만날 때마다 기존의 eastCars 값을 answer에 추가
  3. 최대 1,000,000,000을 초과하면 -1 반환

✅ 시간 복잡도: O(N) ​

  • 배열을 한 번만 순회하여 해결 가능

✅ 공간 복잡도: O(1) ​

  • 추가적인 배열을 사용하지 않고 변수를 활용하여 최적화

🛠 예제 테스트 ​

typescript
console.log(solution([0, 1, 0, 1, 1])) // 출력: 5
console.log(solution([1, 0, 1, 0, 1])) // 출력: 2
console.log(solution([0, 0, 0, 0, 1])) // 출력: 4
console.log(solution([1, 1, 1, 1, 0])) // 출력: 0
console.log(solution([0, 0, 0, 1, 1, 1])) // 출력: 9

📌 결론 ​

✅ O(N)으로 효율적으로 해결 가능! 🚀
✅ 0이 등장할 때마다 이후의 1과 페어를 이루는 개수를 계산! 🎯
✅ **효율적인