[Hackerrank] Ice Cream Parlor

아이스크림 가게 문제

두 명의 친구가 함께 돈을 모아 아이스크림 가게에 갔습니다.
그들은 항상 두 가지 다른 맛의 아이스크림을 구매하며, 가진 돈을 모두 사용합니다.

문제
주어진 아이스크림의 가격 리스트에서, 친구들이 가진 돈 m을 정확히 사용하여 구매할 수 있는 두 가지 맛의 아이스크림을 선택하세요.

---

입력 형식

첫 번째 줄: 정수 t (테스트 케이스 개수)
각 테스트 케이스는 다음과 같이 구성됩니다:

1. 정수 m (가진 돈의 총액)
2. 정수 n (아이스크림의 종류 수)
3. n개의 정수로 이루어진 리스트: 각 아이스크림 맛의 가격

---

출력 형식

각 테스트 케이스에 대해, 선택된 두 아이스크림 맛의 인덱스를 오름차순으로 출력합니다.
1부터 시작하는 인덱스를 사용해야 합니다.

---

제약 조건

• 1 ≤ t ≤ 50
• 2 ≤ m ≤ 10⁴
• 2 ≤ n ≤ 10⁴
• 1 ≤ 가격 ≤ 10⁴

---

예제 입력

m = 6 가격 리스트: [1, 3, 4, 5, 6]

---

예제 출력

가진 돈 m = 6으로 구매할 수 있는 두 가지 맛의 조합은 1번 맛(가격 1)과 5번 맛(가격 5)입니다.
결과 출력: [1, 5]

 

문제 제약을 보면 n, 리스트의 길이가 10^4으로 매우 작다. 그래서 O(n^2)을 사용해도 문제가 해결될 것이라고 생각했다. 그래서 이중 for문을 이용해서 모든 원소를 하나씩 돌아가며 2개의 원소의 합이 m과 동일하면 그 순간의 인덱스 2개를 return 하는 코드를 작성하였다. 문제 조건 중 답은 유일하다는 조건이 있으니 정답에 문제가 없다.

코드는 다음과 같다.

def icecreamParlor(m, arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == m:
                return [i + 1, j + 1]

위 코드는 O(n^2)의 시간 복잡도를 가지는데, 딕셔너리를 이용하면 O(n), 즉 한 번의 순회로 문제를 해결할 수 있다.

코드는 다음과 같다.

def icecreamParlor(m, arr):
    value_to_index = {}
    for i, value in enumerate(arr):
        complement = m - value
        if complement in value_to_index:
            return [value_to_index[complement] + 1, i + 1]
        value_to_index[value] = i

먼저 value_to_index 딕셔너리로 이미 방문한 값을 저장하고, 현재 값을 확인할때 필요한 짝(m - 값)이 이미 존재하는지 확인하고, 만약 존재한다면 현재 인덱스와 딕셔너리에 저장된 인덱스를 반환한다.

위 방법을 사용한다면 O(n)의 시간 복잡도로 문제 해결이 가능하다.