[백준] 3052번 나머지 / HashSet을 사용하여 해결해보자

 

1. 배열에 값을 모두 넣은 후 나중에 중복을 확인하는 방법

2.값을 배열에 넣기 전에 중복을 확인하는 방법에 대해 시간 복잡도를 지피티에게 물어봤습니다.

 

결론은 해쉬셋을 써라.

 

하.. 해쉬셋을 많이 안써봐서 뇌에서 바로 안나옴. 자료구조 시간에 썼으려나...

개념은 아는데 막상 활용까지 안이어지는게 탄식만 나온다.

 

 

1번 방법으로 배열에 넣었다  비교를 하게되면 코드짜는거야 간단해지지만

-배열에 넣는시간 O(n)(n은 배열의 크기)

-중복확인을 위해 배열을 비교하는 시간 O(n²) 이 걸림.

 

배열의 크기가 커질수록 시간이 급격히 늘어난다.

 

2번 방법 (값을 넣으면서 중복확인)

마찬가지로 최악의 경우(모두 확인) O(n), 중복확인  O(n²)

 

...

 

 

 

나보고 Set 자료구조를 사용하란다.

미ㅣ안 !

import java.util.HashSet;
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		HashSet<Integer> set = new HashSet<>();
		int count =0;
		for(int i=0;i<10;i++) {
			int n = scan.nextInt();
			int num = n%42;
			if(set.contains(num)) {
				continue;
			}else {
				set.add(num);
				count++;
			}
		}
		System.out.println(count);
	
	}
}

완.