모든 챌린지
보통 0명 해결 정답률 0%

복권 당첨 집계

복권마다 당첨 번호를 0개, 1개, 2개, ... 맞힌 장수를 셉니다.

배우게 될 내용

  • 집합으로 포함 여부를 빠르게 확인한다
  • 복권마다 맞힌 개수를 센다
  • 점수의 히스토그램을 만든다

문제

원문 보기 (영어)

학교 모금 행사에서 번호 추첨 복권을 엽니다. 추첨에서는 서로 다른 당첨 번호 몇 개를 뽑고, 모든 복권에는 같은 개수의 서로 다른 번호가 적혀 있습니다. 복권에 적힌 번호의 순서는 상관없으며, 복권의 점수는 그 번호 중 당첨 번호가 몇 개인지입니다. 상품을 정하기 위해 주최 측은 점수별로 복권이 몇 장인지 알아야 합니다.

ticket_lottery(winning, tickets) 함수를 구현하세요.

입력

winning: 서로 다른 당첨 번호들입니다.

tickets: 복권들입니다. 각 행은 복권 한 장에 적힌 서로 다른 번호이며, 길이는 winning과 같습니다.

출력

길이가 len(winning) + 1인 리스트를 반환하세요. k번 위치의 값은 당첨 번호를 정확히 k개 맞힌 복권의 장수입니다.

제약 조건

1 ≤ len(winning) ≤ 10

0 ≤ 복권 장수 ≤ 5,000

1 ≤ 모든 번호 ≤ 99

예시

예시 1
입력:
winning = [3, 11, 20]
tickets = [
    [3, 11, 20],
    [20, 5, 7],
    [1, 2, 4],
    [11, 3, 9]
]

예상 출력:
expected = [1, 1, 1, 1]
입력:
std::vector<long long> winning = {3, 11, 20};
std::vector<std::vector<long long>> tickets = {
    {3, 11, 20},
    {20, 5, 7},
    {1, 2, 4},
    {11, 3, 9}
};

예상 출력:
std::vector<long long> expected = {1, 1, 1, 1};
입력:
long[] winning = new long[] {3, 11, 20};
long[][] tickets = new long[][] {
    new long[] {3, 11, 20},
    new long[] {20, 5, 7},
    new long[] {1, 2, 4},
    new long[] {11, 3, 9}
};

예상 출력:
long[] expected = new long[] {1, 1, 1, 1};

설명

복권들은 각각 3개, 1개, 0개, 2개를 맞혔으므로 0부터 3까지 점수마다 한 장씩입니다. 결과는 [1, 1, 1, 1]입니다.

예시 2
입력:
winning = [7, 8]
tickets = [
    [8, 7],
    [7, 1],
    [1, 7]
]

예상 출력:
expected = [0, 2, 1]
입력:
std::vector<long long> winning = {7, 8};
std::vector<std::vector<long long>> tickets = {
    {8, 7},
    {7, 1},
    {1, 7}
};

예상 출력:
std::vector<long long> expected = {0, 2, 1};
입력:
long[] winning = new long[] {7, 8};
long[][] tickets = new long[][] {
    new long[] {8, 7},
    new long[] {7, 1},
    new long[] {1, 7}
};

예상 출력:
long[] expected = new long[] {0, 2, 1};

설명

한 장은 두 번호를 모두 맞혔고(순서는 상관없음) 두 장은 하나씩 맞혔으므로 [0, 2, 1]입니다.

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

당첨 번호를 집합이나, 번호를 인덱스로 쓰는 불리언 배열에 넣으세요.

힌트 2

복권 한 장의 맞힌 개수를 센 다음, 그 점수의 칸에 1을 더하세요.

힌트 3

결과의 칸 수는 당첨 번호 개수보다 하나 많습니다.

예상 복잡도

시간 O(t × k), 추가 공간 O(k)

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.