[Java] baekjoon_1920 : 수 찾기

자료 구조, 정렬, 이분 탐색

수 찾기 : Silver4

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

1920번: 수 찾기

 

 

두 번째 코드 작성

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

public class Main {
  public static void main(String[] args) throws Exception {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    ArrayList<Integer> arr1 = new ArrayList<>();
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
      arr1.add(Integer.parseInt(st.nextToken()));
    }
    int M = Integer.parseInt(br.readLine());
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < M; i++) {
      if (arr1.contains(Integer.parseInt(st.nextToken()))) {
        bw.write(String.valueOf(1));
        bw.newLine();
      } else {
        bw.write(String.valueOf(0));
        bw.newLine();
      }
    }

    bw.flush();
    bw.close();
  }
}

 

ㄴ 시간초과가 발생되는 문제가 있었다.

ㄴ ArrayList 에 매우 많은 데이터가 들어가게 되어 for 문을 실행 시 큰 시간 복잡도가 발생하였다.

 

두 번째 코드 작성

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

public class Main {
  public static void main(String[] args) throws Exception {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    HashSet<Integer> arr1 = new HashSet<>();
    for (int i = 0; i < N; i++) {
      arr1.add(Integer.parseInt(st.nextToken()));
    }
    int M = Integer.parseInt(br.readLine());
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < M; i++) {
      if (arr1.contains(Integer.parseInt(st.nextToken()))) {
        bw.write(String.valueOf(1));
        bw.newLine();
      } else {
        bw.write(String.valueOf(0));
        bw.newLine();
      }
    }

    bw.flush();
    bw.close();
  }
}

 

ㄴ ArrayList를 HashSet으로 변경하여 for 문을 실행 시 큰 시간 복잡도를 줄였다.

ㄴ 하지만 코드 가독성이 떨어지므로 다른 방법을 생각해보았다.

 

세 번재 코드 작성

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer 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());

        for (int i = 0; i < M; i++) {
          int num = Integer.parseInt(st.nextToken());
          bw.write(set.contains(num) ? String.valueOf(1) : String.valueOf(0));
          bw.newLine();
        }
        bw.flush();
        bw.close();
    }
}

 

ㄴ 코드 가독성을 높이기위해 삼항연산을 이용하였다.

 

 

입력 데이터의 크기가 큰 경우에는 더 효율적인 알고리즘을 사용해야 한다.

ArrayList의 contains 메서드는 선형 검색을 수행하므로 시간 복잡도가 O(N)이며, 이는 큰 입력에 대해서는 비효율적일 수 있다.
이를 해결하기 위해 HashSet을 사용하면 보다 효율적으로 중복 여부를 확인할 수 있다.

HashSet은 검색 연산이 상수 시간(complexity)에 이루어지기 때문에 시간 복잡도가 낮습니다.

 

---

 

 

문제점 : 디버깅 시 정상 출력되지만 채점 시 시간초과가 되는 것을 확인하였다.

해결 방법 : ArrayList를 이용해 입력된 수를 모두 받았던 것을 HashSet을 이용해 중복을 제거하여 반복을 줄였다. 또한, 코드 가독성을 위해 if문 대신 삼항 연산을 이용하였다.

깨달은 바 : 입력 데이터의 크기가 큰 경우에는 더 효율적인 알고리즘을 이용하도록 생각해야겠다. 또한, 코드 가독성을 위해 다양한 방법을 생각해보아야겠다.