두 개 뽑아서 더하기 (월간 코드 챌린지 시즌1)

문제

코드

class Solution {
    public int[] solution(int[] numbers) {
        int[] arr=new int[201];
        for(int i=0;i<201;i++){
            arr[i]=-1;
        }

        int size=numbers.length;
        int sum,index;
    
        for(int i=0;i<size-1;i++){
            for(int j=i;j!=size-1;j++){
                index=j+1;
                sum=numbers[i]+numbers[index];
                arr[sum]=sum;
            }
        }

        int answerSize=0;
        for(int i=0;i<201;i++){
            if(arr[i]!=-1)
                answerSize++;
        }
        int[] answer= new int[answerSize];
    
        int answerIndex=0;
        for(int i=0;i<201;i++){
            if(arr[i]!=-1){
                answer[answerIndex]=arr[i];
                answerIndex++;
            }
        }
        return answer;
    }
    
}

풀이

문제 자체는 크게 어렵지 않았다.
어떻게 시간복잡도를 줄일지가 관건이었다.
출력 결과에는 정렬이 되어있어야 하고, 중복을 포함하면 안된다.
이 두가지를 모두 성립시키면서 시간복잡도를 줄일 수 있는 방법을 생각하고자 하였다.
numbers의 모든 수는 0이상 100이하 라는 조건이 있기 때문에,
어느 수를 뽑아도 합의 범위는 0~200 사이가 된다.
그래서 크기가 201개인 "arr"이라는 이름의 배열을 만들어 준 후 모두 -1로 초기화 해 주었고,
numbers에서 차례대로 두 수를 뽑아 만든 합을 "arr" 배열에 넣어주었다. ex)합이 10이면 arr[10]=10 으로 저장해 주었다.
이렇게 하면 자연스럽게 오름차순 정렬이 되면서, 중복된 값은 같은 배열 인덱스에 두번 초기화 되기 때문에 중복이 될 일도 없었다.

이런 방식으로 arr 배열에 모든 수의 합을 저장해두었다.
마지막으로, 반환 결과인 answer 배열을 만들어 주어야 하는데, 여기서는 arr배열의 모든 값중 -1이 아닌 값들만 골라서 새로 넣어주면 문제에서 요구하는 반환값을 만들 수 있다.

결과

출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges