109. 개미굴 (백준 14725) [JAVA]

109. 개미굴 (백준 14725) [JAVA]

문제

문제 링크 : https://www.acmicpc.net/problem/14725

문제

로봇 개미 개발을 완료한 윤수는 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 위 그림의 개미굴에 로봇 개미를 투입했다. (로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을 만큼 넣는다.)

다음은 로봇 개미들이 윤수에게 보내준 정보다.

KIWI BANANA

KIWI APPLE

APPLE APPLE

APPLE BANANA KIWI

(공백을 기준으로 왼쪽부터 순서대로 로봇 개미가 각 층마다 지나온 방에 있는 먹이 이름을 뜻한다.)

윤수는 로봇 개미들이 보내준 정보를 바탕으로 다음과 같이 개미굴의 구조를 손으로 그려봤다.

APPLE --APPLE --BANANA ----KIWI KIWI --APPLE --BANANA

(개미굴의 각 층은 "--" 로 구분을 하였다.

또 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.)

입력

첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000)

두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정보 개수 K가 주어진다. (1 ≤ K ≤ 15)

다음 K개의 입력은 로봇 개미가 왼쪽부터 순서대로 각 층마다 지나온 방에 있는 먹이 정보이며 먹이 이름 길이 t는 (1 ≤ t ≤ 15) 이다.

출력

개미굴의 시각화된 구조를 출력하여라.

개미굴의 각 층을 "--" 로 구분하며, 같은 층에 여러개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.

풀이

문제가 길고 복잡하지만, 해결은 간단하게 할 수 있었다.

각각의 입력에서 같은 부분끼리 묶어주면 되기 때문이다. (트리 구조 만들기)

문자열을 빠르게 처리하기 위해서 HashMap을 사용하였고, 각 문자열을 입력받을때 검사하여 만약 존재하는 노드라면 다음 노드로 이어지게 했다.

출력을 할 경우에는 HashMap의 키값을 정렬해주고 출력함으로써 문제를 해결할 수 있었다.

코드

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.util.StringTokenizer; public class Main { static int N; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); StringTokenizer st; Node root = new Node(); for(int i=0; i childs = new HashMap<>(); }

결과

반응형

from http://howtolivelikehuman.tistory.com/252 by ccl(A) rewrite - 2021-09-04 15:00:17