99클럽 코테 스터디 8일차 TIL - Java 백준 32978 아맞다마늘

🌟 [백준 32978] 아 맞다 마늘 해결하기

📝 Today I Learned

오늘은 깜빡하고 뺀 재료를 찾는 문제를 풀어보았다. 처음엔 간단해 보였지만, 생각보다 많은 시행착오를 겪었다.

1. 문제 분석 (재정의)

• N개의 전체 재료 중에서 N-1개만 사용했을 때, 빠진 1개 재료를 찾는 문제다.
• 재료는 대소문자를 구분하며, 중복된 재료는 입력되지 않는다.
• 결국 "차집합"을 구하는 문제라고 볼 수 있다.

2. 문제 접근 방식

처음에는 배열로 하나씩 순차 비교하려고 했다. 그런데 문득 이런 생각이 들었다.
지금은 몇 개 없다고 하지만, N-1개를 일일이 비교하면... 시간이 너무 오래 걸리지 않을까?

그래서 해시 자료구조를 떠올렸다. 처음엔 HashMap을 쓸까 고민했는데, 키-값 쌍까지는 필요 없었다.
그냥 재료의 존재 여부만 빠르게 확인하면 되니까 HashSet이면 충분했다.

 

HashSet이란?

HashSet은 마치 주머니와 같다. 이 주머니는 특별해서:

1. 같은 물건은 두 번 넣을 수 없다 (중복 불가)
2. 물건을 엄청 빨리 찾을 수 있다 (해시 기반 검색)
3. 물건의 순서는 중요하지 않다 (순서 보장 X)

이 문제에서는 재료들이 중복되지 않고, 빠르게 찾아야 하기 때문에 HashSet이 딱이었다.

3. 문제 풀이 과정

먼저 시도한 코드는 이랬다. 

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

// 백준 32978번 아 맞다 마늘
public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 요리재료 종류개수 : N
        int N = Integer.parseInt(br.readLine()); 

        // 배열 순차비교보다는, 전체 요리 재료 HashSet에 저장, stringtokenizer (중복없음)
        HashSet<String> ingredients = new HashSet<>(); 
        StringTokenizer st = new StringTokenizer(br.readLine()); 

        // N 중 N-1 개 재료 -> 공백 구분 (중복없음)
        st = new StringTokenizer(br.readLine()); 
        // 입력은 N-1개의 재료만 들어옴
        for (int i = 0; i < N-1; i++) { 
            ingredients.remove(st.nextToken());
        }

        // 주의: 알파벳 대/소문자 구분함. 대소문자 다르면 다른 재료임: lower,upper 필요없음
        // 안 넣은 재료 출력 : 해시셋에 남은 하나의 재료  
        System.out.println(ingredients.iterator().next());
    }
}

 

 

그런데 계속 NoSuchElementException이 발생했다. 분명히 입력은 제대로 받았는데... 왜지?
처음에는 문제 제약사항 '분명히 N-1개만 넣는다'가 제대로 작동하지 않는 줄 알고
N-1까지만 반복 && st.hasMoreTokens를 조건 안에 추가했었다.
그래도 같은 예외가 발생했다.

 

한참을 고민하다 보니 치명적인 실수를 발견했다. HashSet에 전체 재료를 담는 과정을 빼먹은 것이다.

결국 이렇게 해결했다:

HashSet<String> ingredients = new HashSet<>();
String[] ingredientArray = br.readLine().split(" ");
Collections.addAll(ingredients, ingredientArray);

4. 최종 제출 코드

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

// 백준 32978번 아 맞다 마늘
public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 요리재료 종류개수 : N
        int N = Integer.parseInt(br.readLine()); 

        // 배열 순차비교보다는, 전체 요리 재료 HashSet에 저장, stringtokenizer (중복없음)
        HashSet<String> ingredients = new HashSet<>(); 
        String[] ingredientArray = br.readLine().split(" ");
        Collections.addAll(ingredients, ingredientArray);

        // N 중 N-1 개 재료 -> 공백 구분 (중복없음)
        StringTokenizer st = new StringTokenizer(br.readLine()); 

        // 입력은 N-1개의 재료만 들어옴
        for (int i = 0; i < N-1; i++) { 
            ingredients.remove(st.nextToken());
        }

        // 주의: 알파벳 대/소문자 구분함. 대소문자 다르면 다른 재료임: lower,upper 필요없음
        // 안 넣은 재료 출력 : 해시셋에 남은 하나의 재료  
        System.out.println(ingredients.iterator().next());
    }
}

Collections.addAll()

마치 주머니에 여러 물건을 한 번에 쓱 넣는 것처럼, 

addAll은 배열의 모든 요소를 HashSet에 한 번에 추가한다. 

일일이 for문으로 add하는 것보다 훨씬 편리하다.

 

여기서 첫 번째 파라미터 ingredients는 요소들을 추가할 대상 컬렉션으로, "어디에 넣을 건지"를 지정
두 번째 파라미터 ingredientArray는 추가할 요소들이 담긴 배열로, "무엇을 넣을 건지"를 지정

// Collections.addAll은 내부적으로 이런 동작을 함
for (String ingredient : ingredientArray) {
    ingredients.add(ingredient);
}

 

iterator.next()

HashSet에 남은 마지막 하나의 재료를 꺼낼 때는 iterator.next()를 사용했다. 

이는 마치 주머니에 손을 넣어 물건을 하나 꺼내는 것과 같다. 

HashSet에 딱 하나의 재료만 남아있다는 것을 알기 때문에 이렇게 사용할 수 있었다.

 

HashSet<String> ingredients = new HashSet<>();
Collections.addAll(ingredients, "마늘", "면", "소금");

Iterator<String> iterator = ingredients.iterator();

// hasNext()는 현재 포인터 다음에 요소가 있는지 확인
// next()는 포인터를 다음으로 이동하고 해당 요소를 반환

현재상태: [마늘] → [면] → [소금]
          ↑
       포인터

1. iterator.hasNext() : true  // 포인터 다음에 "마늘"이 있음
2. iterator.next()    : "마늘" 반환
   [마늘] → [면] → [소금]
            ↑
         포인터

3. iterator.hasNext() : true  // 포인터 다음에 "면"이 있음
4. iterator.next()    : "면" 반환
   [마늘] → [면] → [소금]
                   ↑
                포인터

5. iterator.hasNext() : true  // 포인터 다음에 "소금"이 있음
6. iterator.next()    : "소금" 반환
   [마늘] → [면] → [소금] → null
                            ↑
                         포인터

7. iterator.hasNext() : false // 포인터 다음에 아무것도 없음

 

내부적으로 hasNext()는 현재 위치에서 다음 요소가 존재하는지 확인하는 불리언 값을 반환한다.

문제에서는 HashSet에 정확히 하나의 요소만 남아있다는 것을 알고 있었기 때문에, hasNext() 체크 없이 바로 next()를 호출했다. 
만약 요소가 없는 상태에서 next()를 호출하면 NoSuchElementException이 발생하니 주의해야 한다.

일반적으로는 hasNext()로 체크 후 next()를 호출하는 것이 안전하다. 

5. 다른 풀이 참고

다른 분들의 풀이를 보니 Stream API를 활용한 방법도 있었다. 하지만 이 문제에서는 단순히 배열의 요소를 HashSet에 추가하는 것이 목적이라 Collections.addAll()을 사용하는 게 더 직관적이라고 생각했다.

// 비교

// 방법 1: 바로 HashSet으로 변환
HashSet<String> ingredients = new HashSet<>();
String[] ingredientArray = br.readLine().split(" ");
Collections.addAll(ingredients, ingredientArray);

// 또는 더 간단히
// 방법 2: Stream 활용
HashSet<String> ingredients = new HashSet<>();
String[] ingredientArray = br.readLine().split(" ");
Arrays.stream(ingredientArray).forEach(ingredients::add);

💭 Reflection

오늘 문제를 통해 자료구조의 선택이 얼마나 중요한지 다시 한번 느꼈다. 처음엔 단순하게 배열로 접근했다가, HashSet을 사용하면서 코드가 훨씬 깔끔해졌다.

 

또한 NoSuchElementException을 해결하면서 입력 처리의 중요성도 배웠다.

입력은 받았는데 처리를 안 했다는 깨달음이 문제 해결의 키포인트였다.