𝝅번째 알파카의 개발 낙서장

screen

[프로그래머스 / JAVA] Level 1 두 개 뽑아서 더하기 (68644)

posts

알고리즘

시리즈 톺아보기

프로그래머스

프로그래머스
count

두 개 뽑아서 더하기 🔗

랭크 사용 언어
Level 1 JAVA

🔗 두 개 뽑아서 더하기

문제 설명 🔗

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항 🔗

  • numbers의 길이는 2 이상 100 이하입니다.
    • numbers의 모든 수는 0 이상 100 이하입니다.

입출력 예 🔗

numbers result
{ 2, 1, 3, 4, 1 } { 2, 3, 4, 5, 6, 7 }
{ 5, 0, 2, 7 } { 2, 5, 7, 9, 12 }

입출력 예 설명 🔗

입출력 예 #1

  • 2 = 1 + 1 입니다. (1이 numbers에 두 개 있습니다.)
  • 3 = 2 + 1 입니다.
  • 4 = 1 + 3 입니다.
  • 5 = 1 + 4 = 2 + 3 입니다.
  • 6 = 2 + 4 입니다.
  • 7 = 3 + 4 입니다.

따라서 { 2, 3, 4, 5, 6, 7 } 을 return 해야 합니다.

입출력 예 #2

  • 2 = 0 + 2 입니다.
  • 5 = 5 + 0 입니다.
  • 7 = 0 + 7 = 5 + 2 입니다.
  • 9 = 2 + 7 입니다.
  • 12 = 5 + 7 입니다.

따라서 { 2, 5, 7, 9, 12 } 를 return 해야 합니다.

풀이 🔗

정수 배열 numbers에서 임의의 정수 두 개를 뽑아 더할 때, 나올 수 있는 모든 수의 배열을 요구하는 알고리즘이다.

  1. 배열에서 임의의 요소 두 개를 뽑아내는 알고리즘
  2. 두 수를 더한 값 저장

1번의 경우 이중 for로도 충분히 구현할 수 있지만, 이번에는 좀 더 알고리즘적인 측면에서 접근하고자 한다. 백트래킹을 활용한 조합 알고리즘을 통해 요소를 뽑아내보자.

2번의 경우 HashSet을 사용하여 더한 값의 고유값만을 지정하도록 하자.


JAVA

0/**
1 * 조합 메서드 (백트래킹)
2 *
3 * @param numbers: [int[]] 대상 배열
4 * @param isCheck: [int[]] 백트래킹 체크 여부 배열
5 * @param start: [int] 시작값
6 * @param target: [int] 조합할 갯수
7 */
8private void combination(int[] numbers, boolean[] isCheck, int start, int target)
9{
10 // 조합할 갯수가 0개일 경우 (탐색 완료)
11 if (target == 0)
12 {
13 int sum = 0;
14
15 for (int i = 0; i < numbers.length; i++)
16 {
17 // 백트래킹 체크일 경우
18 if (isCheck[i])
19 {
20 sum += numbers[i];
21 }
22 }
23
24 set.add(sum);
25 }
26
27 // 아닐 경우
28 else
29 {
30 for (int i = start; i < numbers.length; i++)
31 {
32 isCheck[i] = true;
33
34 combination(numbers, isCheck, i + 1, target - 1);
35
36 isCheck[i] = false;
37 }
38 }
39}

백트래킹 조합 알고리즘은 위와 같다.

조합을 수행한 뒤 선택된 두 값을 더해 HashSet 객체에 입력한다.

이후 해당값을 정렬하여 배열로 반환한다.

코드 🔗

JAVA

0import java.util.HashSet;
1
2/**
3 * 두 개 뽑아서 더하기 클래스
4 *
5 * @author RWB
6 * @since 2021.12.12 Sun 03:19:39
7 */
8class Solution
9{
10 private HashSet<Integer> set;
11
12 /**
13 * 해답 반환 메서드
14 *
15 * @param numbers: [int[]] 정수 배열
16 *
17 * @return [int[]] 해답
18 */
19 public int[] solution(int[] numbers)
20 {
21 set = new HashSet<>();
22
23 boolean[] isCheck = new boolean[numbers.length];
24
25 combination(numbers, isCheck, 0, 2);
26
27 return set.stream().mapToInt(Integer::intValue).sorted().toArray();
28 }
29
30 /**
31 * 조합 메서드 (백트래킹)
32 *
33 * @param numbers: [int[]] 대상 배열
34 * @param isCheck: [int[]] 백트래킹 체크 여부 배열
35 * @param start: [int] 시작값
36 * @param target: [int] 조합할 갯수
37 */
38 private void combination(int[] numbers, boolean[] isCheck, int start, int target)
39 {
40 // 조합할 갯수가 0개일 경우 (탐색 완료)
41 if (target == 0)
42 {
43 int sum = 0;
44
45 for (int i = 0; i < numbers.length; i++)
46 {
47 // 백트래킹 체크일 경우
48 if (isCheck[i])
49 {
50 sum += numbers[i];
51 }
52 }
53
54 set.add(sum);
55 }
56
57 // 아닐 경우
58 else
59 {
60 for (int i = start; i < numbers.length; i++)
61 {
62 isCheck[i] = true;
63
64 combination(numbers, isCheck, i + 1, target - 1);
65
66 isCheck[i] = false;
67 }
68 }
69 }
70}