99클럽 코테 스터디 8일차 TIL + 브루트포스 알고리즘, 집합, set()

1. 문제 설명

[문제 내용]

APC-Extra배 흑백 요리사에 참가한 현빈이는 라운드마다 자신만의 창의적인 요리를 선보여 활약하고 있다. 결승전에 진출한 현빈, 그는 여기에서 자신의 인생 요리이자 시그니처 요리인 봉골레 파스타를 선보였다.

그러나 현빈이는 1위와 1점 차이로 아쉽게 지고 말았는데, 곰곰이 요리 과정을 복기하던 현빈이는 요리하는 과정에서 정확히 하나의 요리 재료를 빼먹었다는 것을 떠올렸다.

현빈이가 요리하는 과정에서 무슨 재료를 빼먹었는지 맞혀보자.

[입력]

첫 번째 줄에 봉골레 파스타를 만들기 위한 요리 재료 종류의 개수 $N$이 주어진다. $(2\le N\le 1 000)$ 

두 번째 줄에 봉골레 파스타에 들어가는 $N$가지의 요리 재료가 공백으로 구분되어 주어진다. 모든 요리 재료는 한 번씩만 주어진다.

세 번째 줄에 봉골레 파스타에 들어가는 $N$가지의 재료 중 현빈이가 사용한 $N-1$가지의 요리 재료가 공백으로 구분되어 주어진다. 같은 요리 재료가 $2$번 이상 주어지는 경우는 없다.

각 재료는 알파벳 대/소문자로 이루어져 있고 길이 $20$ 이하의 문자열이다. 같은 철자를 가진 요리 재료이더라도, 대소문자의 여부가 다르다면 두 요리 재료는 다른 요리 재료이다.

[출력]

현빈이가 빼먹은 재료를 출력한다.

[입출력 예]

2. 풀이

N = int(input())

ingredients = set(input().split())

used_ingredients = set(input().split())

missing_ingredient = ingredients - used_ingredients

print(*missing_ingredient)

3. 회고

3-1. 문제 해결 과정

처음에 작성한 코드가 출력 초과로 나와서 뭐지? 했는데, 아마도 인덱스를 사용해서 접근하다 보니 비효율적이기도 하고 중복해서 잘못된 값이 출력될 가능성이 높았다.

list가 아니면 어떻게 저장을 해야하나 고민하던 찰나에 set()을 발견하게 되었다. set()을 통해 고유한 값들만 저장하게 되면서, 집합의 원리를 이용하여 필수 재료와 사용된 재료를 빼면 차집합이 된다.

매번 리스트 형태로 코드를 작성하려고 했었는데 집합을 사용하면 조금 더 빠르게 접근할 수 있겠다는 생각이 들었다. 기존에 시도한 방식은 브루트포스 알고리즘 형태로, 무작위로 비교하는 거였는데 집합을 사용하면 차집합을 이용하면 되니 더 깔끔하다!

3-2. 새롭게 배운 내용

• set() : Python의 내장 자료형으로, 중복을 허용하지 않고 순서가 없는 고유한 값들의 모음을 나타낼 수 있다. 동일한 값이 여러 번 추가되더라도 하나의 값만 갖게 된다.

numbers { 1, 2, 3, 4, 5}
print(numbers) # 출력 : {1, 2, 3, 4}

또한 순서가 없기 때문에 인덱스가 없으며, 출력 순서는 랜덤이다.

numbers = set([1, 2, 3, 4, 4])
print(numbers)  # 출력: {1, 2, 3, 4}

추가적으로 add(), remove(), disard(), clear()를 통해서 요소를 넣거나 삭제할 수 있다. discard()는 없는 요소를 제거하려고 해도 에러가 발생하지 않으며, clear()는 모든 요소를 제거한다.

• 합집합 연산 : | 또는 union()을 이용하면 두 집합의 모든 요소를 포함할 수 있다.

A = {1, 2, 3}
B = {3, 4, 5}
print(A | B)  # 출력: {1, 2, 3, 4, 5}
print(A.union(B))  # 출력: {1, 2, 3, 4, 5}

• 교집합 연산 : & 또는 intersection()을 이용하면 두 집합에 공통적으로 포함된 요소를 출력할 수 있다.

print(A & B)  # 출력: {3}
print(A.intersection(B))  # 출력: {3}

• 차집합 연산 : - 또는 difference()를 이용하면 첫 번째 집합에는 포함되고 두 번째 집합에는 포함되지 않는 요소를 출력한다.

print(A - B)  # 출력: {1, 2}
print(A.difference(B))  # 출력: {1, 2}

• 대칭 차집합 연산 : ^ 또는 symmetric_difference()를 이용하면 두 집합 중 어느 한 쪽에만 포함된 요소를 반환한다.

print(A ^ B)  # 출력: {1, 2, 4, 5}
print(A.symmetric_difference(B))  # 출력: {1, 2, 4, 5}

• 언패킹 연산자 * : 리스트나 튜플 등과 같은 iterable 객체의 요소를 하나씩 풀어서 함수나 연산에 전달할 수 있다. 즉, 객체의 각 요소를 개별적인 인수로 분리하여 처리하게 된다.

numbers = [1, 2, 3, 4]
print(*numbers)  # 출력: 1 2 3 4

• 브루트포스 알고리즘 : 무차별 대입 알고리즘 또는 완전 탐색 알고리즘으로 불리며, 가능한 모든 경우의 수를 하나씩 대입하여 정답을 찾는 알고리즘이다. 가장 단순하고 직관적이지만 비효율적이다.