[BOJ] 5052 ์ ํ๋ฒํธ ๋ชฉ๋ก
๋ฌธ์
๋ฌธ์ ์ค๋ช
Baekjoon Online Judge - 5052๋ฒ ์ ํ๋ฒํธ ๋ชฉ๋ก
์ ํ๋ฒํธ ๋ชฉ๋ก์ด ์ฃผ์ด์ง๋ค. ์ด๋, ์ด ๋ชฉ๋ก์ด ์ผ๊ด์ฑ์ด ์๋์ง ์๋์ง๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ํ๋ฒํธ ๋ชฉ๋ก์ด ์ผ๊ด์ฑ์ ์ ์งํ๋ ค๋ฉด, ํ ๋ฒํธ๊ฐ ๋ค๋ฅธ ๋ฒํธ์ ์ ๋์ด์ธ ๊ฒฝ์ฐ๊ฐ ์์ด์ผ ํ๋ค.
์๋ฅผ ๋ค์ด, ์ ํ๋ฒํธ ๋ชฉ๋ก์ด ์๋์ ๊ฐ์ ๊ฒฝ์ฐ๋ฅผ ์๊ฐํด๋ณด์
- ๊ธด๊ธ์ ํ: 911
- ์๊ทผ: 97 625 999
- ์ ์: 91 12 54 26
์ด ๊ฒฝ์ฐ์ ์ ์์ด์๊ฒ ์ ํ๋ฅผ ๊ฑธ ์ ์๋ ๋ฐฉ๋ฒ์ด ์๋ค. ์ ํ๊ธฐ๋ฅผ ๋ค๊ณ ์ ์์ด ๋ฒํธ์ ์ฒ์ ์ธ ์๋ฆฌ๋ฅผ ๋๋ฅด๋ ์๊ฐ ๋ฐ๋ก ๊ธด๊ธ์ ํ๊ฐ ๊ฑธ๋ฆฌ๊ธฐ ๋๋ฌธ์ด๋ค. ๋ฐ๋ผ์, ์ด ๋ชฉ๋ก์ ์ผ๊ด์ฑ์ด ์๋ ๋ชฉ๋ก์ด๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ t๊ฐ ์ฃผ์ด์ง๋ค. (1 โค t โค 50) ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ์ฒซ์งธ ์ค์๋ ์ ํ๋ฒํธ์ ์ n์ด ์ฃผ์ด์ง๋ค. (1 โค n โค 10000) ๋ค์ n๊ฐ์ ์ค์๋ ๋ชฉ๋ก์ ํฌํจ๋์ด ์๋ ์ ํ๋ฒํธ๊ฐ ํ๋์ฉ ์ฃผ์ด์ง๋ค. ์ ํ๋ฒํธ์ ๊ธธ์ด๋ ๊ธธ์ด์ผ 10์๋ฆฌ์ด๋ฉฐ, ๋ชฉ๋ก์ ์๋ ๋ ์ ํ๋ฒํธ๊ฐ ๊ฐ์ ๊ฒฝ์ฐ๋ ์๋ค.
์ถ๋ ฅ
๊ฐ ํ ์คํธ ์ผ์ด์ค์ ๋ํด์, ์ผ๊ด์ฑ ์๋ ๋ชฉ๋ก์ธ ๊ฒฝ์ฐ์๋ YES, ์๋ ๊ฒฝ์ฐ์๋ NO๋ฅผ ์ถ๋ ฅํ๋ค.
ํ์ด
ํด์ค
๊ฐ ์ ํ๋ฒํธ์ ์ซ์๋ฅผ ๋ ธ๋๋กํ๋ ํธ๋ผ์ด ์๋ฃ๊ตฌ์กฐ๋ฅผ ํ์ฉํ๋ค.
0~9์ ์ซ์๋ก ์์ํ๋ ์ ํ๋ฒํธ๋ฅผ ๊ฐ๊ฐ 0~9์ ๋
ธ๋์ ๋งํฌ๋ก ์ฐ๊ฒฐํ์ฌ ์ ํ๋ฒํธ ๊ธธ์ด๋งํผ์ ๋
ธ๋๊ฐ ์ฐ๊ฒฐ๋ ํํ๋ก ๋ง๋ ๋ค.
์ด๋ ๊ฐ ํ๋์ ์ ํ๋ฒํธ ์ ์ฅ์ด ๋๋๋ฉด isLeaf๋ผ๋ booleanํ ๋ณ์๋ฅผ ํตํด ๊ฐ ์ ํ๋ฒํธ ๋จ์(์ ๋์ฌ)๊ฐ ์์ฑ๋์์์ ๊ธฐ๋กํด์ผํ๋ค.
์๋ก์ด ์ ํ๋ฒํธ๋ ์์ ๊ฐ์ ๋ฐฉ๋ฒ์ผ๋ก ์ฝ์ ํ๋๋ฐ ๊ฐ ์ซ์์ ํด๋นํ๋ ๋ ธ๋๊ฐ ์ด๋ฏธ ์กด์ฌํ๋ฉด ๋ค๋ฅธ ์ ํ๋ฒํธ์ ์ค๋ณต๋๋ ์์์ ์ ํ๋ฒํธ๋ผ๋ ์๋ฏธ์ด๋ฏ๋ก, ์ค๋ณต๋๋ ๊ธธ์ด๊น์ง๊ฐ ๋ค๋ฅธ ์ ํ๋ฒํธ ๋จ์(์ ๋์ฌ)์ ๊ฒน์น๋์ง isLeaf ๋ณ์๋ก ํ์ธํ๋ค.
๋ง์ฝ ๋ค๋ฅธ ์ ํ๋ฒํธ์ ํต์งธ๋ก ์ผ์นํ๋ ๋ถ๋ถ์ด ์กด์ฌํ๋ค๋ฉด ์ฆ, ์ ๋์ฌ๊ฐ ์ผ์นํ๋ค๋ฉด ์ผ๊ด์ฑ์ด ์๋ ๋ชฉ๋ก์ผ๋ก ํ๋ณํ๋ค.
์ํ์ฐฉ์ค
- ์ฐ์ ํธ๋ผ์ด ์๋ฃ๊ตฌ์กฐ ๊ตฌํ์ ๊ธฐ์ตํ ๋ฆฌ..๊ฐ ์์ด์ ๊ณผ๊ฑฐ์ ์ ๋ฆฌํ ๊ฒ ๋ณด๊ณ ํ
- ๋ํ ์ผ์นํ๋ ์ ๋์ฌ์ธ์ง ํ์ธํ๊ธฐ ์ํด ์ ํ๋ฒํธ์ ์ฒ์๋ถํฐ ํน์ ๊ธธ์ด๊น์ง๊ฐ ๋ค๋ฅธ ์ ํ๋ฒํธ์ ์ผ์นํ๋์ง๋ง ํ์ธํ๋๋ฐ, ์ ๋์ฌ๊ฐ ์ผ์นํ๋ ๊ฒ์ด ์๋๋ผ ์ ํ๋ฒํธ์ ์ผ๋ถ๋ง ์ผ์นํ๋ ๊ฒฝ์ฐ๋ฅผ ์ก์๋ด์ง ๋ชปํด ํ๋ ธ์์..
ex) 123 39940 39950
- ๊ธธ์ด๊ฐ ๋ ๊ธด ๋ฒํธ๋จผ์ ์ ์ฅํ๋ค๋ฉด isLeaf ์ฒดํฌ๋ฅผ ํด๋ ๋ฏธ์ฒ ์ ๋ฏธ์ฌ๋ก ๋ฑ๋ก๋์ง ์์ ๊ฒฝ์ฐ๋ ์ผ์นํ๋ค๊ณ ๋ณด์ง ๋ชปํ๊ธฐ๋๋ฌธ์ ์ ํ๋ฒํธ ๊ธธ์ด๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ์ฅํ ๋ค ํธ๋ผ์ด๋ก ๋ง๋ค์๋ค.
ex) 999999 9999
์ฝ๋
import java.io.*;
import java.util.*;
/**
* [1214] BOJ 5052 ์ ํ๋ฒํธ ๋ชฉ๋ก
* ๋ฌธ์์ด, ํธ๋ผ์ด, ์ ๋์ฌ
*/
public class BOJ_5052_์ ํ๋ฒํธ๋ชฉ๋ก {
static Node root; // ํธ๋ผ์ด ์๋ฃ๊ตฌ์กฐ ๋ฃจํธ ๋
ธ๋
static String[] numbers; // ์ ํ๋ฒํธ๋ฅผ ๊ธธ์ด ์ค๋ฆ์ฐจ์ ์ ๋ ฌํ๊ธฐ ์ํ ๋ฐฐ์ด
// ํธ๋ผ์ด์ ๊ฐ ์ซ์ ๋
ธ๋
public static class Node {
Node[] next; // ํ์ฌ ์ซ์ ๋ฐ๋ก ๋ค์ ์ซ์ ์ข
๋ฅ๋ฅผ ์ ์ฅํ ๋
ธ๋ ๋ฐฐ์ด(0~9)
boolean isLeaf; // ์ ๋์ฌ๊ฐ ์์ฑ๋์๋์ง ์ฌ๋ถ
public Node() {
this.next = new Node[10]; // 0~9๋ก ์ด๊ธฐํ
this.isLeaf = false;
}
}
// ํธ๋ผ์ด ๊ตฌ์กฐ์ ๊ฐ ๋
ธ๋ ์ฝ์
public static boolean insert(char[] inputNums) {
Node curNum = root;
int size = inputNums.length;
boolean isPrefixSame = false;
// ํ๋์ ์ ํ๋ฒํธ์ ๊ฐ ์ซ์๋ฅผ ๋
ธ๋๋ก ์ฐ๊ฒฐํ์ฌ ์ ์ฅ
for (int j=0; j<size; j++) {
int digit = inputNums[j] - '0';
if (curNum.next[digit] == null) { // ํ์ฌ ์ซ์์ ์ฐ๊ฒฐ๋ ๋ค์ ์ซ์์ ํ๋ฆ(์ซ์ ์์)์ด ์ฒ์์ด๋ฉด
curNum.next[digit] = new Node(); // ํ์ฌ ์ซ์์ ํด๋นํ๋ ๋ค์ ์ซ์ ๋
ธ๋๋ฅผ ์์ฑํ์ฌ ์ฐ๊ฒฐ
} else { // ํ์ฌ ์ซ์์ ์ฐ๊ฒฐ๋ ๋ค์ ์ซ์์ ํ๋ฆ(์ซ์ ์์)์ด ๋ค๋ฅธ ์ ํ๋ฒํธ์ ์ํด ์ ์ฅ๋ ์ ์ด ์์ผ๋ฉด
if (curNum.next[digit].isLeaf) isPrefixSame = true; // true ๋ฐํ
}
curNum = curNum.next[digit]; // ๊ธฐ์ค์ด ํ์ฌ ์ซ์์์ ๋ค์ ์ซ์๋ก ๋์ด๊ฐ
}
curNum.isLeaf = true; // ํ๋์ ์ ํ๋ฒํธ ๋จ์๋ฅผ ๋ค ์ ์ฅํ์์ ๊ธฐ๋ก(ํ๋์ ์ ๋์ฌ ์์ฑ)
return isPrefixSame;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while(t-->0) {
// ํธ๋ผ์ด ๋ฃจํธ ๋
ธ๋ ์์ฑ
root = new Node();
int n = Integer.parseInt(br.readLine());
numbers = new String[n];
// ์ ํ๋ฒํธ๋ฅผ ๋ชจ๋ ์
๋ ฅ๋ฐ์ ๋ฐฐ์ด์ ์ ์ฅํ ๋ค, ๊ธธ์ด ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ
for (int i=0; i<n; i++) numbers[i] = br.readLine();
Arrays.sort(numbers, (s1, s2) -> s1.length()-s2.length());
// ๋ชจ๋ ์ ํ๋ฒํธ์ ๋ํด ํธ๋ผ์ด์ ์ ์ฅํ๋ฉฐ ์ด์ ์ ์ ์ฅํ ์ ํ๋ฒํธ ๋จ์์ ์ผ์นํ๋ ์ ๋์ฌ๊ฐ ์๋์ง ํ์ธ
boolean consistent = false;
for (int i=0; i<n; i++) {
if (insert(numbers[i].toCharArray())) consistent = true;
}
// ์ถ๋ ฅ
if (consistent) System.out.println("NO");
else System.out.println("YES");
}
}
}
๐ก
- ํธ๋ผ์ด ๋ฒ์จ ๊น๋จน๋ค๋โฆ