6일차 - 할리갈리 ( 백준 27160번 )

27160번 : 할리갈리

---

https://www.acmicpc.net/problem/27160

---

풀이 

이 문제는 해시테이블을 사용하여 풀 수 있다. (파이썬에서는 딕셔너리)

( 해시테이블은 키-값 으로 데이터를 저장하는 자료구조이다.)

 

1. 우선 카드의 갯수를 N으로 받는다.

N = int(input())

 

2. 카드정보를 담을 딕셔너리를 만들어 준다. 해당 문제에서 S는 카드에 보여지는 과일의 종류로  STRAWBERRY, BANANA, LIME, PLUM 중 하나라고 했기 때문에 key를 과일 이름으로 받고 과 value(과일 갯수) 값을 0으로 만들어준다.

cards = {"STRAWBERRY": 0, "BANANA": 0, "LIME": 0, "PLUM": 0}

 

3. 카드 갯수만큼 반복하여 카드종류(s)와 수량(x)을 받아온다. 입력받은 카드종류에 대한 수량을 업데이트 해준다.

for i in range(N):

s, x = input().split()

card[i] += int(x)

 

4. 조건문을 통해 cards안의 value 값이 5이면 YES , 아니면 NO를 출력해준다.

if 5 in cards.values():

print("YES")

else:

print("NO")

 

제출 코드 

N = int(input())
cards = {"STRAWBERRY": 0, "BANANA": 0, "LIME": 0, "PLUM": 0}
for i in range(N):
    s, x = input().split()
    cards[s] += int(x)
if 5 in cards.values():
    print("YES")
else:
    print("NO")

 

 

 

배열에 익숙한 나에게 해시테이블은 생소했지만 배열을 사용하면 원하는 값을 찾기위해서 배열 내에서 하나하나 돌아가면서 원하는 값에 대한 정보를 찾아야한다면 해시테이블을 이용하면 테이블의 key를 해시함수를 통해 배열의 인덱스로 변환하여 원하는 정보를 빠르게 검색할 수 있다는 걸 배우게 되었다.

배열 시간 복잡도: O(n) - n은 배열의 길이

해시테이블 시간 복잡도: O(1) - 해시 함수 계산과 배열 인덱스 접근