← 4주차 · 완전탐색과 시뮬레이션
쉬움완전탐색배열

세 수의 합

정수 배열 nums와 정수 m이 주어져요. 서로 다른 세 개의 원소를 골라 더했을 때, m을 넘지 않으면서 가장 큰 합을 반환해요.

그런 조합이 하나도 없으면 -1을 반환해요.

원소가 100개까지라 세 개를 고르는 모든 경우는 최대 16만 가지 남짓이에요. 영리한 방법을 찾기 전에, 모든 경우를 만들어 보는 코드부터 정확히 쓰는 것이 이 문제의 목적이에요.

예시

예시 1
입력
nums = [5, 6, 7, 8, 9], m = 21
출력
21
설명
5 + 7 + 9 = 21 로 정확히 m 이에요. 9 + 8 + 7 = 24 는 m을 넘어요.
예시 2
입력
nums = [1, 2, 3], m = 10
출력
6
설명
고를 수 있는 조합이 하나뿐이에요.
예시 3
입력
nums = [10, 10, 10], m = 5
출력
-1
설명
어떤 조합도 5를 넘지 않을 수 없어요.

제한 사항

  • 3 ≤ nums.length ≤ 100
  • 1 ≤ nums[i] ≤ 100,000
  • 1 ≤ m ≤ 300,000
  • 같은 인덱스를 두 번 고를 수 없어요. 값이 같은 원소가 여러 개 있는 것은 괜찮아요.
인덱스 i < j < k 로 삼중 반복문을 돌면 같은 조합을 두 번 세지 않아요. for j = i + 1, for k = j + 1 로 시작하는 것이 요령이에요. 답을 담을 변수는 -1로 초기화해 두면 '없음' 처리가 저절로 돼요.
javascript
function threeSum(nums, m) {
  let best = -1;
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        const sum = nums[i] + nums[j] + nums[k];
        if (sum <= m && sum > best) best = sum;
      }
    }
  }
  return best;
}
이전 문제문자열 압축
다음 문제부분집합의 합
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.