[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๋ฅผ ์ ํ์ฉํด์ผ ๊ฒ ๋ค...
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐ด๋ฐฑ์ค 10816 ์ซ์ ์นด๋ 2), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-๋ฐฑ์ค-10816-์ซ์-์นด๋-2์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค