[백준 | Java] 32978번 아 맞다 마늘

32978번 / 아 맞다 마늘

❓ 아 맞다 마늘

🏷️ 관련 주제 : 브루트포스 알고리즘 Map

💦 나의 시도

Try01. HashMap으로 생성한 Map을 사용한 방법

N가지 요리 재료를 입력 받고 실제로 사용한 재료와 비교하여 체크하려면 입력받은 요리 재료를 저장한 자료구조를 탐색해야 하는데 이 때, 시간복잡도가 O(1)인 Map이 가장 빠를 것 같아서 Map을 사용한 풀이 시도

1. BufferedReader를 이용하여 총 재료 개수 N을 입력 받고 int형으로 변환 후, 초기화
2. 재료를 담을 Map<String, Integer> ingredients를 초기화
3. StringTokenizer로 모든 재료를 입력 받음
4. 0 ~ (N - 1) 범위를 반복문을 돌면서 StringTokenizer의 nextToken()메서드로 재료를 하나씩 꺼내 ingredients에 재료명을 키로 값을 1로 추가
   재료를 Key로 했는데 Value는 특별히 필요하지 않은데 어떤 값을 넣을 지 몰라 그냥 값을 모두 1로 저장
5. 사용한 재료를 입력 받고 0 ~ (N - 2) 범위를 반복문을 돌면서 StringTokenizer의 nextToken()메서드로 사용한 재료를 하나씩 꺼내 ingredients에서 삭제
6. forEach문으로 ingredients의 keySet()에서 재료를 꺼내 출력
   • 이렇게 남은 재료를 출력했었는데
     for (String notUsed : ingredients.keySet()) { System.out.println(notUsed); }
   • 아래 방법이 더 빠른 것 같다.
     ingredients.keySet().forEach(ingredient -> System.out.println(ingredient));

맞았습니다!!

6-1번 코드

• 메모리 : 14868 KB
• 시간 : 120 ms
• 코드 길이 : 876 B

6-2번 코드

• 메모리 : 14712 KB
• 시간 : 116 ms
• 코드 길이 : 855 B

Try02. ArrayList를 사용한 방법

Map을 사용한 방법이 Key를 빨리 조회하는 것은 좋은데 불필요한 Value 값을 넣어야하는 것이 마음에 걸려서 ArrayList를 사용한 방법도 시도해 보았습니다.

Map에 값을 추가 및 삭제, 남은 재료 출력하는 부분 코드 수정

for (int i = 0; i < N; i++) {
    ingredients.add(st.nextToken());
}

st = new StringTokenizer(br.readLine());
for (int i = 0; i < N - 1; i++) {
    ingredients.remove(st.nextToken());
}

System.out.println(ingredients.get(0));

 

맞았습니다!!

• 메모리 : 14968 KB
• 시간 : 132 ms
• 코드 길이 : 795 B

문제와 관련된 알고리즘을 보니 브루트포스 알고리즘이 있어서
완전 탐색을 해도 풀 수 있는 문제였다는 것을 알았습니다.
그런데 정확히 어느 범위까지 완전탐색을 사용해도 되는지 전에 배웠던 것이 기억이 안나서 검색을 해 보았습니다.

 

코딩테스트 문제에서 보통 1초에 약 100,000,000번의 연산 가능

• 완전 탐색의 시간 복잡도 ($n$ : 문제의 크기)
  • 순열 문제 : O($n!$)
  • 조합 문제 : O($n^k$)
  • 부분 집합 문제 : O($2^n$)
• 완전 탐색을 사용할 수 있는 값의 범위
  • 순열, 조합 문제
    • $n \leq 100,000$
    • $n!$이나 $2^n$처럼 급격히 증가하는 경우를 피할 수 있음
  • 단순 반복문
    • $n \leq 1,000$
    • 최대 1,000,000번의 연산이므로 충분히 시간이 허용됨.
  • 조합, 부분 집합 문제
    • $n \leq 20$
    • 약 1,000,000번까지 계산 가능하므로 적합

📑제출 기록 및 오답 원인

💯 해결 방법

1. Map을 이용한 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

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());
        Map<String, Integer> ingredients = new HashMap<>();
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            ingredients.put(st.nextToken(), 0);
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N - 1; i++) {
            ingredients.remove(st.nextToken());
        }

        for (String notUsed : ingredients.keySet()) {
            System.out.println(notUsed);
        }
    }
}

 

2. ArrayList를 이용한 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

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());
        ArrayList<String> ingredients = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            ingredients.add(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N - 1; i++) {
            ingredients.remove(st.nextToken());
        }

        System.out.println(ingredients.get(0));
    }
}

🏷️ 문제 풀면서 참고한 블로그

• [08강] 브루트 포스 알고리즘