문제를 푸는 기준

함수 시그니처와 반환값을 먼저 확인하고, 제한사항으로 허용 복잡도를 정한 뒤 예시를 손으로 추적합니다. 코드는 그 다음에 작성합니다.

핵심 개념

대표 문제

예산 안에서 가장 많이 구매하기

상품 가격 배열 prices와 예산 budget이 주어집니다. 예산을 넘지 않으면서 구매할 수 있는 상품의 최대 개수를 반환하세요.

함수 시그니처: solution(prices, budget)

제한사항

• prices의 길이는 1 이상 100,000 이하입니다.
• 모든 가격은 양의 정수입니다.
• 원본 prices의 순서는 바꾸지 않습니다.

입출력 예

풀이 설계

1. 최대 개수를 원하므로 싼 상품부터 봅니다.
2. 원본을 보존한 복사본을 오름차순 정렬합니다.
3. 누적 금액이 예산을 넘기 직전에 반복을 끝냅니다.

JavaScript 풀이

function solution(prices, budget) {
  const sorted = [...prices].sort((a, b) => a - b);
  let total = 0;
  let count = 0;
  for (const price of sorted) {
    if (total + price > budget) break;
    total += price;
    count += 1;
  }
  return count;
}

복잡도

• 시간복잡도: O(n log n)
• 공간복잡도: O(n)
• 핵심 패턴: 정렬 뒤 가능한 항목부터 선택
• 경계 사례: 가장 싼 상품도 예산보다 비싸면 0 반환

연습 문제

1. 기준 점수 세기

점수 배열에서 기준 이상인 점수 개수를 반환하세요.

2. 연속 중복 제거

바로 앞 문자와 같은 문자를 제거한 문자열을 반환하세요.

3. 최대 차이

뒤 값에서 앞 값을 뺀 차이의 최댓값을 반환하세요.

자주 하는 실수

• 정답을 return하지 않는 실수
• 호출 사이에 남는 전역 상태를 사용하는 실수
• 정렬로 원본 배열을 바꾸는 실수
• 정답이 없는 경우의 반환값을 빠뜨리는 실수

핵심 정리

• 함수 시그니처와 반환 자료형을 먼저 확정합니다.
• 제한사항으로 가능한 시간복잡도를 판단합니다.
• 예시와 경계 사례를 손으로 추적한 뒤 구현합니다.
• 완성한 solution 함수가 입력을 불필요하게 바꾸지 않는지도 확인합니다.

확인 문제

참고 자료

• 프로그래머스 JavaScript solution 함수 예시 
• MDN JavaScript 함수 
• MIT 6.006 알고리즘 설명·정당성·복잡도 지침