[ etc ] #18 : 두 개의 수로 특정값 만들기 - JAVA

문제 설명

n개의 양의 정수로 이루어진 배열 arr와 정수 target이 주어졌을 때 이 중에서 합이 target인 두 수가 arr에 있는지 찾고 있으면 true, 없으면 false를 반환하는 solution()함수를 작성하세요.

 

제약 조건

• n은 2이상 10,000 이하의 자연수입니다.
• arr의 각 원소는 1 이상 10,000 이하의 자연수 입니다.
• arr의 원소 중 중복되는 원소는 없습니다.
• target은 1이상 20,000 이하의 자연수 입니다.

 

입출력 예

arr	target	return
[1,2,3,4,8]	6	true
[2,3,5,9]	10	false

 

문제 풀이

• arr에서 임의의 원소 x에 대해 x+k=target이 되는 원소 k가 arr에 있는지 확인하기
• 즉, hash set에 (target-arr원소) 가 있으면 target을 만들 수 있는 두 수가 arr에 있는 것과 같다.

※ HashMap은 키-값 쌍으로 데이터를 저장, HashSet은 키만 저장, 현재 문제에서는 키만 필요하므로 HashSet 사용함

 

 

import java.util.HashSet;
public class Java18 {
    public static boolean solution(int[]arr,int target){

        HashSet<Integer> set = new HashSet<>();
        // 1. (target - 현재원소값) 이 해시셋에 있는지 확인
        for(int i: arr){
            if(set.contains(target-i)){ // O(1)
                return true;
            }
            // 해시셋에 현재 값 저장
            set.add(i); // O(1)
        }

        return false;

        // 최종 O(N)
    }

    public static void main(String[] args) {
        int [] arr1={1,2,3,4,8};
        int target1=6;
        boolean result1=solution(arr1,target1);
        System.out.println("arr1, target1 에 대한 반환값 : "+result1);
        int[]arr2={2,3,5,9};
        int target2=10;
        boolean result2=solution(arr2,target2);
        System.out.println("arr2, target3 에 대한 반환값 : "+result2);

    }
}