[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

์ฝ”๋“œ

Java
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");
		}
	}

}

๐Ÿ’ก

  • ํŠธ๋ผ์ด ๋ฒŒ์จ ๊นŒ๋จน๋‹ค๋‹ˆโ€ฆ