[백준] 16165 걸그룹 마스터 준석이 - HashMap(해시맵) + HashSet(해시셋) + TreeSet(트리셋) JAVA

https://www.acmicpc.net/problem/16165

16165번: 걸그룹 마스터 준석이

코드설명

HashMap(해시맵) + HashSet(해시셋) 를 활용합니다.

 

단순히 HashMap을 사용하여 해결할 줄 알았으나, 생각보다 구현을 해야했습니다.

제출하고난뒤 너무 복잡하게 푸는 것 같아 다른분들 코드도 함께 확인했으나 

다른분들은, HashMap<Team이름, 멤버1+" "+멤버2+" "+멤버3" "> 이런식으로 각 팀을 넣습니다.

이렇게 하면 장점은 Team이름을 검색할때 바로 찾을 수 있을 것 입니다

.

저는, HAshSet[N] 을 활용해서 각 배열과 

각 팀의 이름을 저장하는 groupName[N]을 따로 만들어서 처리했습니다.

이렇게 할경우, 활용되는 데이터들이 많아 구현시에 실수가 일어날 수 있다는 점이 단점입니다.

 

또 만약 Quiz가 0일경우 그룹포함한 멤버들을 모두 오름차순으로 출력해야하는데,

groupArr = new ArrayList[N];
for(int i=0;i<N;i++) {
    groupArr[i] = new ArrayList(hashset[i]);
    Collections.sort(groupArr[i]);
}

이와 같은 코드로, 먼저 각 그룹별로 오름차순 정보를 저장해서 Sort가 시작 부분에서만 이루어지도록 처리합니다.

 

유의해야할점은, 만약 HashSet이나 HashMap을 사용하지 않고 모든 Member들이나 Team의 정보를 직접비교를 통해 진행할경우 O(N^2)의 시간복잡도가 나올 수 있습니다.

조회시에 O(1)의 시간복잡도를 보장해주어야 속도를 증가시킬 수 있습니다.

코드

package algorhythm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	public static int N, M, T;
	public static String[] groupName;
	public static ArrayList<String>[] groupArr;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		groupName = new String[N];
		//각 그룹별.
		HashSet<String>[] hashset = new HashSet[N];
		
		for(int i=0;i<N;i++) {
			//먼저 그룹이름을 받는다.
			st = new StringTokenizer(br.readLine());
			String input = st.nextToken();
			groupName[i] = input;
			hashset[i] = new HashSet<String>();
			
			//이제 각 그룹에 속한 멤버들을 받는다.
			st = new StringTokenizer(br.readLine());
			int groupCnt = Integer.parseInt(st.nextToken());
			for(int j=0;j<groupCnt; j++) {
				st = new StringTokenizer(br.readLine());
				input = st.nextToken();
				hashset[i].add(input);
			}
		}
		
		groupArr = new ArrayList[N];
		for(int i=0;i<N;i++) {
			groupArr[i] = new ArrayList(hashset[i]);
			Collections.sort(groupArr[i]);
		}
		
		//Quiz 시작
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			String quizName = st.nextToken();
			
			st = new StringTokenizer(br.readLine());
			int quizKind = Integer.parseInt(st.nextToken());
			
			//퀴즈의 종류가 0일경우 팀에 속한 그룹포함 멤버들을 오름차순으로 출력한다.
			if(quizKind == 0) {
				for(int j=0;j<N;j++) {
					if(groupName[j].equals(quizName) == true) {
						for(String name : groupArr[j]) {
							System.out.println(name);
						}
					}
				}
			}
			
			//퀴즈의 종류가 1 일경우 팀의 이름을 출력한다.
			else if(quizKind == 1) {
				for(int j=0;j<N;j++) {
					if(hashset[j].contains(quizName) == true) {
						System.out.println(groupName[j]);
					}
				}
			}
			
		}
		
	}
}

 

HashMap과 TreeSet을 활용합니다. 가장 빠른 코드입니다.

이떄 유의할점은, TreeSet<String>은 HashMap에 들어갈때 참조형으로 들어가기에 먼저 넣어놓은뒤 나중에 입력을 받아도 참조형이기에 연동됩니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
    private static int N, K, M, L;
    private static int[] arr;
    private static long answer = 0;
    
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		Map<String, String> memberToTeam = new HashMap<>();
		Map<String, TreeSet<String>> teamToMembers = new HashMap<>();
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			String teamName = st.nextToken();
			st = new StringTokenizer(br.readLine());
			int teamSize = Integer.parseInt(st.nextToken());
			
			TreeSet<String> membersTreeSet = new TreeSet<>();
			teamToMembers.put(teamName, membersTreeSet);
			
			for(int j=0;j<teamSize; j++) {
				st = new StringTokenizer(br.readLine());
				String memberName = st.nextToken();
				membersTreeSet.add(memberName);
				memberToTeam.put(memberName, teamName);
			}
		}
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			String quiz = st.nextToken();
			st = new StringTokenizer(br.readLine());
			int quizType = Integer.parseInt(st.nextToken());
			
			if(quizType == 0) {
				TreeSet<String> tempTreeSet = teamToMembers.get(quiz);
				for(String v : tempTreeSet) {
					System.out.println(v);
				}
			} else if(quizType == 1) {
				System.out.println(memberToTeam.get(quiz));
			}
		}
    }
    
    
}