BOJ 4118 - Fred's Lotto Tickets

문제

BOJ 4118 - Fred's Lotto Tickets

프레드는 여러 장의 로또 티켓을 가지고 있다. 각 티켓에는 1부터 49 사이의 서로 다른 숫자 6개가 적혀 있다. 모든 티켓에 적힌 번호를 합쳤을 때 1부터 49까지의 모든 번호가 빠짐없이 등장하면 Yes, 그렇지 않으면 No를 출력한다.

입력

여러 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 티켓 수 n이 주어진다. n이 0이면 입력이 종료된다. 이후 n * 6개의 정수가 주어진다.

출력

각 테스트 케이스마다 모든 번호(1~49)가 포함되면 Yes, 아니면 No를 출력한다.

예제

풀이

set에 모든 번호를 삽입한 뒤 크기가 49인지 확인한다.

1. 테스트 케이스마다 set을 초기화한다.
2. n * 6개의 번호를 set에 삽입한다.
3. set의 크기가 49이면 Yes, 아니면 No를 출력한다.
4. n == 0이면 반복을 종료한다.

핵심 아이디어: set은 중복을 자동으로 제거하므로, 모든 티켓 번호를 삽입한 뒤 크기가 49인지만 확인하면 1~49의 완전한 커버 여부를 알 수 있다.

코드

#include <iostream>
#include <set>
 
using namespace std;
 
set<int> s;
 
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
 
  int n, t;
 
  while (true)
  {
    cin >> n;
    if (n == 0)
    {
      break;
    }
 
    for (int i = 0; i < n * 6; i++)
    {
      cin >> t;
      s.insert(t);
    }
 
    if (s.size() == 49)
    {
      cout << "Yes\n";
    }
    else
    {
      cout << "No\n";
    }
    s.clear();
  }
}

복잡도

• 시간: O(N log N) — N개의 번호를 set에 삽입하는 비용
• 공간: O(1) — 최대 49개의 번호만 저장 (상수)