백준 12033 - 김인천씨의 식료품가게 (Small)

설명

입출력 및 제한 사항

풀이

시간제한이 무려 5초..!이고 상품의 수는 4개까지밖에 없는 몹시 귀여운 문제이다. 주어진 값들을 순회하면서 75% 값을 찾고 있으면 정답 배열에 넣어주는 식으로 풀이했다.

여기서 주의해야 할 점은 동일한 값이 여러 개 있는 경우이다.

이런 입력이 있을 때 12의 4/3인 15는 하나 밖에 없으므로 정답은 9 9 12 15가 되어야한다. 사전형으로 각 숫자가 몇 개 있는지 확인하고 빼주는 방식으로 해결했다.

 

핵심은 다음과 같다.

정상가: 4의 배수 (정상가 × 3/4 = 할인가가 정수)

할인가: 3의 배수 (할인가 × 4/3 = 정상가가 정수)

12의 배수(예: 300) 는 할인가도 될 수 있고 정상가도 될 수 있음. -> 역할이 모호함

 

정렬만 믿고 “현재 값 i에 대해 i*4 // 3 이 있으면 i는 할인가”로 처리하면,

12의 배수에서 잘못된 쪽(큰 쪽과 짝) 으로 먼저 매칭해버려서 나중에 작은 쪽과의 필수 매칭이 깨질 수 있다.
정답이 유일하다는 조건에서도, 구현이 “남은 것들” 기준이 아니라 “원본 배열을 그대로 한 번씩 스캔”하는 방식이면 이런 반례가 생기는 것을 주의해야한다.

-> 남아 있는 값들 중 최솟값은 반드시 할인가 (정렬 + 정답 존재 조건에 의해 성립)

내 코드

import sys
input = sys.stdin.readline
mis = lambda: map(int, input().split())

t = int(input())
for TC in range(1, t+1):
    n = int(input())
    products = [*mis()]
    products_counter = dict()
    for i in products:
        products_counter[i] = products_counter.get(i, 0) + 1
    
    ans = []
    for i in products:
        if products_counter.get(i, 0) == 0:
            continue

        origin = i * 4 // 3
        if products_counter.get(origin, 0) > 0:
            ans.append(i)
            products_counter[origin] -= 1
            products_counter[i] -= 1

    print(f"Case #{TC}:", *ans)

주어진 배열을 두 번 순회하기 때문에 시간 복잡도는 O(2n)