[Hackerrank] Hash Tables: Ice Cream Parlor

https://www.hackerrank.com/challenges/ctci-ice-cream-parlor/problem

Hash Tables: Ice Cream Parlor | HackerRank

풀이

• input : 가지고 있는 money, 아이스크림 가격 정보에 대한 list

• 두 개의 아이스크림 가격의 합이 가지고 있는 money와 일치할 때 아이스크림의 index를 오름차순으로 출력

• 아이스크림 가격 리스트를 한 번 순회하면서 파이썬의 dictionary를 사용해 , key는 i번째 아이스크림의 가격, value는 index i를 저장.

• j번째 아이스크림의 가격 정보가 입력되었을 때 (money - j번째 아이스크림의 가격)이 dictionary key로 존재할 경우, dictionary[(money - j번째 아이스크림의 가격)] + 1, j+1을 출력하고 종료.

• dictionary에는 j번째 index보다 더 앞서 나온 아이스크림 가격과 index가 저장되어있으므로, dictionary에서 찾은 index, 현재 index 순으로 출력하면 오름차순이 됨.

• 파이썬의 dictionary에서 key를 찾는 알고리즘은 시간복잡도 O(1)이기 때문에 총 계산 O(N)으로 구현할 수 있음.

  def whatFlavors(cost, money):
      cost_dict = {}
      for idx, c in enumerate(cost):
          if money-c in cost_dict:
              print(f"{cost_dict[money-c] + 1} {idx+1}")
          else:
              cost_dict[c] = idx