문제
이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.
학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.
예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.
1 2 3 4 5 6 7
3 1 3 7 3 4 6
위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.
주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)
출력
각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.
알고리즘 초안 작성
- 인풋을 그래프로 생성
- 1번 부터 스택에 넣음 (N번 까지 반복)
- 스택에서 하나씩 꺼냄
- 방문 혹은 루프면 스킵
- 방문 처리 후 방문 기록에 넣음
- 다음 노드 선택
- 본인을 가리키면 루프처리 하고 팀멤버에 넣고 스킵
- 가리키는 노드가 첫 노드이면 루프처리 하고 팀멤버에 넣고 스킵
- 가리키는 노드를 스택에 넣음
소스 코드
// 1. 인풋을 그래프로 생성
val T = readLine()!!.toInt()
repeat(T) {
result = 0
val N = readLine()!!.toInt()
val graph: Array<Int> = Array(N+1) {0}
val visit: Array<Boolean> = Array(N+1) {false}
val loop: Array<Boolean> = Array(N+1) {false}
readLine()!!.split(' ').forEachIndexed { index, s ->
graph[index+1] = s.toInt()
}// 2. 1번 부터 스택에 넣음 (노드 수 만큼 반복) 2 <= N <= 100,000
for (i in 1..N) {
val visitList = LinkedList<Int>()
val stack = Stack<Int>()
stack.push(i)
...
} while (stack.isNotEmpty()) {
// 3. 스택에서 하나씩 꺼냄
val node = stack.pop()
// 4. 방문 혹은 루프면 스킵
if (visit[node] || loop[node]) {
break
}
// 4. 방문 처리 후 방문 기록에 넣음
visit[node] = true
visitList.add(node)
...
}// 5. 본인을 가리키면 루프처리 하고 팀멤버에 넣고 스킵
val next = graph[node]
if (node == next) {
loop[node] = true
result++ // *변경점*
break
}변경점 : 시간 감소를 위해 팀 멤버에 추가하는 것이 아닌 팀을 구성한 인원 수만 체크하면 되므로 결괏값을 하나씩 늘려주는 로직으로 변경
// *변경점*
if (visit[next]) {
// 6. 가리키는 노드가 방문 기록에 있으면 걔네를 루프처리 하고 팀멤버에 넣고 스킵
val index = visitList.indexOf(next)
if (index != -1) {
result += abs(index-visitList.lastIndex) + 1
break
}
}변경점 : '가리키는 노드가 첫 노드라면 루프처리한다' 가 잘못되었고, 해당 반례는 (1) - (4) - (7) - (6) - (4) 의 경우 (4, 7, 6)이 루프지만 첫 노드가 아니라서 판별하지 못한다. 따라서, 방문 기록에 존재하면 루프라고 로직을 변경하였고, 해당 상태에서 계속 시간 초과가 났다. 계~속 고민해본 결과 visitList.indexOf() 함수 자체가 결국엔 visitList를 리니어 서치하는 것과 같기 때문에 해당 부분에 변경을 줘야 했고, 위의 코드 첫 줄 If 문이 없다면 모든 노드에 대해 수행되기 때문에 시간 초과가 난다고 판단해 다음 노드가 이미 방문했던 노드인 경우에만 실행되도록 변경했더니 통과하였다!
최종 코드
import java.util.LinkedList
import java.util.Stack
import kotlin.math.abs
import kotlin.time.ExperimentalTime
import kotlin.time.TimedValue
import kotlin.time.measureTimedValue
/*
1. 인풋을 그래프로 생성
2. 1번 부터 스택에 넣음
3. 스택에서 하나씩 꺼냄
4. 방문 혹은 루프면 스킵
4. 방문 처리 후 방문 기록에 넣음
5. 본인을 가리키면 루프처리 하고 팀멤버에 넣고 스킵
6. 가리키는 노드가 첫 노드이면 루프처리 하고 팀멤버에 넣고 스킵
4. 가리키는 노드를 스택에 넣음
*/
@OptIn(ExperimentalTime::class)
fun main() {
val solution = Solution()
solution.solution()
}
/*
2
7
3 1 3 7 3 4 6
8
2 1 3 4 5 6 7 8
*/
class Solution {
var result = 0
fun solution() {
// 1. 인풋을 그래프로 생성
val T = readLine()!!.toInt()
repeat(T) {
result = 0
val N = readLine()!!.toInt()
val graph: Array<Int> = Array(N+1) {0}
val visit: Array<Boolean> = Array(N+1) {false}
val loop: Array<Boolean> = Array(N+1) {false}
readLine()!!.split(' ').forEachIndexed { index, s ->
graph[index+1] = s.toInt()
}
// 2. 1번 부터 스택에 넣음 (노드 수 만큼 반복) 2 <= N <= 100,000
for (i in 1..N) {
val visitList = LinkedList<Int>()
val stack = Stack<Int>()
stack.push(i)
while (stack.isNotEmpty()) {
// 3. 스택에서 하나씩 꺼냄
val node = stack.pop() // node 6 first 4 visit[1][2][4][7][6] t, loop[3][4][7][6] t, visitlist (4)(7)(6), result (3)(4)(7)
// 4. 방문 혹은 루프면 스킵
if (visit[node] || loop[node]) {
break
} // visit[6] f loop[6] f
// 4. 방문 처리 후 방문 기록에 넣음
visit[node] = true // visit[1] t
visitList.add(node) // visitlist (9)(10)(4)(7)(6)(4)
// 5. 본인을 가리키면 루프처리 하고 팀멤버에 넣고 스킵
val next = graph[node] // next 4
// temp
if (node == next) { // f
loop[node] = true // loop[3] t
result++ // result (3)
break
}
if (visit[next]) {
// 6. 가리키는 노드가 방문 기록에 있으면 걔네를 루프처리 하고 팀멤버에 넣고 스킵
val index = visitList.indexOf(next)
if (index != -1) {
result += abs(index-visitList.lastIndex) + 1
break
}
}
// 4. 가리키는 노드를 스택에 넣음
stack.push(next) // stack (2)
}
}
println(N-result)
}
}
}
// 100,000 1 -> 2 -> 3 ... -> 100,000 -> 1
