문제를 푸는 기준

답 후보 x에 대한 가능 여부가 한 방향으로만 바뀐다면 배열이 아니라 정답 범위 자체를 이분 탐색할 수 있습니다.

핵심 개념

대표 문제

설치 간격 최대로 만들기

위치 배열 positions에 count개 장치를 설치할 때 인접 설치 위치 사이 최소 거리의 최댓값을 반환하세요.

함수 시그니처: solution(positions, count)

제한사항

• positions의 길이는 2 이상 200,000 이하입니다.
• 위치는 서로 다르고 count는 2 이상입니다.

입출력 예

풀이 설계

1. 위치를 정렬합니다.
2. 거리 distance를 지킬 때 설치 가능한 개수를 셉니다.
3. 가능하면 더 큰 거리, 불가능하면 더 작은 거리를 탐색합니다.

JavaScript 풀이

function solution(positions, count) {
  const sorted = [...positions].sort((a, b) => a - b);
  const canPlace = (distance) => {
    let placed = 1;
    let last = sorted[0];
    for (let i = 1; i < sorted.length; i += 1) {
      if (sorted[i] - last >= distance) {
        placed += 1;
        last = sorted[i];
      }
    }
    return placed >= count;
  };
  let low = 1;
  let high = sorted.at(-1) - sorted[0];
  let answer = 0;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (canPlace(mid)) {
      answer = mid;
      low = mid + 1;
    } else high = mid - 1;
  }
  return answer;
}

복잡도

• 시간복잡도: O(n log R)
• 공간복잡도: O(n)
• 핵심 패턴: 단조로운 가능 여부로 정답 후보 경계 탐색
• 경계 사례: 가능한 최댓값을 찾으므로 mid 저장 뒤 오른쪽 탐색

연습 문제

1. 첫 등장 위치

target의 첫 인덱스를 반환하세요.

2. 작업 최소 시간

모든 작업을 끝내는 최소 시간을 구하세요.

3. 예산 상한

가능한 상한액의 최댓값을 구하세요.

자주 하는 실수

• mid를 그대로 경계에 넣어 무한 반복하는 실수
• 가능한 최댓값과 불가능한 최솟값을 혼동하는 실수
• 값 찾기에서 정렬을 확인하지 않는 실수
• 정답 저장 시점을 일관되지 않게 쓰는 실수

핵심 정리

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

확인 문제

참고 자료

• MIT OpenCourseWare 6.006 Introduction to Algorithms 
• Princeton Algorithms 4e - Sorting 
• 프로그래머스 코딩테스트 고득점 Kit