[백준/JAVA] 해시를 사용한 집합과 맵 1920 수 찾기

나의 답) 592ms

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(Integer.parseInt(st.nextToken()));
        }
        
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] comp = new int[m];
        for (int i = 0; i < m; i++) {
            comp[i] = Integer.parseInt(st.nextToken());
        }
        
        for (int i = 0; i < m; i++) {
            if (set.contains(comp[i])) {
                sb.append("1").append("\n");
            } else {
                sb.append("0").append("\n");
            }
        }
        
        System.out.print(sb);
    }
}

 

해당 문제는 특정 정수의 존재 여부만 확인하면 된다.

따라서 데이터의 순서가 중요하지 않기에 Set을 사용하였다.

 

평균 시간 복잡도: O(1)

 

개선 가능 사항

1. com 배열 불필요

: comp 배열은 단순히 값을 저장했다가 set에서 확인하는 용도로만 사용된다.

대신, st.nextToken()을 바로 set.contains()로 확인하면 메모리를 절약할 수 있다.

 

2.가독성 개선

: 변수명은 코드의 의도를 더 명확히 하기 위해 조금 더 구체적으로 설정할 수 있다.

 

 

개선된 코드) 552ms

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        HashSet<Integer> set = new HashSet<>();
        while(st.hasMoreTokens()) {
            set.add(Integer.parseInt(st.nextToken()));
        }
        
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        while(st.hasMoreTokens()) {
            int num = Integer.parseInt(st.nextToken());
            if (set.contains(num)) sb.append("1\n");
            else sb.append("0\n");
        }
        
        System.out.print(sb);
    }
}