[백준] 붙임성 좋은 총총이 (BufferedReader, StringTokenizer, HashSet, 26069번, Java)

 

문제설명

입력 & 출력

나의 풀이

"무지개 댄스를 추지 않고 있던 사람이 무지개 댄스를 추고 있던 사람을 만나게 된다면, 만난 시점 이후로 무지개 댄스를 추게 된다." 

 

이번 문제는 위 설명처럼 총총이가 춤을 췄을 때 그 춤은 중독적이어서 보는 사람은 무조건 따라 치게 된다고 합니다.

 

즉 총총이를 시작으로 연결된 사람들을 모두 체크하면 되는 문제입니다.

---

잘못된 풀이

처음에는 위와 같이 코드를 작성했습니다.

 

이 문제의 핵심은 직접적인 연결뿐 아니라 간접적인 연결이 중요합니다. 즉 직간접적으로 연결된 모든 사람을 찾는 것입니다.

 

처음 풀이는 ChongChong을 만나면 flag가 true로 바뀌고 해당 사람을 체크하는 방식이었습니다. 그러나 이 코드는 직접 연결된 사람들만 체크하기 때문에 간접적으로 연결된 사람은 놓칠 수 있습니다.

 

이해하기 쉽게 그림으로 표현하자면 위와 같습니다. ChongChong이가 춤을 추면 다음 사람 A는 춤을 추게 되고 A를 만난 B도... C.. D 전부 춤을 추게 됩니다.

---

 

 

 

저의 풀이는 위와 같습니다.

 

대소문자를 구분해야 하며, 중복이 없어야 하기 때문에 HashSet을 사용하기에 적합합니다. 

 

먼저 빠른 입력과 출력을 위해 BufferedReader클래스와 , BufferedWriter클래스를 사용하여 입력과 출력을 합니다.

 

또한 각 A사람과 B사람을 구분해야 하기 때문에 StringTokenizer를 사용하여 공백을 기준으로 구분해 줍니다.

 

HashSet을 선언하고 해당 set에 먼저 "ChongChong"을 넣어줍니다.

 

그리고 직간접적인 연결을 찾기 위하여contains() 메서드를 사용하여 A사람과 B사람이 set에 존재하는지 확인합니다.

 

존재한다면 직간접적으로 연결된 사람이기 때문에 set에 추가를 해줍니다.

---

6
ChongChong Hani
Mina Hani
ChongChong Jisu
Nayeon Sana
Jisoo Rosé
Rosé Lisa

예를 들어 위와 같은 입력이 된다면

 

 

• 첫 번째 상호작용: "ChongChong Hani"
  • A = ChongChong, B = Hani
  • set에 "ChongChong"이 포함되어 있으므로, "ChongChong"과 "Hani"를 set에 추가합니다.
  • set에는 이제 ["ChongChong", "Hani"]가 있습니다.
• 두 번째 상호작용: "Mina Hani"
  • A = Mina, B = Hani
  • set에 "Hani"가 포함되어 있으므로, "Mina"와 "Hani"를 set에 추가합니다.
  • set에는 이제 ["ChongChong", "Hani", "Mina"]가 있습니다.
• 세 번째 상호작용: "ChongChong Jisu"
  • A = ChongChong, B = Jisu
  • set에 "ChongChong"이 포함되어 있으므로, "ChongChong"과 "Jisu"를 set에 추가합니다.
  • set에는 이제 ["ChongChong", "Hani", "Mina", "Jisu"]가 있습니다.
• 네 번째 상호작용: "Nayeon Sana"
  • A = Nayeon, B = Sana
  • Nayeon과 Sana 모두 set에 포함되어 있지 않으므로, set은 변경되지 않습니다.
  • set에는 여전히 ["ChongChong", "Hani", "Mina", "Jisu"]가 있습니다.
• 다섯 번째 상호작용: "Jisoo Rosé"
  • A = Jisoo, B = Rosé
  • Jisoo와 Rosé 모두 set에 포함되어 있지 않으므로, set은 변경되지 않습니다.
  • set에는 여전히 ["ChongChong", "Hani", "Mina", "Jisu"]가 있습니다.
• 여섯 번째 상호작용: "Rosé Lisa"
  • A = Rosé, B = Lisa
  • Rosé 와 Lisa 모두 set에 포함되어 있지 않으므로, set은 변경되지 않습니다.
  • set에는 여전히 ["ChongChong", "Hani", "Mina", "Jisu"]가 있습니다.

 

 

참고❗️

[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기