intro : Set은 참 훌륭한 자료구조이다. (빠르고 중복제거도 해줌)

문제

총총이는 친구 곰곰이의 소개로 제2회 곰곰컵에 출연할 기회를 얻었다! 총총이는 자신의 묘기인 무지개 댄스를 선보여, 여러분의 환심을 사려 한다. 이 댄스는 중독성이 강하기 때문에, 한번 보게 된 사람은 모두 따라 하게 돼버린다. 무지개 댄스를 추는 총총 2마리 사람들이 만난 기록이 시간 순서대로 N개 주어진다. (총총이는 토끼이지만 이 문제에서는 편의상 사람이라고 가정한다.) 무지개 댄스를 추지 않고 있던 사람이 무지개 댄스를 추고 있던 사람을 만나게 된다면, 만난 시점 이후로 무지개 댄스를 추게 된다. 기록이 시작되기 이전 무지개 댄스를 추고 있는 사람은 총총이 뿐이라고 할 때, 마지막 기록 이후 무지개 댄스를 추는 사람이 몇 명인지 구해보자!

입력

첫번째 줄에는 사람들이 만난 기록의 수 N (1 <= N <= 1000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 사람들이 만난 기록이 주어진다. i + 1번째 줄에는 i번째로 만난 사람들의 이름 A와 B가 공백을 사이에 두고 주어진다. A와 B는 숫자와 영문 대소문자로 이루어진 최대 길이 20의 문자열이며, 서로 같지 않다. 총총이의 이름은 ChongChong으로 주어지며, 기록에서 1회 이상 주어진다. 동명이인은 없으며, 사람의 이름은 대소문자를 구분한다.(ChongChong과 chongchong은 다른 이름이다.)

출력

마지막 기록 이후 무지개 댄스를 추는 사람의 수를 출력하라.

문제 풀이 (124ms)

import java.io.*;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입출력을 위한 BufferedReader, BufferedWriter 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String stand = "ChongChong";

        // 중복제거를 위한 set 변수 선언 
        // 무지개 댄스를 춘 사람들 및 전염시킬 수 있는 사람들의 모임
        Set<String> set = new HashSet<>();
        // ChongChong 미리 add 
        set.add(stand);
        // 입력받을 값 개수 
        int count = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for (int i = 0; i < count; i++) {
            st = new StringTokenizer(br.readLine());
            String first = st.nextToken();
            String second = st.nextToken();
            // 만약 무지개 댄스를 추고 있는사람들 이거나 전염된 사람들이라면
            if (set.contains(first) || set.contains(second)) {
                // 만남 사람들 또한 전염
                set.add(first);
                set.add(second);
            }
        }
        // bw로 출력하기 위해 문자열로 변환 후 write
        bw.write(String.valueOf(set.size()));
        bw.flush();

        // 자원 반납
        bw.close();
        br.close();
    }
}

문제 해석

처음에 문제를 너무 쉽게 생각해서 빠르게 코드 제출하고 틀렸었는데 입력예제 1번에 속았던거 같다. 총총이가 나온다음 부터 모든 사람들은 전염되어 그냥 카운팅만 했었는데, 생각해보니까 총총이와 만난 사람들이 다음번에도 연속적으로 다른사람들과 만난다는 전제는 없으니, 전염된 사람들을 정확히 체크해서 전염된 사람들이 입력값으로 들어오는지 확인하여 카운팅을 해야한다.

위 말이 조금 이해가 안갈수도 있으니 좀더 명확하게 설명하자면, 총총이가 만난사람이 A라고 한다면 현재 무지개 댄스를 추는 사람은 총총이와 A다. 다음 입력값으로 B와 C가 들어온다면 이사람들은 총총이와 A를 만난게 아니니 무지개 댄스를 추지 않는다 하지만 다음 입력값으로 A와 D가 들어온다면 A는 총총이에게 전염당해 무지개댄스를 추구있는사람이니 D또한 무지개 댄스를 추게된다. (이후 같은 과정이 반복됨)

위 내용을 코드로 구현하게되면, 초기에 총총이를 set변수 (전염된 사람들의 모임)에 넣어두고 만나는 사람들이 set에 있는 사람들인지 확인하며 만약 set변수에 있는사람을 만났다는건 무지개 댄스를 추고 있는 사람이라는 것이니 만난 사람들 전부 set변수에 넣는다. 여기서 중복을 걱정할 수도 있지만. set은 중복을 제거하고 데이터를 관리하는 자료구조이기에 마음편히 set에 다 넣어서 관리해도 중복을 제거한 값들만 가지고 있게되어 결과적으로 size() 메서드를 통해 무지개 댄스를 추고 있는 사람들의 개수를 구할 수 있다.

I am visible

contact

문제

입력

출력

문제 풀이 (124ms)

문제 해석