일반 스터디/코딩 테스트

[프로그래머스] 주차 요금 계산

StelthPark 2025. 10. 9. 11:33

문제 개요

주차 기록 배열과 요금 정책을 받아서 차량별 주차 요금을 계산하는 함수를 구현하는 문제입니다.

입력 형식

  • records: 주차 기록 배열 (예: ["16:00 3961 IN","16:00 0202 IN","18:00 3961 OUT","18:00 0202 OUT","23:58 3961 IN"])
  • fees: 요금 정책 배열 [기본시간(분), 기본요금(원), 단위시간(분), 단위요금(원)]

출력 형식

  • 차량번호 오름차순으로 정렬된 요금 배열 (예: [0, 591])

요구사항 분석

핵심 요구사항

  1. 누적 주차시간 계산: 차량별로 모든 입차-출차 시간을 누적
  2. 출차 기록 없는 경우: 마지막 입차부터 23:59까지 계산
  3. 요금 계산 공식: 기본요금 + ((누적시간 - 기본시간) ÷ 단위시간) × 단위요금
  4. 결과 정렬: 차량번호 오름차순으로 정렬 후 값만 배열로 반환

제한사항

  • fees 배열 길이: 4
  • 기본시간: 1 ≤ fees[0] ≤ 1,439분
  • 기본요금: 0 ≤ fees[1] ≤ 100,000원
  • 단위시간: 1 ≤ fees[2] ≤ 1,439분
  • 단위요금: 1 ≤ fees[3] ≤ 10,000원
  • records 길이: 1 ≤ N ≤ 1,000
  • 시간 형식: HH:MM (00:00~23:59)
  • 차량번호: 4자리 숫자 문자열

해결 과정

1단계: 기본 구조 설계

function solution(records, fees) {
  const basicTime = fees[0];
  const basicFee = fees[1];
  const unitTime = fees[2];
  const unitFee = fees[3];

  const parkingData = {}; // 현재 주차 중인 차량
  const totalParkingTime = {}; // 차량별 누적 주차시간

  // 시간 변환 및 요금 계산 함수들...
}

2단계: 시간 변환 함수 구현

function timeToMinutes(timeStr) {
  const colonIndex = timeStr.indexOf(":");
  const hours = parseInt(timeStr.substring(0, colonIndex), 10);
  const minutes = parseInt(timeStr.substring(colonIndex + 1), 10);
  return hours * 60 + minutes;
}

최적화 포인트:

  • split() 대신 indexOf()와 substring() 사용
  • 배열 생성 없이 직접 파싱

3단계: 누적 주차시간 계산

// 주차 기록 처리
for (let i = 0; i < records.length; i++) {
  const record = records[i];
  const spaceIndex1 = record.indexOf(" ");
  const spaceIndex2 = record.indexOf(" ", spaceIndex1 + 1);

  const timeStr = record.substring(0, spaceIndex1);
  const carNumber = record.substring(spaceIndex1 + 1, spaceIndex2);
  const action = record.substring(spaceIndex2 + 1);

  const timeInMinutes = timeToMinutes(timeStr);

  if (action === "IN") {
    parkingData[carNumber] = timeInMinutes;
  } else if (action === "OUT") {
    if (parkingData[carNumber] !== undefined) {
      const parkingMinutes = timeInMinutes - parkingData[carNumber];

      // 누적 주차시간에 추가
      if (totalParkingTime[carNumber] !== undefined) {
        totalParkingTime[carNumber] += parkingMinutes;
      } else {
        totalParkingTime[carNumber] = parkingMinutes;
      }

      delete parkingData[carNumber];
    }
  }
}

4단계: 출차 기록 없는 차량 처리

// 출차 기록이 없는 차량들 처리 (23:59 출차로 가정)
const lastTime = 23 * 60 + 59; // 1439분
for (const carNumber in parkingData) {
  const parkingMinutes = lastTime - parkingData[carNumber];

  if (totalParkingTime[carNumber] !== undefined) {
    totalParkingTime[carNumber] += parkingMinutes;
  } else {
    totalParkingTime[carNumber] = parkingMinutes;
  }
}

5단계: 요금 계산 및 정렬

// 누적 주차시간을 기반으로 요금 계산
function calculateTotalFee(totalMinutes) {
  if (totalMinutes <= basicTime) {
    return basicFee;
  }

  const extraTime = totalMinutes - basicTime;
  const extraUnits = Math.ceil(extraTime / unitTime);
  return basicFee + extraUnits * unitFee;
}

// 각 차량별로 총 요금 계산
const result = {};
for (const carNumber in totalParkingTime) {
  result[carNumber] = calculateTotalFee(totalParkingTime[carNumber]);
}

// 차량번호를 오름차순으로 정렬하고 값만 배열로 반환
const sortedCarNumbers = Object.keys(result).sort();
const sortedValues = [];
for (let i = 0; i < sortedCarNumbers.length; i++) {
  sortedValues.push(result[sortedCarNumbers[i]]);
}

return sortedValues;

최종 구현 코드

function solution(records, fees) {
  const basicTime = fees[0];
  const basicFee = fees[1];
  const unitTime = fees[2];
  const unitFee = fees[3];

  const parkingData = {};
  const totalParkingTime = {};

  function timeToMinutes(timeStr) {
    const colonIndex = timeStr.indexOf(":");
    const hours = parseInt(timeStr.substring(0, colonIndex), 10);
    const minutes = parseInt(timeStr.substring(colonIndex + 1), 10);
    return hours * 60 + minutes;
  }

  function calculateTotalFee(totalMinutes) {
    if (totalMinutes <= basicTime) {
      return basicFee;
    }

    const extraTime = totalMinutes - basicTime;
    const extraUnits = Math.ceil(extraTime / unitTime);
    return basicFee + extraUnits * unitFee;
  }

  // 주차 기록 처리
  for (let i = 0; i < records.length; i++) {
    const record = records[i];
    const spaceIndex1 = record.indexOf(" ");
    const spaceIndex2 = record.indexOf(" ", spaceIndex1 + 1);

    const timeStr = record.substring(0, spaceIndex1);
    const carNumber = record.substring(spaceIndex1 + 1, spaceIndex2);
    const action = record.substring(spaceIndex2 + 1);

    const timeInMinutes = timeToMinutes(timeStr);

    if (action === "IN") {
      parkingData[carNumber] = timeInMinutes;
    } else if (action === "OUT") {
      if (parkingData[carNumber] !== undefined) {
        const parkingMinutes = timeInMinutes - parkingData[carNumber];

        if (totalParkingTime[carNumber] !== undefined) {
          totalParkingTime[carNumber] += parkingMinutes;
        } else {
          totalParkingTime[carNumber] = parkingMinutes;
        }

        delete parkingData[carNumber];
      }
    }
  }

  // 출차 기록이 없는 차량들 처리 (23:59 출차로 가정)
  const lastTime = 23 * 60 + 59;
  for (const carNumber in parkingData) {
    const parkingMinutes = lastTime - parkingData[carNumber];

    if (totalParkingTime[carNumber] !== undefined) {
      totalParkingTime[carNumber] += parkingMinutes;
    } else {
      totalParkingTime[carNumber] = parkingMinutes;
    }
  }

  // 각 차량별로 총 요금 계산
  const result = {};
  for (const carNumber in totalParkingTime) {
    result[carNumber] = calculateTotalFee(totalParkingTime[carNumber]);
  }

  // 차량번호를 오름차순으로 정렬하고 값만 배열로 반환
  const sortedCarNumbers = Object.keys(result).sort();
  const sortedValues = [];
  for (let i = 0; i < sortedCarNumbers.length; i++) {
    sortedValues.push(result[sortedCarNumbers[i]]);
  }

  return sortedValues;
}

테스트 케이스

기본 테스트 케이스

const records = [
  "16:00 3961 IN",
  "16:00 0202 IN",
  "18:00 3961 OUT",
  "18:00 0202 OUT",
  "23:58 3961 IN",
];
const fees = [120, 0, 60, 591];

// 결과: [0, 591]
// 0202: 16:00~18:00 (120분) → 기본시간 120분이므로 0원
// 3961: 16:00~18:00 (120분) + 23:58~23:59 (1분) = 총 121분 → 0 + Math.ceil(1÷60) × 591 = 591원

성능 분석

시간복잡도

  • O(N log N): records 배열 순회 O(N) + 정렬 O(N log N)
  • N ≤ 1,000이므로 충분히 효율적

공간복잡도

  • O(N): 차량 수만큼의 메모리 사용
  • parkingData, totalParkingTime, result 객체들

성능 리팩토링

function solution(records, fees) {
  // 공간복잡도 최적화: 하나의 객체로 통합 관리
  const basicTime = fees[0];
  const basicFee = fees[1];
  const unitTime = fees[2];
  const unitFee = fees[3];

  // 차량별 데이터를 하나의 객체로 통합: {carNumber: {entryTime: number, totalTime: number}}
  const carData = {};

  // 시간을 분으로 변환하는 함수 (최적화)
  function timeToMinutes(timeStr) {
    const colonIndex = timeStr.indexOf(":");
    const hours = parseInt(timeStr.substring(0, colonIndex), 10);
    const minutes = parseInt(timeStr.substring(colonIndex + 1), 10);
    return hours * 60 + minutes;
  }

  // 누적 주차시간을 기반으로 요금 계산하는 함수
  function calculateTotalFee(totalMinutes) {
    if (totalMinutes <= basicTime) {
      return basicFee;
    }

    const extraTime = totalMinutes - basicTime;
    const extraUnits = Math.ceil(extraTime / unitTime);
    return basicFee + extraUnits * unitFee;
  }

  // 주차 기록 처리
  for (let i = 0; i < records.length; i++) {
    const record = records[i];
    const spaceIndex1 = record.indexOf(" ");
    const spaceIndex2 = record.indexOf(" ", spaceIndex1 + 1);

    const timeStr = record.substring(0, spaceIndex1);
    const carNumber = record.substring(spaceIndex1 + 1, spaceIndex2);
    const action = record.substring(spaceIndex2 + 1);

    const timeInMinutes = timeToMinutes(timeStr);

    if (action === "IN") {
      // 입차 기록: 새로운 차량이거나 기존 차량의 새로운 주차 시작
      if (!carData[carNumber]) {
        carData[carNumber] = { entryTime: timeInMinutes, totalTime: 0 };
      } else {
        carData[carNumber].entryTime = timeInMinutes;
      }
    } else if (action === "OUT") {
      // 출차 기록
      const car = carData[carNumber];
      if (car && car.entryTime !== -1) {
        car.totalTime += timeInMinutes - car.entryTime;
        car.entryTime = -1; // 출차 완료 표시
      }
    }
  }

  // 출차 기록이 없는 차량들 처리 (23:59 출차로 가정)
  const lastTime = 23 * 60 + 59;
  for (const carNumber in carData) {
    const car = carData[carNumber];
    if (car.entryTime !== -1) {
      car.totalTime += lastTime - car.entryTime;
    }
  }

  // 시간복잡도 최적화: 정렬과 배열 생성을 한 번에 처리
  const carNumbers = Object.keys(carData);
  carNumbers.sort(); // 차량번호 오름차순 정렬

  const result = [];
  for (let i = 0; i < carNumbers.length; i++) {
    result.push(calculateTotalFee(carData[carNumbers[i]].totalTime));
  }

  return result;
}

 

  • 시간복잡도: O(N log N) 유지
  • 문자열 파싱: split() → indexOf() + substring()
  • 배열 생성: 불필요한 중간 배열 제거
  • 정렬 과정: 한 번의 정렬로 모든 처리 완료하도록 수정
  • 데이터 구조 통합
    • parkingData, totalParkingTime, result → carData 하나로 통합
    • 차량별 데이터를 {entryTime, totalTime} 구조로 관리
  • 상태 관리 개선
    • entryTime = -1로 출차 완료 상태 표시
    • 불필요한 조건 검사 제거
저작자표시 (새창열림)