문제를 푸는 기준

완전탐색은 제한사항 안에서 가장 단순하고 확실한 풀이일 수 있습니다. 후보 수와 후보 하나의 검사 비용을 곱해 먼저 판단합니다.

핵심 개념

대표 문제

세 수의 목표 합

정수 배열 numbers에서 서로 다른 세 인덱스를 골라 합이 target이 되는 조합의 개수를 반환하세요.

함수 시그니처: solution(numbers, target)

제한사항

• numbers의 길이는 3 이상 100 이하입니다.
• 같은 값이 서로 다른 인덱스에 있을 수 있습니다.

입출력 예

풀이 설계

1. i를 첫 인덱스로 고릅니다.
2. j는 i 뒤, k는 j 뒤에서 고릅니다.
3. 합이 target이면 개수를 늘립니다.

JavaScript 풀이

function solution(numbers, target) {
  let count = 0;
  for (let i = 0; i < numbers.length - 2; i += 1) {
    for (let j = i + 1; j < numbers.length - 1; j += 1) {
      for (let k = j + 1; k < numbers.length; k += 1) {
        if (numbers[i] + numbers[j] + numbers[k] === target) count += 1;
      }
    }
  }
  return count;
}

복잡도

• 시간복잡도: O(n³)
• 공간복잡도: O(1)
• 핵심 패턴: 증가하는 인덱스로 고정 개수 조합 전부 확인
• 경계 사례: 값이 같아도 인덱스가 다르면 별도 조합

연습 문제

1. 반복 답안 점수

세 답안 패턴의 최고 득점자를 반환하세요.

2. 카펫 크기

칸 수 조건에 맞는 가로·세로를 반환하세요.

3. 숫자 카드 소수

카드를 이어 만들 수 있는 소수 수를 구하세요.

자주 하는 실수

• 후보 수를 계산하지 않는 실수
• 인덱스 순서를 고정하지 않아 중복 계산하는 실수
• 값 중복과 인덱스 중복을 혼동하는 실수
• 반복 경계를 하나 빠뜨리는 실수

핵심 정리

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

확인 문제

참고 자료

• 프로그래머스 코딩테스트 고득점 Kit 
• MIT OpenCourseWare 6.006 Introduction to Algorithms 
• MDN Array