쿠폰 금액 딱 맞추기

문제

어느 쇼핑몰에는 "두 상품 합계가 쿠폰 금액과 정확히 같을 때만" 쓸 수 있는 특별 쿠폰이 있습니다.

장바구니에 담긴 상품들의 상품ID 목록 ids와 가격 목록 prices가 같은 순서로 주어집니다. 즉 i번째 상품의 ID는 ids[i], 가격은 prices[i]입니다.

장바구니에서 서로 다른 두 상품을 골라 가격의 합이 쿠폰 금액 coupon과 정확히 같아지는 조합이 있으면, 그 두 상품의 ID를 사전순 오름차순으로 담은 배열 [작은ID, 큰ID]를 반환하세요. 그런 조합이 없으면 빈 배열 []을 반환하는 solution(ids, prices, coupon) 함수를 작성하세요.

예시

ids = ["milk", "bread", "jam", "tea"]
prices = [3200, 2800, 5400, 1500]
coupon = 4300
→ ["bread", "tea"]
  bread(2800) + tea(1500) = 4300. 사전순으로 bread가 앞서므로 이 순서로 반환한다.
 
ids = ["soap", "towel", "brush"]
prices = [1200, 4500, 2600]
coupon = 10000
→ []
  어떤 두 상품을 골라도 합이 10000이 되지 않는다.
 
ids = ["pen", "note"]
prices = [900, 900]
coupon = 1800
→ ["note", "pen"]
  가격이 같아도 서로 다른 상품이므로 조합이 가능하다. 사전순으로 note가 앞선다.

제약 조건

• 2 ≤ ids.length = prices.length ≤ 100,000
• 상품ID는 영소문자·숫자로 이루어진 1~10자 문자열이며, 서로 중복되지 않습니다
• 1 ≤ prices[i] ≤ 1,000,000
• 1 ≤ coupon ≤ 2,000,000
• 같은 상품을 두 번 고를 수는 없습니다 (서로 다른 두 위치여야 합니다)
• 조건을 만족하는 상품 쌍은 최대 한 쌍만 존재합니다

시간 복잡도 목표: O(N)