ํด๋น์ด๋ ํจ์ ์ ๋งค์ฐ ๋ฏผ๊ฐํด์ ํ๋ฒ ์ ์๋ ์ท๋ค์ ์กฐํฉ์ ์ ๋ ๋ค์ ์ ์ง ์๋๋ค. ์๋ฅผ ๋ค์ด ์ค๋ ํด๋น์ด๊ฐ ์๊ฒฝ, ์ฝํธ, ์์, ์ ๋ฐ์ ์ ์๋ค๋ฉด, ๋ค์๋ ์ ๋ฐ์ง๋ฅผ ์ถ๊ฐ๋ก ์ ๊ฑฐ๋ ์๊ฒฝ๋์ ๋ ์ฆ๋ฅผ ์ฐฉ์ฉํ๊ฑฐ๋ ํด์ผํ๋ค. ํด๋น์ด๊ฐ ๊ฐ์ง ์์๋ค์ด ์ฃผ์ด์ก์๋ ๊ณผ์ฐ ํด๋น์ด๋ ์๋ชธ์ด ์๋ ์ํ๋ก ๋ฉฐ์น ๋์ ๋ฐ์ ๋์๋ค๋ ์ ์์๊น?
์ ๋ ฅ
์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค๊ฐ ์ฃผ์ด์ง๋ค. ํ ์คํธ ์ผ์ด์ค๋ ์ต๋ 100์ด๋ค.
- ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ์ฒซ์งธ ์ค์๋ ํด๋น์ด๊ฐ ๊ฐ์ง ์์์ ์ n(0 โค n โค 30)์ดย ์ฃผ์ด์ง๋ค.
- ๋ค์ n๊ฐ์๋ ํด๋น์ด๊ฐ ๊ฐ์งย ์์์ ์ด๋ฆ๊ณผ ์์์ ์ข ๋ฅ๊ฐ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด ์ฃผ์ด์ง๋ค. ๊ฐ์ ์ข ๋ฅ์ ์์์ ํ๋๋ง ์ ์ ์ ์๋ค.
๋ชจ๋ ๋ฌธ์์ด์ 1์ด์ 20์ดํ์ ์ํ๋ฒณ ์๋ฌธ์๋ก ์ด๋ฃจ์ด์ ธ์์ผ๋ฉฐ ๊ฐ์ ์ด๋ฆ์ ๊ฐ์ง ์์์ ์กด์ฌํ์ง ์๋๋ค.
์ถ๋ ฅ
๊ฐ ํ ์คํธ ์ผ์ด์ค์ ๋ํด ํด๋น์ด๊ฐ ์๋ชธ์ด ์๋ ์ํ๋ก ์์์ ์ ์ ์ ์๋ ๊ฒฝ์ฐ๋ฅผ ์ถ๋ ฅํ์์ค.
๐ก (์ข
๋ฅ, ์ด๋ฆ) ์ hash ๊ฐ์ผ๋ก ์ ์ฅ
๐ก ๊ทธ ์ข
๋ฅ์ ์ท์ด ์๋ค๋ฉด 2(์ ์
์ ๊ฒ ํฌํจ)๋ฅผ ์ ์ฅ ์๋ค๋ฉด ๊ฐ์๋ฅผ ๋นผ์์ +1ํด์ฃผ๊ณ ๋ฃ์
๐ก key ๊ฐ์ ๊ธฐ์ค์ผ๋ก value๋ฅผ ๋ชจ๋ ๊ณฑํ ํ -1(์๋ฌด๊ฒ๋ ์์
์ ์ํ)์ ํด์ค
if(map.containsKey(s[1])) {
map.put(s[1], map.get(s[1])+1);
} else {
map.put(s[1], 2);
}
for(String key :map.keySet()) {
ret *= map.get(key);
}
...
sb.append(Integer.toString(ret-1));
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
public class BOJ_9375 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
int tc = Integer.parseInt(br.readLine());
while(tc-->0) {
HashMap<String, Integer> map = new HashMap<>();
int n = Integer.parseInt(br.readLine());
int ret = 1;
for(int i=0; i<n; i++) {
String[] s = br.readLine().split(" ");
if(map.containsKey(s[1])) {
map.put(s[1], map.get(s[1])+1);
} else {
map.put(s[1], 2);
}
}
for(String key :map.keySet()) {
ret *= map.get(key);
}
sb.append(Integer.toString(ret-1));
sb.append("\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
}
}
์ฑ๊ณตโจ