처음으로 모순이 생기는 요청
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 20000 ms
- 푼 사람
- 0
스위치 n개가 있고 각 스위치는 켜짐(true) 또는 꺼짐(false) 중 하나입니다. 스위치 번호는 1부터 n까지입니다.
요청이 clauses 순서대로 하나씩 들어옵니다. 요청 clauses[i] = [x, y]는 "x 또는 y 중 적어도 하나는 지켜 달라"는 뜻입니다. 각 수는 다음과 같이 읽습니다.
- 양수
v— "v번 스위치가 켜져 있어야 한다" - 음수
-v— "v번 스위치가 꺼져 있어야 한다"
x와 y가 같은 스위치를 가리킬 수도 있습니다. 예를 들어 [3, 3]은 "3번은 반드시 켜짐", [2, -2]는 항상 지켜지는 요청입니다.
요청을 앞에서부터 받아들이다 보면, 어느 순간 지금까지의 요청을 모두 만족하는 스위치 상태가 존재하지 않게 될 수 있습니다. 그렇게 만드는 첫 요청의 인덱스(0부터)를 반환하세요. 모든 요청을 동시에 만족할 수 있으면 -1을 반환합니다.
입출력 예
| n | clauses | result |
|---|---|---|
3 | [[1, 2], [-1, 3], [-2, -3], [-3, 1]] | -1 |
2 | [[1, 1], [-1, 2], [-2, -1], [2, 2]] | 2 |
2 | [[1, 2], [-1, 2], [1, -2], [-1, -2]] | 3 |
입출력 예 설명
예 1 — 1번 켜짐, 2번 꺼짐, 3번 켜짐이면 네 요청이 모두 지켜집니다.
예 2 — 요청 0은 1번을 켜게 하고, 요청 1("1번 꺼짐 또는 2번 켜짐")은 2번을 켜게 합니다. 요청 2("2번 꺼짐 또는 1번 꺼짐")는 이제 지킬 수 없으므로 답은 2입니다.
예 3 — 처음 세 요청은 두 스위치를 모두 켜면 지켜지지만, 네 요청을 합치면 두 스위치의 어떤 조합도 통하지 않습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(n: int, clauses: int[][]) → int
제한 사항
-
n -
clauses.length clauses[i] = [x, y],n(0은 나오지 않습니다)
기대 복잡도
- 시간
- O((N + M) log M)
- 공간
- O(N + M)
입출력 예
| n | clauses | 기대 출력 |
|---|---|---|
3 | [[1,2],[-1,3],[-2,-3],[-3,1]] | -1 |
2 | [[1,1],[-1,2],[-2,-1],[2,2]] | 2 |
2 | [[1,2],[-1,2],[1,-2],[-1,-2]] | 3 |
힌트
힌트
1. 한 번의 판정 — 2-SAT
요청 "a 또는 b"는 두 개의 함의와 같습니다: "a가 거짓이면 b", "b가 거짓이면 a". 리터럴(스위치 v의 켜짐/꺼짐) 개를 정점으로, 함의를 간선으로 하는 함의 그래프를 만듭니다.
어떤 스위치의 "켜짐"과 "꺼짐"이 **같은 강한 연결 요소(SCC)**에 있으면 서로를 강제하므로 모순이고, 그런 스위치가 없으면 반드시 해가 존재합니다. 타잔/코사라주 알고리즘으로 에 판정합니다.
2. 첫 모순 위치 — 이분 탐색
요청을 추가하면 조건이 늘어날 뿐이므로, "앞의 k개를 만족할 수 있는가"는 k에 대해 단조입니다(한 번 불가능해지면 계속 불가능). 따라서 가능한 마지막 k를 이분 탐색하면 판정을 번만 하면 됩니다.
복잡도 목표
입니다. 요청을 하나 받을 때마다 다시 판정하는 풀이는 효율성 테스트에서 시간 초과가 납니다. 재귀 DFS는 깊이가 까지 갈 수 있으니 언어에 따라 반복문으로 구현하세요.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 364 ms | 추정 |
| C++ (GCC, gnu++23) | 364 ms | 도출됨 |
| Python 3.13 | 6948 ms | 도출됨 |
| Java 25 | 2034 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1728 ms | 추정 |
| C# 14 (.NET 10) | 1728 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 4 | 판정만 |