[Java] 백준 알고리즘 10816 번 문제 : 숫자 카드 2 (배열)

---문제---

 

---코드---

 

#1. 첫 번째 시도 (HashMap 구조 이용)

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Bj10816 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		Map<Integer, Integer> number = new HashMap<Integer,Integer>();
		
		for(int i=0; i<N; ++i) {
			int tmp = sc.nextInt();
			if(number.containsKey(tmp)) {
				number.put(tmp,number.get(tmp)+1);
			}else {
				number.put(tmp,1);
			}
		}
		int M = sc.nextInt();		
		for(int i=0; i<M; ++i) {
			int tmp = sc.nextInt();
			if(number.containsKey(tmp)) {
				System.out.printf("%d ",number.get(tmp));
			}
			else {
				System.out.printf("%d ",0);
			}
		}
		
	}

}

-> 처음엔 해쉬 맵 구조를 이용하여 구현하였으나, 시간 초과로 통과하지 못했습니다.

 

#2. 두 번째 시도 (배열 이용)

import java.util.Scanner;

public class Bj10816_2 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] card = new int[20000001];
		for (int i = 0; i < N; ++i) {
			 ++card[sc.nextInt()+10000000] ;
		}
		int M = sc.nextInt();
		
		for (int i = 0; i < M; ++i) {
			System.out.printf("%d ", &card[sc.nextInt()]);
		}		
	}
}

-> 두번째 시도로, 배열을 이용하였더니 메모리 측면에서는 비효율 적이지만 시간 적으로는 더 효율적이 된 것 같습니다.

-> 하지만, 역시나 시간 초과

 

#3. 세 번째 시도 (배열 이용 , StringBuilder 클래스 이용)

import java.util.Scanner;

public class Bj10816_2 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		int[] card = new int[20000001];
		for (int i = 0; i < N; ++i) {
			 ++card[sc.nextInt()+10000000] ;
		}
		int M = sc.nextInt();
		
		for (int i = 0; i < M; ++i) {
			sb.append(card[sc.nextInt()+10000000]+" ");
		}		
		System.out.println(sb.toString());
	}

}

-> 때 마다, 출력하는 게 아니라 StringBuilder 클래스에 모아놨다가 출력하니까 통과되었습니다.

 

---출처---

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

10816번: 숫자 카드 2