19596번 - 선물 교환 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 256 MB | 174 | 67 | 30 | 38.462% |
문제
사내 N명의 임직원이 심심풀이 선물 교환 이벤트를 열기로 했다. 임직원은 1부터 N까지 번호가 매겨져있다.
총 M쌍의 임직원쌍이 선택되었고, 각 쌍의 임직원은 둘 중 한 사람이 선물을 주고 다른 사람이 받아야 한다 (서로 줄 수 없다).
구체적으로 M개의 (X[i], Y[i]) 쌍이 선택되었고, 각 쌍에 대해 X[i]가 Y[i]에게 선물을 주거나 Y[i]가 X[i]에게 선물을 주어야만 한다.
다만, 선물을 주고 받는 재미를 더하기 위해 아래와 같은 규칙을 정했다:
- 각 임직원 i에 대하여, 임직원 i가 (다른 사람에게) 주는 선물의 수와 (다른 사람으로부터) 받는 선물의 수의 차이가 2미만이어야 한다
임직원쌍이 M개 있으므로 누가 누구에게 선물을 줄지 정하는 방법은 2M 가지 존재하는데, 이는 길이가 M인 0-1 문자열로 나타낼 수 있다 (이를 선물 문자열이라 하자).
구체적으로, X[i] 가 Y[i]에게 선물을 주는 경우를 '0'으로 나타내고 반대의 경우를 '1'로 나타내자.
예를 들어, N = 3, M = 2이고 임직원 쌍이 (2, 1) 과 (3, 1)이라 하자 (즉, X = [2, 3], Y = [1, 1])
- 선물 문자열이 00인 경우: 임직원 2와 임직원 3이 임직원 1에게 선물을 준다. 이 경우 임직원 1이 선물을 2개 받고 0개 주어서 규칙을 어긴다.
- 선물 문자열이 01인 경우: 임직원 2가 임직원 1에게, 임직원 1이 임직원 3에게 선물을 준다. 이 경우 규칙을 어기지 않는다.
- 선물 문자열이 10인 경우: 임직원 1이 임직원 2에게, 임직원 3이 임직원 1에게 선물을 준다. 이 경우 규칙을 어기지 않는다.
- 선물 문자열이 11인 경우: 임직원 1이 임직원 2와 임직원 3에게 선물을 준다. 이 경우 임직원 1이 규칙을 어긴다.
임직원의 수 N과 M개의 임직원 쌍이 주어졌을 때, 위 규칙을 어기지 않는 선물 문자열을 찾으시오.
위 예제의 경우 "01" 과 "10" 중 어느 것을 찾아도 정답이다.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 줄은 두 개의 정수 N과 M을 공백으로 구분하여 담고있다.
다음 M줄에 걸쳐서 임직원 쌍이 공백으로 구분되어 주어진다 (즉, X[i], Y[i]가 공백으로 구분되어 주어진다).
한 테스트 케이스 내에서 같은 쌍의 임직원은 최대 한 번만 입력으로 주어진다 (즉 x y가 한 번 입력으로 주어지면,x y 혹은 y x는 같은 테스트 케이스 내에서 다시 주어지지 않는다).
출력
각 테스트 케이스에 대해 규칙을 어기지 않는 (길이 M인) 선물 문자열 중 하나를 출력한다.
제한
- 1 ≤ T ≤ 10
- 2 ≤ N ≤ 1,000
- 1 ≤ M ≤ min(100,000, N*(N-1)/2)
예제 입력 1
5 3 2 2 1 3 1 3 3 1 2 2 3 1 3 4 4 1 2 1 3 2 3 2 4 4 5 2 1 1 3 2 3 2 4 4 1 6 3 1 2 3 4 5 6
예제 출력 1
01 001 0100 11011 000
시간 제한
- Java 8: 2 초
- Python 3: 4 초
- PyPy3: 4 초
- Java 8 (OpenJDK): 2 초
- Java 11: 2 초
- Python 2: 4 초
- PyPy2: 4 초
- Kotlin (JVM): 2 초
- Java 15: 2 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호