9536번: 여우는 어떻게 울지?

문제

녹음된 소리에서 다른 모든 동물들의 울음소리를 제외하고 여우의 울음소리만 알아내는 프로그램을 작성하는 문제입니다. 녹음된 소리는 여러 단어로 이루어져 있으며, 각 동물의 울음소리는 "<동물> goes <소리>" 형태로 주어집니다. 질문인 "what does the fox say?"가 주어지면 입력을 종료하고, 녹음된 소리 중 다른 동물의 울음소리를 모두 뺀 나머지를 출력해야 합니다.

• 입력: 첫째 줄에 테스트 케이스의 개수 T가 주어집니다. 각 테스트 케이스의 첫째 줄에는 녹음된 소리가 주어지며, 이후로 다른 동물의 울음소리가 주어집니다. 마지막 줄에는 "what does the fox say?"가 주어집니다.
• 출력: 각 테스트 케이스마다 여우의 울음소리를 공백으로 구분하여 출력합니다.

링크: https://www.acmicpc.net/problem/9536

풀이: HashSet을 활용한 문자열 파싱 및 필터링

녹음된 전체 소리를 배열로 분리한 뒤, 알려진 다른 동물들의 울음소리를 HashSet에 모아두고 이를 기준으로 필터링하는 효율적인 접근 방식입니다.

• 문자열 파싱 (String Parsing): 첫 줄에 주어지는 녹음된 소리를 split(" ")을 사용하여 공백 기준으로 분리하고 sBits 배열에 저장합니다.
• 해시 집합(HashSet) 활용: 다른 동물들의 울음소리를 저장하기 위해 탐색 속도가 O(1)로 매우 빠른 HashSet을 사용합니다.
• 종료 조건 및 데이터 수집: 무한 루프(while(true)) 안에서 입력을 계속 받으며 split(" ")으로 단어를 분리합니다.
  • 만약 분리된 배열의 마지막 단어(tmp[tmp.length - 1])가 "say?"라면, 이는 종료 문장인 "what does the fox say?"를 의미하므로 루프를 탈출합니다.
  • 그렇지 않다면 일반적인 울음소리 정보("animal goes sound")이므로, 마지막 단어인 sound 부분을 Set에 추가합니다.
• 여우 소리 필터링: 미리 분리해둔 sBits 배열을 순회합니다. Set.contains(s)를 통해 현재 소리가 다른 동물의 소리인지 확인하고, 포함되어 있지 않다면(!set.contains(s)) 이는 여우의 소리이므로 BufferedWriter를 이용해 출력합니다.

코드

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));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int t = Integer.parseInt(br.readLine());

       while (t-- > 0) {
          // 1. 녹음된 전체 소리 파싱
          String[] sBits = br.readLine().split(" ");
          Set<String> set = new HashSet<>();
          
          // 2. 다른 동물의 울음소리 수집 및 종료 조건 확인
          while (true) {
             String[] tmp = br.readLine().split(" ");
             // "what does the fox say?"의 마지막 단어로 종료 판별
             if (tmp[tmp.length - 1].equals("say?")) {
                break;
             }

             // "animal goes sound" 형태에서 마지막 단어인 sound를 저장
             set.add(tmp[tmp.length - 1]);
          }

          // 3. 수집된 소리를 제외한 여우 소리만 필터링하여 출력
          for (String s : sBits) {
             if (!set.contains(s)) {
                bw.write(s + " ");
             }
          }
          bw.write("\n");
       }

       bw.flush();
    }
}

알고리즘 분류

자료 구조 (Data Structures), 문자열 (String), 해시를 사용한 집합과 맵 (Hash Set/Map), 파싱 (Parsing)