[Java] 두 개 뽑아서 더하기 (programmers)

Haeun Noh·2023년 5월 29일

programmers

목록 보기

46/64

0529

📌문제 설명

정수 배열 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 해야 합니다.

📌풀이 방법

이 문제는 서로 다른 인덱스의 숫자끼리 더하여 중복되지 않고 오름차순정렬된 합계들을 반환해야 하는 문제입니다.

처음에는 아래의 순서대로 문제를 해결하려 시도하였습니다.

다른 인덱스끼리의 합 구하기
배열에 있는 합을 오름차순 정렬하기
배열 안에 있는 합의 값이 전부 다 0일 경우에는 [0] 반환하기
겹치지 않는 합계값의 개수 구하기
4번에서 구한 값만큼의 길이를 가지는 정답 배열 만들기
정답 배열의 0번방을 합계의 0번방의 값으로 초기화하기
정답 배열과 합계의 값을 비교하여 겹치지 않는 수들을 정답 배열에 넣기
합계 배열 반환하기

이러한 풀이 방법의 소스 코드는 다음과 같습니다.

class Solution {
    public int[] solution(int[] numbers) {
        int[] sum = new int[numbers.length*numbers.length];
        int idx = 0;
        boolean b = true;
        // 다른 인덱스의 값의 합 구하기
        for ( int i = 0; i < numbers.length; i++) {
            for ( int j = 0; j < numbers.length; j++) {
                if ( i != j )
                    sum[idx++] = numbers[i] + numbers[j];
            }
        }
        // 합 오름차순 정렬
        for ( int i = 0;i < sum.length; i++) {
            for ( int j = 0;j < sum.length; j++) {
                if ( sum[i] < sum[j] ) {
                    int tmp = sum[i];
                    sum[i] = sum[j];
                    sum[j] = tmp;
                }
            }
        }
        // 전부 다 0일 경우
        int zero = 0;
        for ( int i = 0; i < sum.length; i++) {
            if ( sum[i] == 0 ) {
                zero++;
            }
        }
        if ( zero == sum.length ) {
            int[] arr = new int[1];
            arr[0] = 0;
            return arr;   
        }
        
        // 겹치지 않는 sum개수 구하기
        int cnt = 0;
        for ( int i = 1; i < sum.length; i++) {
            if ( sum[i-1] == sum[i] )
                continue;
            cnt++;
        }
        
        // 정답을 담을 answer
        int[] answer = new int[cnt];
        answer[0] = sum[0];
        idx = 1;
        for ( int i = 1; i < sum.length; i++ ) {
            if ( answer[idx-1] != sum[i] ) {
                answer[idx] = sum[i];
            }
        }
        return answer;
    }
}

하지만 "제출 후 채점하기"의 8번째 테스트케이스에서 실패가 나오게 됩니다.
제 예상으로는 아마 배열에 0과 0이 아닌 수가 같이 있을 때 예외가 발생하게 된 것 같습니다.

따라서 저는 조금 다른 방식으로 다시 풀기 시작하였습니다.
아래는 개선된 풀이 순서입니다.

각각 다른 인덱스의 숫자끼리 더하여 합계를 저장합니다.
합계 배열을 오름차순 정렬합니다.
기준이 되는 변수을 sum[0]으로 초기화 시킵니다.
기준이 되는 변수가 합계 배열의 n번째 방의 값과 같지 않을 경우, 기준값을 업데이트하고 겹치지 않는 합계값의 개수를 구합니다.
정답 배열을 만듭니다. 이 때, 겹치지 않는 합계값+1을 해주는 것이 중요합니다. 자세한 풀이는 아래에서 다시 설명하겠습니다.
서로 겹치지 않는 합계를 찾아 정답 배열에 저장하여 반환합니다.

    public int[] solution(int[] numbers) {
        int[] sum = new int[numbers.length*numbers.length-numbers.length];
        int idx = 0;
        for ( int i = 0; i < numbers.length; i++) {
            for ( int j = 0; j < numbers.length; j++) {
                if ( i != j )
                    sum[idx++] = numbers[i] + numbers[j];
            }
        }

주어진 숫자배연 numbers길이의 제곱만큼의 sum배열을 만들어줍니다.
이는 이중 for문을 사용하기 때문입니다.

이 때 numbers.length만큼 다시 빼주어야 합니다.
만약 빼주지 않는다면 인덱스가 같음으로 인해 합계가 계산이 되지 않은 0값을 포함하게 되므로 쓰레기 값이 생겨나게 됩니다.

이중 for문을 사용하여 인덱스가 다른 numbers의 값일 경우 둘의 값을 더하여 sum에 저장합니다.
이 때 sum의 인덱스인 idx를 1증가시킵니다.

        for ( int i = 0; i < sum.length; i++) {
            for ( int j = 1; j < sum.length; j++) {
                if ( sum[j-1] > sum[j] ) {
                    int tmp = sum[j-1];
                    sum[j-1] = sum[j];
                    sum[j] = tmp;
                }
            }
        }

구한 합계인 sum을 오름차순 정렬시킵니다.
java.util.Arrays를 import하여 Arrays.sort(sum);으로도 구현할 수 있습니다.

        int std = sum[0];
        int cnt = 0;
        for ( int i = 1; i < sum.length; i++) {
            if ( std != sum[i]) {
                cnt++;
                std = sum[i];
            }
        }

이제 중복이 없는 합계의 수를 구할 것입니다.
이러한 절차는 정답 배열의 길이를 정하기 위해 필요합니다.

기준값이 될 std를 sum[0]으로 초기화를 시켜 비교가 가능하도록 만들어줍니다.
중복되지 않는 sum[i]값의 개수를 판단할 cnt변수를 0으로 초기화시킵니다.

for문을 통해 만약 기준값이 sum[i]과 같지 않다면 중복된 값이 아니므로 cnt++하고 기준값을 sum[i]로 변경시킵니다.

이렇게 저희는 정답 배열을 만들 수 있는 길이값을 구하는 것에 성공하였습니다.

        int[] answer = new int[cnt+1];
        answer[0] = sum[0];
        idx = 1;
        for ( int i = 0; i < sum.length; i++) {
            if ( answer[idx-1] != sum[i]) {
               answer[idx++] = sum[i];
            }
        }
        return answer;

정답 배열인 answer의 길이를 cnt+1로 설정합니다.
애먹었던 부분이었는데요, cnt만을 길이로 가지게 된다면 앞서 보았던 int std = sum[0];의 개수를 무시하게 됩니다.
지금 보니 앞의 cnt값을 1로 초기화를 시켜도 될 것 같군요!

다시금 answer에 있는 값과 sum[i]값을 비교하여 겹치지 않을 시에 answer[idx]방에 넣어준 뒤 idx++을 수행합니다.

이렇게 answer에는 오름차순 정렬이 된 겹치지 않는 합의 값들이 담겨지게 되는 것입니다.

📌소스 코드

class Solution {
    public int[] solution(int[] numbers) {
        int[] sum = new int[numbers.length*numbers.length-numbers.length];
        int idx = 0;
        for ( int i = 0; i < numbers.length; i++) {
            for ( int j = 0; j < numbers.length; j++) {
                if ( i != j )
                    sum[idx++] = numbers[i] + numbers[j];
            }
        }
        for ( int i = 0; i < sum.length; i++) {
            for ( int j = 1; j < sum.length; j++) {
                if ( sum[j-1] > sum[j] ) {
                    int tmp = sum[j-1];
                    sum[j-1] = sum[j];
                    sum[j] = tmp;
                }
            }
        }
        int std = sum[0];
        int cnt = 1;
        for ( int i = 1; i < sum.length; i++) {
            if ( std != sum[i]) {
                cnt++;
                std = sum[i];
            }
        }
        int[] answer = new int[cnt];
        answer[0] = sum[0];
        idx = 1;
        for ( int i = 0; i < sum.length; i++) {
            if ( answer[idx-1] != sum[i]) {
               answer[idx++] = sum[i];
            }
        }
        return answer;
    }
}