[BOJ] 26069 - 붙임성 좋은 총총이 (Java)

알고리즘

• 자료 구조
• 해시를 사용한 집합과 맵
• 트리를 사용한 집합과 맵

1. 문제

• 무지개 댄스를 추고 있는 사람들의 수를 구하는 문제
  

2. Idea

• HashSet hs = 총총이를 포함한 무지개 댄스를 추고 있는 사람들의 이름들의 집합
• hs에는 총총이가 포함되어 있는 상태로 초기값 설정
• 각 입력의 두 사람 중 누구든 hs에 포함되어 있는 사람들인가?를 판단하면서 진행
• 처음에는 입력 라인마다 총총이가 나올때까지 기다렸다가, 이후 라인부터 count를 증가시키면서 하려고 했다. 하지만 이 방법은 중복 인원이 입력되는 경우까지 고려할 수 없어서 Set을 사용해야만 했다.

3. 풀이

3.1. 변수 선언 및 초기화

• int N: 입력 Line 수
• HashSet hs: 총총이를 포함한 무지개 댄스를 추고 있는 사람들의 이름들의 집합
  • Set이므로 중복 요소는 없다.
• 총총이는 무지개 댄스를 추고 있는 상황에서 시작하므로 hs에 총총이를 추가한 상태로 시작한다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
HashSet<String> hs=new HashSet<>();
hs.add("ChongChong");

3.2. 입력값 확인 및 처리

• 각 입력줄의 두 사람을 me/met으로 구분
• 둘 중 하나라도 hs에 존재 -> 상대방은 무지개댄스를 추게 되므로 hs에 추가
• 앞에서 언급했듯이 hs는 중복을 허용하지 않기 때문에 둘 중 누구를 hs에 추가할 지 처리하는 과정이 필요하지 않다.

for(int i=0; i<N; i++){
	StringTokenizer st=new StringTokenizer(br.readLine());
	String me=st.nextToken();
	String met=st.nextToken();
	if(hs.contains(me)||hs.contains(met)){hs.add(met); hs.add(me);}
}

3.3. 결과 출력

• 총총이를 포함한 무지개 댄스를 추고 있는 사람의 수 = hs의 크기

System.out.println(hs.size());

4. 전체코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        HashSet<String> hs=new HashSet<>();
        hs.add("ChongChong");
        for(int i=0; i<N; i++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            String me=st.nextToken();
            String met=st.nextToken();
            if(hs.contains(me)||hs.contains(met)){hs.add(met); hs.add(me);}
        }
        System.out.println(hs.size());
    }
}