[자바] 백준 16165 - 걸그룹 마스터 준석이 (java)

 문제 : boj16165

---

 

필요 알고리즘 개념

• 해시를 사용한 집합과 맵
  
  • 해시맵에 대해 제대로 이해하고 있어야 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  이 문제의 두 쿼리를 나눠서 생각해보자.

우선 '1' 쿼리의 경우 멤버의 이름이 주어지면 팀명을 출력해야 한다. 이 부분은 입력을 받으면서 멤버의 이름을 key, 팀명을 value로 하는 해시맵을 구성해두면 각 쿼리마다 O(1)로 출력해줄 수 있다.

while (N-->0) {
    String tName = br.readLine();	// 팀명
    int K = Integer.parseInt(br.readLine());
    String[] arr = new String[K];
    while (K-->0) {
        String gName = br.readLine();	// 멤버명
        girl.put(gName, tName);	// 멤버명을 key, 팀명을 value로 하는 해시맵
        arr[K] = gName;
    }
    Arrays.sort(arr);
    team.put(tName, arr);
}

 

  '0' 쿼리가 문제인데 우선 팀명이 주어졌을 때 빠르게 멤버 리스트를 얻을 수 있어야 하고, 또 정렬을 해서 출력해줘야 한다. 이건 해시맵에 팀명을 key, 팀원 리스트를 value로 하는 해시맵을 구성해두면 된다. 이 때 팀원 리스트는 입력받으면서 미리 정렬해두면 정렬부분은 생각하지 않아도 되며, 팀명이 주어졌을 때 팀원 리스트도 빠르게 획득할 수 있다.

while (N-->0) {
    String tName = br.readLine();	// 팀명
    int K = Integer.parseInt(br.readLine());
    String[] arr = new String[K];	// 팀원 리스트
    while (K-->0) {
        String gName = br.readLine();	// 멤버명
        girl.put(gName, tName);	// 멤버명을 key, 팀명을 value로 하는 해시맵
        arr[K] = gName;	// 멤버명을 팀원 리스트에 넣어둔다.
    }
    Arrays.sort(arr);	// 미리 팀원 리스트를 정렬한 후
    team.put(tName, arr);	// 팀명을 key, 팀원 리스트를 value로 하는 해시맵에 넣는다.
}

  

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		HashMap<String, String[]> team = new HashMap<String, String[]>();
		HashMap<String, String> girl = new HashMap<String, String>();
		while (N-->0) {
			String tName = br.readLine();
			int K = Integer.parseInt(br.readLine());
			String[] arr = new String[K];
			while (K-->0) {
				String gName = br.readLine();
				girl.put(gName, tName);
				arr[K] = gName;
			}
			Arrays.sort(arr);
			team.put(tName, arr);
		}
		while (M-->0) {
			String tmp = br.readLine();
			int pr = Integer.parseInt(br.readLine());
			switch (pr) {
			case 0 :
				for (String s : team.get(tmp))
					bw.write(s + "\n");
				break;
			case 1 :
				bw.write(girl.get(tmp) + "\n");
			}
		}
		bw.flush();		
		bw.close();
		br.close();
	}
}