[백준] 32978 - 아 맞다 마늘

 

문제 출처 : https://www.acmicpc.net/problem/32978

 

문제
요리하는 과정에서 빼먹은 요리 재료를 떠올리자.

 

입력

• 첫 번째 줄에 파스타를 만들기 위한 요리 재료의 개수 N이 주어짐 (2<=N<=1000)
• 두 번째 줄에 파스타에 들어가는 재료 N가지가 공백으로 구분되어 주어짐(중복 없음)
• 세 번째 줄에 N재료 중 사용한 N-1개의 재료가 공백으로 구분되어 주어짐
• 각 재료는 알파벳 대소문자, 길이 20이하 문자열

 

출력

•  잊어버린 요리 재료

 

풀이 방법

1. 모든 재료와 사용한 재료를 각각 리스트 ingredients와 used에 넣음.
2. 리스트를 정렬함.
3. 같은 순번에 같은 재료가 있는지 비교.
4. 같지 않으면 해당 순번의 ingredients의 요소가 빠진 재료이므로 출력

 

작성한 코드

import sys
N = int(sys.stdin.readline().strip())
ingredients = sys.stdin.readline().strip().split() #1
used = sys.stdin.readline().strip().split()

ingredients.sort() #2
used.sort()
used.append("nothing") #ingredients와 length를 맞춰주기 위해 추가

for i in range(N):
    if (ingredients[i]!=used[i]): #3
        print(ingredients[i]) #4
        break

 

 

접두어 관련 다른 문제를 풀 때 sort()를 사용해서 푼 풀이를 봤었는데,

이번 문제에 적용하면 좋은 것 같아서 그렇게 풀어보았다.

 

다른 풀이를 보니 모든 재료에서 사용한 재료를 하나씩 지워서 남은 재료를 출력한 방법도 있었고,

in 연산으로 사용한 재료 리스트에 있는지 하나씩 확인하는 방법도 있었다. 

또 해시 기반 탐색을 사용한 방법도 있었는데 사용한 재료를 set에 저장해서 not in 연산으로 사용하지 않은 재료를 찾는 방식이었다.

set은 해시테이블로 구현되어 있어 데이터 탐색과 삽입에 평균적으로 O(1)이 소요된다고 한다.

 

4명의 풀이 방법이 다 다른게 재미있었다.