[hackerrank] Ice Cream Parlor python

 

처음에 그냥 딱히 생각이 안나서 O(N^2)풀이로 풀었는데 100% 정답이 뜨긴 했지만, 실제 코딩테스트에서는 O(N)시간 복잡도를 요구하는 것 같은 문제라 시간을 줄여 보았다.

 

dictionary를 이용해서 문제를 풀어보았다 (키포인트)

 

1. 가격을 key값으로, 문제의 indices를 value로 dictionary를 생성하고, for문을 돌려보자.

 

2. arr의 0번째 인덱스부터 시작해서 for문이 돌면서 dictionary에 m-arr[i] 즉, cost = [1, 4, 5, 3, 2]이 있을때 1 4 5 를 거치면서 3을 만났을때 생성된 1의 key값을 가진 값이 dictionary에 있기때문에 return [priceDic[m-arr[i]], i+1]을 해주면 오름차순으로 정답을 찾을 수 있다.

 

def icecreamParlor(m, arr):
    # Write your code here
    priceDic = dict()
    for i in range(len(arr)):
        if m-arr[i] in priceDic:
            return [priceDic[m-arr[i]], i+1]
        else:
            priceDic[arr[i]] = i+1

 

아래는 그냥 바로 풀어본 O(N^2)시간복잡도의 코드.

def icecreamParlor(m, arr):
    # Write your code here
    for i in range(len(arr)-1):
        for j in range(i+1, len(arr)):
            if arr[i] + arr[j] == m:
                return [i+1,j+1]