[Algorithm] ๐ŸŽด๋ฐฑ์ค€ 10816 ์ˆซ์ž ์นด๋“œ 2

0. ๋ฌธ์ œ

์ˆซ์ž ์นด๋“œ๋Š” ์ •์ˆ˜ ํ•˜๋‚˜๊ฐ€ ์ ํ˜€์ ธ ์žˆ๋Š” ์นด๋“œ์ด๋‹ค. ์ƒ๊ทผ์ด๋Š” ์ˆซ์ž ์นด๋“œ N๊ฐœ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ์ •์ˆ˜ M๊ฐœ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด ์ˆ˜๊ฐ€ ์ ํ˜€์žˆ๋Š” ์ˆซ์ž ์นด๋“œ๋ฅผ ์ƒ๊ทผ์ด๊ฐ€ ๋ช‡ ๊ฐœ ๊ฐ€์ง€๊ณ  ์žˆ๋Š”์ง€ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ
์ฒซ์งธ ์ค„์— ์ƒ๊ทผ์ด๊ฐ€ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์ˆซ์ž ์นด๋“œ์˜ ๊ฐœ์ˆ˜ N(1 โ‰ค N โ‰ค 500,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ์ˆซ์ž ์นด๋“œ์— ์ ํ˜€์žˆ๋Š” ์ •์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ˆซ์ž ์นด๋“œ์— ์ ํ˜€์žˆ๋Š” ์ˆ˜๋Š” -10,000,000๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 10,000,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™๋‹ค.

์…‹์งธ ์ค„์—๋Š” M(1 โ‰ค M โ‰ค 500,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋„ท์งธ ์ค„์—๋Š” ์ƒ๊ทผ์ด๊ฐ€ ๋ช‡ ๊ฐœ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์ˆซ์ž ์นด๋“œ์ธ์ง€ ๊ตฌํ•ด์•ผ ํ•  M๊ฐœ์˜ ์ •์ˆ˜๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, ์ด ์ˆ˜๋Š” ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด์ ธ ์žˆ๋‹ค. ์ด ์ˆ˜๋„ -10,000,000๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 10,000,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™๋‹ค.

์ถœ๋ ฅ
์ฒซ์งธ ์ค„์— ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ M๊ฐœ์˜ ์ˆ˜์— ๋Œ€ํ•ด์„œ, ๊ฐ ์ˆ˜๊ฐ€ ์ ํžŒ ์ˆซ์ž ์นด๋“œ๋ฅผ ์ƒ๊ทผ์ด๊ฐ€ ๋ช‡ ๊ฐœ ๊ฐ€์ง€๊ณ  ์žˆ๋Š”์ง€๋ฅผ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ํ•ด ์ถœ๋ ฅํ•œ๋‹ค.

1. ์•„์ด๋””์–ด

HashMap ์ด์šฉ
๐Ÿ’ก ์นด๋“œ์˜ ์ˆซ์ž๋ฅผ key๊ฐ’์œผ๋กœ ์ด์šฉ
๐Ÿ’ก ์ฒ˜์Œ ๋‚˜์˜จ ์ˆซ์ž๋Š” value์— 1 ์ €์žฅ, ์ด๋ฏธ ๋‚˜์™”๋˜ ์ˆซ์ž๋Š” value์— value+1์„ ์ €์žฅ
๐Ÿ’ก m์˜ ์ˆซ์ž๊ฐ€ key ๊ฐ’์œผ๋กœ ์žˆ๋Š”์ง€ ํ™•์ธ ํ›„์— value ์ถœ๋ ฅ

2. ํ•ต์‹ฌ ํ’€์ด

1) ์ฒ˜์Œ ๋‚˜์˜จ ์ˆซ์ž๋Š” value์— 1 ์ €์žฅ, ์ด๋ฏธ ๋‚˜์™”๋˜ ์ˆซ์ž๋Š” value์— value+1์„ ์ €์žฅ

if(map.containsKey(num)) {
	map.put(num,map.get(num)+1);
} else {
	map.put(num, 1);
}

2) m์˜ ์ˆซ์ž๊ฐ€ key ๊ฐ’์œผ๋กœ ์žˆ๋Š”์ง€ ํ™•์ธ ํ›„์— value ์ถœ๋ ฅ

if(map.containsKey(num))
	sb.append(map.get(num));
else
	sb.append("0");
sb.append(" ");

3. ์ฝ”๋“œ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
public class Hash_3 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		HashMap<Integer, Integer> map = new HashMap<>();

		String[] s = br.readLine().split(" ");
		
		for(int i=0; i<n; i++) {
			int num = Integer.parseInt(s[i]);
			
			if(map.containsKey(num)) {
				map.put(num,map.get(num)+1);
			} else {
				map.put(num, 1);
			}
		}
		
		int m = Integer.parseInt(br.readLine());
		s = br.readLine().split(" ");
		StringBuilder sb = new StringBuilder();
		
		for(int i=0; i<m; i++) {
			int num = Integer.parseInt(s[i]);
			
			if(map.containsKey(num))
				sb.append(map.get(num));
			else
				sb.append("0");
			sb.append(" ");
		}
		
		System.out.println(sb.toString());
	}

}

4. ๊ฒฐ๊ณผ

์„ฑ๊ณตโœจ

์ฒ˜์Œ์—๋Š” System.out.println(map.get(num)+" ") ํ–ˆ๋‹ค๊ฐ€ ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋‚ฌ๋‹ค.
+" " ์—ฐ์‚ฐ์€ ์‹œ๊ฐ„์„ ๋งŽ์ด ์žก์•„๋จน๋Š”๋‹ค๊ณ  ํ•œ๋‹ค.
์ด์ œ๋ถ€ํ„ฐ StringBuilder๋‚˜ BufferedWriter๋ฅผ ์ž˜ ํ™œ์šฉํ•ด์•ผ ๊ฒ ๋‹ค...

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ