[백준 - 3273 JAVA] 두 수의 합 : set 2개 사용

주어진 문제의 조건이 서로 다른 양의 정수였기 때문에 중복 고려를 하지 않아도 되고, 이미 한번 연산한 내용에대해서는 따로 체크할 필요가 없기때문에 Contains 의 시간복잡도가 O(1)인 Set을 사용하기로 하였다. Set중 HashSet은 중복 저장하지않고, 순서 없이 저장되지만 속도는 빠르기때문에 자바로 문제푸는 본인은 set을 사용하기로 선택! 

 

고려사항 

• 첫번째 입력값으로 주어지는 정수 갯수는...의미가 없었음 -> 한줄로 들어오는 입력 값을 Tokenizer 를 사용하여 분리했음
• 결국엔 (finalNum - 현재 정수) 가 입력된 수열안에 있기만 하면 카운트 증가 
  • 대신 체크한 정수인지 확인하기위해 set을 하나 더 사용하여, 체크된 정수는 set에 저장하여 while 문 안에서 Contains로 확인을 통해 동작 시간을 줄였다.  

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Integer.parseInt(br.readLine());

        StringTokenizer tokenizer = new StringTokenizer(br.readLine());
        Set<Integer> ints = new HashSet<>();
        Set<Integer> resultSet = new HashSet<>();
        while (tokenizer.hasMoreTokens()) {
            ints.add(Integer.parseInt(tokenizer.nextToken()));
        }

        int finalNum = Integer.parseInt(br.readLine());

        int cnt = 0;
        for (int i : ints) {
            if (finalNum <= i || resultSet.contains(i)) {
                continue;
            }

            int result = finalNum - i;

            if (ints.contains(result) && result != i) {
                cnt++;
                resultSet.add(result);
            }
        }
        System.out.println(cnt);
    }
}

 

https://www.acmicpc.net/problem/3273

 

자료구조 속도 참고 : https://www.grepiu.com/post/9