1. 문제 소개

3606. Coupon Code Validator

2. 나의 풀이

배열을 순회할 때 조건에 맞는 경우만 추출하고, 우선도 맵을 사용해서 정렬을 손쉽게 했다.
쿠폰 수를 $n$, 평균 쿠폰 코드 길이를 $L$이라고 할 때, 시간복잡도는 $O(n * L + n\, log n)$이다.

class Solution:
    def validateCoupons(self, code: List[str], businessLine: List[str], isActive: List[bool]) -> List[str]:
        # 비즈니스 라인별 우선순위 정의 (숫자가 작을수록 우선순위 높음)
        priority = {
            "electronics": 0,
            "grocery": 1,
            "pharmacy": 2,
            "restaurant": 3,
        }

        ans = []  # (우선순위, 쿠폰코드) 형태로 담을 리스트

        # 세 리스트를 동시에 순회하며 각 쿠폰을 검사
        for c, b, a in zip(code, businessLine, isActive):
            # 유효성 조건:
            # 1) 쿠폰 코드가 비어 있지 않을 것
            # 2) 활성 상태일 것
            # 3) 쿠폰 코드가 영문자/숫자/_ 로만 구성될 것
            # 4) 비즈니스 라인이 priority에 정의된 값일 것
            if c and a and all(s.isalnum() or s == "_" for s in c) and b in priority:
                # 조건을 만족하면 (우선순위, 쿠폰코드) 형태로 저장
                ans.append((priority[b], c))

        # 우선순위(첫 번째 원소)를 기준으로 정렬
        ans.sort()

        # 정렬된 결과에서 쿠폰 코드만 추출하여 반환
        return [c for _, c in ans]

3. 다른 풀이

비즈니스별로 배열을 다르게 계산하고, 이후에 순서대로 정렬한 풀이도 존재한다.
이 경우도 똑같은 시간복잡도 $O(n * L + n\, log n)$를 갖는다.

class Solution(object):
    def validateCoupons(self, code, businessLine, isActive):
        # 비즈니스 라인별로 유효한 쿠폰 코드를 담을 리스트
        e, g, p, r = [], [], [], []   # electronics, grocery, pharmacy, restaurant

        # 모든 쿠폰 인덱스를 순회
        for i in range(len(isActive)):
            # 비활성 쿠폰은 즉시 제외
            if not isActive[i]:
                continue

            bl = businessLine[i]

            # 허용된 비즈니스 라인이 아니면 제외
            if bl not in ("electronics", "grocery", "pharmacy", "restaurant"):
                continue

            # 쿠폰 코드가 비어 있으면 제외
            if not code[i]:
                continue

            # 쿠폰 코드가 영문자/숫자/언더스코어(_)만으로 구성되어 있는지 검사
            if not all(ch.isalnum() or ch == '_' for ch in code[i]):
                continue

            # 비즈니스 라인에 따라 해당 버킷에 쿠폰 코드 추가
            # startswith를 사용해 라인 구분
            if bl.startswith("e"): e.append(code[i])  # electronics
            if bl.startswith("g"): g.append(code[i])  # grocery
            if bl.startswith("p"): p.append(code[i])  # pharmacy
            if bl.startswith("r"): r.append(code[i])  # restaurant

        # 각 비즈니스 라인별로 정렬한 뒤,
        # 우선순위(e → g → p → r) 순으로 이어붙여 반환
        return sorted(e) + sorted(g) + sorted(p) + sorted(r)

4. 마무리

조건이 까다로워서 그렇지 쉬운 문제였다.