3606. 쿠폰 코드 검증기

Source: Dev.to

Problem Description

길이 n인 세 개의 배열이 주어집니다. 각각은 n개의 쿠폰 속성을 나타냅니다.

• code[i]: 쿠폰 식별자를 나타내는 문자열.
• businessLine[i]: 쿠폰이 속한 비즈니스 카테고리를 나타내는 문자열.
• isActive[i]: 쿠폰이 현재 활성화되어 있는지를 나타내는 불리언 값.

쿠폰이 유효하려면 다음 조건을 모두 만족해야 합니다.

1. code[i]는 비어 있지 않으며 알파벳 대소문자(a‑z, A‑Z), 숫자(0‑9), 그리고 밑줄(_)만으로 구성되어 있어야 합니다.
2. businessLine[i]는 다음 네 가지 카테고리 중 하나여야 합니다: "electronics", "grocery", "pharmacy", "restaurant".
3. isActive[i]가 true여야 합니다.

유효한 쿠폰들의 코드를 모두 반환하되, 먼저 businessLine 순서

"electronics" → "grocery" → "pharmacy" → "restaurant"

에 따라 정렬하고, 같은 카테고리 안에서는 code를 사전 순(오름차순)으로 정렬합니다.

Example 1

Input

code = ["SAVE20", "", "PHARMA5", "SAVE@20"]
businessLine = ["restaurant", "grocery", "pharmacy", "restaurant"]
isActive = [true, true, true, true]

Output

["PHARMA5", "SAVE20"]

Explanation

• 첫 번째 쿠폰은 유효합니다.
• 두 번째 쿠폰은 코드가 비어 있어 → 무효.
• 세 번째 쿠폰은 유효합니다.
• 네 번째 쿠폰은 특수 문자 @가 포함되어 있어 → 무효.

필터링 후 남은 코드를 비즈니스 라인(pharmacy가 restaurant보다 먼저) 순으로, 그리고 각 라인 안에서는 코드 순으로 정렬합니다.

Example 2

Input

code = ["GROCERY15", "ELECTRONICS_50", "DISCOUNT10"]
businessLine = ["grocery", "electronics", "invalid"]
isActive = [false, true, true]

Output

["ELECTRONICS_50"]

Explanation

• 첫 번째 쿠폰은 비활성 → 무효.
• 두 번째 쿠폰은 유효.
• 세 번째 쿠폰은 비즈니스 라인이 허용된 값이 아니므로 무효.

Constraints

• n == code.length == businessLine.length == isActive.length
• 1 ≤ n ≤ 100
• 0 ≤ code[i].length, businessLine[i].length ≤ 100
• code[i]와 businessLine[i]는 출력 가능한 ASCII 문자로 구성됩니다.
• isActive[i]는 true 또는 false 중 하나입니다.

Hint

1. 다음 조건을 만족하지 않는 쿠폰을 모두 걸러냅니다.
   • isActive[i]가 false인 경우
   • code[i]가 비어 있거나 알파벳·숫자·밑줄 이외의 문자를 포함하는 경우
   • businessLine[i]가 허용된 집합에 속하지 않는 경우
2. 남은 각 쿠폰을 (businessLine[i], code[i]) 쌍으로 저장합니다.
3. 우선순위 맵을 정의합니다. 예: { "electronics":0, "grocery":1, "pharmacy":2, "restaurant":3 }.
4. (우선순위, code)를 기준으로 리스트를 정렬하고, 정렬된 순서대로 code 값을 반환합니다.

Solution Overview

1. Validation

   • 정규식 ^[a-zA-Z0-9_]+$를 사용해 code를 검사합니다.
   • isActive가 true인지 확인합니다.
   • businessLine이 허용된 집합에 속하는지 검증합니다.

2. Mapping Priority
   각 비즈니스 라인에 정렬 우선순위를 매핑하는 연관 배열을 만듭니다.

3. Sorting

   • 모든 유효 쿠폰을 연관 배열 { "line": ..., "code": ... } 형태로 수집합니다.
   • usort와 사용자 정의 비교 함수를 이용해 먼저 우선순위 값을 비교하고, 같을 경우 strcmp로 코드를 사전 순으로 비교합니다.

4. Result Extraction
   정렬이 끝난 뒤 code 필드만 추출해 최종 결과 배열을 반환합니다.

PHP Implementation

 0,
        "grocery"     => 1,
        "pharmacy"   => 2,
        "restaurant" => 3,
    ];

    $valid = [];

    $n = count($code);
    for ($i = 0; $i  $businessLine[$i],
            'code' => $code[$i],
        ];
    }

    // Sort by business line priority, then by code lexicographically
    usort($valid, function ($a, $b) use ($priority) {
        $pA = $priority[$a['line']];
        $pB = $priority[$b['line']];

        if ($pA !== $pB) {
            return $pA  $pB;
        }
        return strcmp($a['code'], $b['code']);
    });

    // Extract only the codes
    return array_column($valid, 'code');
}

// ----- Test cases -----
print_r(validateCoupons(
    ["SAVE20", "", "PHARMA5", "SAVE@20"],
    ["restaurant", "grocery", "pharmacy", "restaurant"],
    [true, true, true, true]
)); // Expected: ["PHARMA5", "SAVE20"]

print_r(validateCoupons(
    ["GROCERY15", "ELECTRONICS_50", "DISCOUNT10"],
    ["grocery", "electronics", "invalid"],
    [false, true, true]
)); // Expected: ["ELECTRONICS_50"]
?>

Complexity Analysis

• Time Complexity: O(n log n) — 필터링은 선형이며, 정렬이 n개의 유효 쿠폰(≤ 100) 개수에 대해 log n을 곱한 것이 지배합니다.
• Space Complexity: O(n) — 유효 쿠폰 리스트를 저장하기 위한 추가 공간이 필요합니다.