[백준 10815] 숫자 카드 JAVA

 

 

 

---

 

 

 

처음 짠 코드는 시간복잡도가 O(n * m) 이라 시간 초과 당했다...

 

아래가 처음 코드

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = 0, m = 0;
		int a = 0;
		
		n = sc.nextInt();
		int[] nArr = new int [n];
		
		for (int i = 0; i < nArr.length; i++) {
			nArr[i] = sc.nextInt();
		}
		
		m = sc.nextInt();
		int[] mArr = new int [m];
		for (int i = 0; i < mArr.length; i++) {
			mArr[i] = sc.nextInt();
		}
		
		for (int i = 0; i < mArr.length; i++) {
			for (int j = 0; j < nArr.length; j++) {
				if(mArr[i] == nArr[j]) {
					System.out.print("1 ");
					a = 1;
				}
			}
			if(a != 1) {
				System.out.print("0 ");
			}
			a = 0;
		}
	}
}

 

 

 

질문 게시판에 나와 같이 시간 초과 당한 사람들이 많았는데, 답변 보니 해시 셋을 사용하라더라.

해시 셋이 뭔지 몰랐는데,, 이번 문제 풀면서 공부 좀 했다.

 

 

대충 알아본 HashSet의 특징은 이랬다.

 

 

• 중복을 허용하지 않는다.
• null을 허용한다.
• 해시 테이블을 사용한다.
• O(1)의 시간복잡도를 가진다.
• 삽입 순서를 보장하지 않는다.
• 삽입 순서를 보장하려면 LinkedHashSet을 사용해야 한다.

 

 

HsahSet을 이용하여 새롭게 코드를 작성해봤다.

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = 0, m = 0;

		n = sc.nextInt();
		int[] nArr = new int[n];

		Set<Integer> nSet = new HashSet<>();
		for (int i = 0; i < nArr.length; i++) {
			nArr[i] = sc.nextInt();
			nSet.add(nArr[i]);
		}

		m = sc.nextInt();
		int[] mArr = new int[m];

		for (int i = 0; i < mArr.length; i++) {
			mArr[i] = sc.nextInt();
		}

		for (int i = 0; i < mArr.length; i++) {
			if (nSet.contains(mArr[i])) {
				System.out.print("1 ");
			} else {
				System.out.print("0 ");
			}
		}
	}
}

 

 

이 코드는 O(n + m)의 시간복잡도를 가진다. 전보다 확실히 시간 복잡도가 작아졌다.

 

 

 

채점 결과