[백준/BOJ] 1920번 : 수 찾기 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

1920번: 수 찾기

---

- 문제 -

 

난이도 실버 4 문제이다.

 

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

솔직히 출제자 의도는 이분탐색을 사용해 시간초과를 해결하는 것을 보고 싶었을지도 모른다...

하지만 필자의 실력이 출중하지 못해서인지 이 방법밖에 생각나지 않았다...

 

함수에는 특정 값이 포합되어있는지 확인하는 contains라는 함수가 있다.

하지만 list를 쓰느냐 set을 쓰느냐 다른 어떤것을 쓰냐에 따라서 시간복잡도가 다르다. 대표적으로 많이 쓰는게 list인데 list에서 contains의 시간 복잡도는 O(n)이다. 해보면 안다 시간초과 뜬다.

set에서의 contains는 O(1)이다. 빠르다. 좋다.

HashSet을 사용해 풀자. 이분탐색을 사용해 풀고자 하는 분은 참고만하자. 이렇게도 풀 수 있단걸.

 

코드로 보자.

---

-풀이-

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		HashSet<Integer> hash = new HashSet<Integer>();
		
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			hash.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());
			
			if(hash.contains(num) == true) sb.append(1).append("\n");
			else sb.append(0).append("\n");
		}
		System.out.println(sb);
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.