๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/1620
- ์ฒซ์งธ ์ค์๋ ๋๊ฐ์ ์๋ก๋์ด ์๋ ํฌ์ผ๋ชฌ์ ๊ฐ์ N์ด๋ ๋ง์ถฐ์ผ ํ๋ ๋ฌธ์ ์ ๊ฐ์ M์ด ์ฃผ์ด์ ธ. N๊ณผ M์ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์
- ํฌ์ผ๋ชฌ์ ์ด๋ฆ์ ๋ชจ๋ ์์ด๋ก๋ง ์ด๋ฃจ์ด์ ธ์์ (์ฒซ ๊ธ์๋ง ๋๋ฌธ์์ด๊ณ , ๋๋จธ์ง ๋ฌธ์๋ ์๋ฌธ์๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ผ๋ ์ผ๋ถ ํฌ์ผ๋ชฌ์ ๋ง์ง๋ง ๋ฌธ์๋ง ๋๋ฌธ์์ผ ์๋ ์์)
- ํฌ์ผ๋ชฌ ์ด๋ฆ์ ์ต๋ ๊ธธ์ด๋ 20, ์ต์ ๊ธธ์ด๋ 2
- ๊ทธ ๋ค์ ์ค๋ถํฐ ์ด M๊ฐ์ ์ค์ ๋ง์ถฐ์ผํ๋ ๋ฌธ์ ๊ฐ ์ ๋ ฅ์ผ๋ก ๋ค์ด์ด
- ๋ฌธ์ ๊ฐ ์ํ๋ฒณ์ผ๋ก๋ง ๋ค์ด์ค๋ฉด ํฌ์ผ๋ชฌ ๋ฒํธ๋ฅผ ๋งํด์ผ ํ๊ณ , ์ซ์๋ก๋ง ๋ค์ด์ค๋ฉด, ํฌ์ผ๋ชฌ ๋ฒํธ์ ํด๋นํ๋ ๋ฌธ์๋ฅผ ์ถ๋ ฅํด์ผํจ
- ์ ๋ ฅ์ผ๋ก ๋ค์ด์ค๋ ์ซ์๋ ๋ฐ๋์ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ฑฐ๋ N๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์
- ์ ๋ ฅ์ผ๋ก ๋ค์ด์ค๋ ๋ฌธ์๋ ๋ฐ๋์ ๋๊ฐ์ ์๋ ํฌ์ผ๋ชฌ์ ์ด๋ฆ๋ง ์ฃผ์ด์ง
์์ด๋์ด
- hashmap์ ์ฌ์ฉํ์ฌ key๊ฐ์ผ๋ก value๋ฅผ ์ฐพ๋ ๋ฐฉ๋ฒ์ ์ฑํํ๋ค.
- ํฌ์ผ๋ชฌ ์ด๋ฆ์ธ ๋ฌธ์์ด๋ก ๋ฒํธ๋ฅผ ์ฐพ์ ์๋ ์๊ณ ํฌ์ผ๋ชฌ ๋ฒํธ์ธ ์ซ์๋ก ์ฐพ์ ์๋ ์๊ธฐ ๋๋ฌธ์ hashmap์ ๋๋ฒ ์จ์คฌ๋ค.(key ๊ฐ์ด String ์ธ hashmap๊ณผ Integer์ธ hashmap)
- ์ ๋ ฅ๊ฐ์ ๋ฌด์กฐ๊ฑด String์ผ๋ก ๋ฐ๊ธฐ์ (๋ด ๋ฐฉ๋ฒ์ ๊ทธ๋ ๋ค..) key ๊ฐ์ด ๋ฌธ์์ด์ธ์ง ์ซ์์ธ์ง ๊ตฌ๋ถํ๊ธฐ ์ํด ๋ฌธ์์ด ์ ์ผ ์๋ถ๋ถ์ ๋ฌธ์๋ก ๋ฐ๊ฟ์ ์์คํค์ฝ๋๋ก ๋๋ฌธ์์ธ์ง ๊ฐ๋ณํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- ์ฒ์์๋ hashmap์ ์๊ฐํ์ง ๋ชปํ๊ณ ๋ฐ๋ณต๋ฌธ์ ์ฌ์ฉํด์ ๋ฌธ์์ด์ ๋น๊ตํด์ ์ฐพ๋ ๋ฐฉ๋ฒ์ ์ฌ์ฉํด, ์๊ฐ์ด๊ณผ๊ฐ ๋ฌ๋ค.....
์ฝ๋
import java.io.*;
import java.util.*;
// hashmap ์ฌ์ฉ
// ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ ๋ key์ value๊ฐ ์ง์ ์ด๋ฃจ์ด ์ ์ฅ๋จ
// ํค ๊ฐ์ผ๋ก hash ํจ์๋ฅผ ์คํํ ๊ฒฐ๊ณผ๋ฅผ ํตํด ์ ์ฅ์์น๋ฅผ ๊ฒฐ์
// ์ถ๊ฐ, ์ญ์ , ํนํ ๊ฒ์์ด ๋น ๋ฆ
public class BOJ1620 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
// ํฌ์ผ๋ชฌ ๋๊ฐ ์
int list = Integer.parseInt(st.nextToken());
// ๋ง์ถฐ์ผ ๋๋ ๋ฌธ์ ์
int test = Integer.parseInt(st.nextToken());
// Hashmap์ key๊ฐ๊ณผ value ๊ฐ์ ์ฌ์ฉํ์ฌ ์ ์ฅ
// ์ด๋ฆ์ผ๋ก ์ฐพ๋ ๊ฒฝ์ฐ์ ๋ฒํธ๋ก ์ฐพ๋ ๊ฒฝ์ฐ ๋๊ฐ์ง๊ฐ ์๊ธฐ ๋๋ฌธ์ ๋๋ฒ ์ ์ฅ
HashMap<String, Integer> poket = new HashMap<String, Integer>(list);
HashMap<Integer, String> poket2 = new HashMap<Integer, String>(list);
for(int i = 1; i < list + 1; i++){
// ๋๊ฐ์ ๋ฑ๋ก๋ ํฌ์ผ๋ชฌ ์ด๋ฆ
String s = br.readLine();
// ๋๊ฐ์ ๋ฑ๋ก
poket.put(s, i);
poket2.put(i, s);
}
for(int i = 0; i < test; i++){
String s = br.readLine();
// ํ
์คํธํ๋ ๋ฌธ์ ๊ฐ ๋ฒํธ์ธ์ง ์ด๋ฆ์ธ์ง ์๊ธฐ ์ํด์
// ์ฒซ ๋ฌธ์๋ฅผ ๋ผ์ ์์คํค์ฝ๋๋ก ๋น๊ตํ๊ธฐ ์ํด ๋ณํ
int ch = (int)s.charAt(0);
// ์์คํค์ฝ๋๋ก ๋น๊ตํด์ ๋๋ฌธ์์ผ ๊ฒฝ์ฐ,
// ๋๊ฐ์์ key ๊ฐ์ธ ์ด๋ฆ์ผ๋ก value ๊ฐ์ธ ๋ฒํธ ์ฐพ์์ ์ ์ฅ
if((65 <= ch) && (ch <= 90)){
int n = poket.get(s);
sb.append(n + "\n");
}
// ์ฒซ ๋ฌธ์๊ฐ ๋๋ฌธ์๊ฐ ์๋ ๊ฒฝ์ฐ,
else{
// ๋ฌธ์์ด๋ก ๋ฐ์์ผ๋ฏ๋ก int๋ก ๋ณํ
int num = Integer.parseInt(s);
// ๋๊ฐ์์ key ๊ฐ์ธ ๋ฒํธ๋ก value ๊ฐ์ธ ํด๋น ํฌ์ผ๋ชฌ ์ด๋ฆ์ ์ฐพ์ ์ ์ฅ
String po = poket2.get(num);
sb.append(po + "\n");
}
}
System.out.println(sb);
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 2231 ๋ถํดํฉ (0) | 2024.07.10 |
---|---|
[Java] BOJ 1978 ์์ ์ฐพ๊ธฐ (0) | 2024.07.09 |
[Java] BOJ 30802 ์ฐ์ปดํคํธ (0) | 2024.07.09 |
[Java] BOJ 4153 ์ง๊ฐ์ผ๊ฐํ (0) | 2024.07.09 |
[Java] BOJ 11723 ์งํฉ (2) | 2024.07.08 |