https://www.acmicpc.net/problem/16165
16165번: 걸그룹 마스터 준석이
정우는 소문난 걸그룹 덕후이다. 정우의 친구 준석이도 걸그룹을 좋아하지만 이름을 잘 외우지 못한다는 문제가 있었다. 정우는 친구를 위해 걸그룹 개인과 팀의 이름을 검색하여 외우게 하는
www.acmicpc.net
코드설명
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)); } } } }
'알고리즘 > 해시를 사용한 집합과 맵' 카테고리의 다른 글
[백준] 3273 두 수의 합 - HashSet(해시셋) + 정렬(Sort) + 투포인터(Two Pointer) JAVA (0) | 2024.07.23 |
---|---|
[백준] 2002 추월 - HashMap(해시맵) + 구현(Implementation) JAVA (0) | 2024.04.03 |
[백준] 4358 생태학 - HashMap(해시맵) + TreeMap(트리맵) + 소수점(printf, .4f, format) JAVA (0) | 2024.04.01 |
[백준] 13414 수강신청 - LinkedHashSet(해시셋) JAVA (0) | 2024.04.01 |
[백준] 9375 패션왕 신해빈 - HashMap(해시맵) + 시간초과(경우의 수에 대한 이해) JAVA (0) | 2024.03.28 |