[프로그래머스] 두 개 뽑아서 더하기

문제 설명

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

 

제한사항

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

 

문제 풀이

이 문제를 맨 처음 어떻게 접근을 해야할지 도무지 감을 잡을 수 없었다.
그 결과 책의 힘을 빌렸다. 이번에 프로그래머스 알고리즘 책을 하나 구매했다.
한동안 고민을 해보고, 도저히 감을 못잡겠다 싶으면 긴 시간을 소비하지 않고 바로바로 책을 보면서 이해해보려고한다.
그런데 책을 본 결과 내가 생각조차 하지 못한 접근법으로 문제를 풀었다.
결과적으로 보았을 때, 책을 확인함으로써 내 사고력이 조금이나마 증가되는 느낌을 받았다.
내가 1시간이고 2시간이고 더 고민을 했더라도 못풀었을 것 같다.
최대 1시간 정도 고민을 하고나서 못풀겠으면 바로 책을 보면서 해당 문제에 대한 접근법, 해설을 보는게 나을 것 같다.

본론으로 가서 문제 풀이를 해보겠다.

import java.util.Arrays;
import java.util.HashSet;

class Solution {
    public int[] solution(int[] numbers) {
        HashSet<Integer> set = new HashSet<>(); // 중복값 제거를 위한 해시셋 생성

        for (int i = 0; i < numbers.length - 1; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                set.add(numbers[i] + numbers[j]);
            }
        }

        int[] answer = set.stream().sorted().mapToInt(Integer::intValue).toArray();
        System.out.println(Arrays.toString(answer));

        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] numbers = {5, 0, 2, 7};

        solution.solution(numbers);
    }
}

이 문제는 배열을 사용한 문제이다.
그것도 이차원 배열을 사용하여 문제에 접근했어야했다.
나는 이차원 배열로 접근할 생각조차 하지 못했다.
단순히 일차원 배열을 이용해서 어떻게든 해결하려고 했었다.

for문을 사용해서 모든 합의 경우의 수를 구하는 것이다.
맨 처음 코드를 보았을 때, for문의 조건들이 도무지 이해가 가지 않았다.

내가 이해되지 않았던 부분은 왜 numbers.length - 1를 쓰고, 왜 int j = i + 1를 쓰는지에 대한 것이었다.
그러나 직접 예시를 보니, 조금씩 이해가 가기 시작했다.

배열 [5, 0, 2, 7]에서

1. i = 0일 때:
   • j는 1, 2, 3이다.
   • 계산하는 조합: (5,0), (5,2), (5,7)
2. i = 1일 때:
   • j는 2, 3이다.
   • 계산하는 조합: (0,2), (0,7)
3. i = 2일 때:
   • j는 3이다.
   • 계산하는 조합: (2,7)

i값을 확인하면 0부터 numbers.length - 1이고,
j값도 확인하면 1부터 numbers.length이다.

그래서 위와 같은 for문의 조건이 나오게 된 것이었다.

그리고 내가 의문이었던 것은 중복값 제거에 대한 부분이었다.
찾아보니 해시셋을 사용한 이유는 이 때문이었다.

해시셋은 자바의 Set 인터페이스를 구현한 클래스로, 자동으로 중복 값을 제거하는 특성을 가지고 있다고 한다.

해시셋의 특징은 다음과 같다.

• 중복 값을 허용하지 않는다. 동일한 값을 추가하려고 하면, 이미 존재하는 값이므로 무시된다.
• 순서를 보장하지 않는다. 요소들이 삽입된 순서대로 유지되지 않는다.
• add() 메서드를 사용해 요소를 추가할 때, 이미 존재하는 값이면 false를 반환하고, 새로운 값이면 true를 반환한다.

이 문제를 풀면서 해시셋에 대해 새롭게 배우게 되었고, for문의 조건에 대해서는 아직 어렵지만 조금이나마 접근을 할 수 있게 되었다.
내가 만약 이 문제를 다시 푼다면, for문의 조건식에 대해 매우 많은 시간을 소비할 것 같다.