문제링크
풀이 전 계획 및 생각
문제를 읽으면서 방향 그래프 구조가 그려져서 이를 활용해서 문제를 풀어야겠다는 생각을 했다.
1번부터 n번까지의 학생이 있으면, 1번 학생부터 쭉 확인하면서 진행했다.
문제에서 나온 예시로 설명을하면
1->3
2
4->7->6
5
이런 식으로 한 번 시작해서 새롭게 지명되는 사람이 없을 때까지 확인하는 과정을 거쳤다.
확인한 사람은 visited 배열에서 현재 구성하고있는 그룹의 넘버로 값을 변경해주었다. 그 다음으로 visited 배열을 한 번 더 돌면서 그룹의 넘버와 같은 값을 가진 사람들은 -1로 값을 변경해줘서 이 사람들은 지목도 되었고 그룹이 결성되었음을 표시했다.(그룹별 구성원을 확인할 필요가 없었기 때문에 이렇게했다.) 그 이유는 한 번 팀구성을 진행했다가 실패한 사람은 '한 명당 한 명씩 지목 가능'이라는 조건 때문에 어차피 팀 빌딩에 실패하기 때문이다.
모든 학생에대해서 지목 및 팀 구성을 끝내면 -1로 설정된 학생들이 아닌 학생들은 팀 빌딩에 실패한 것이기 때문에, 그 학생들의 수만 카운트해주는 방식으로 풀었다.
풀이
import sys
def team_check(array,start):
global team_complete, team_fail, group_num
pick = start
while not visited[pick]:
visited[pick] = group_num
pick = array[pick]
while visited[pick] == group_num:
visited[pick] = -1
pick = array[pick]
group_num += 1
for _ in range(int(sys.stdin.readline())):
n = int(sys.stdin.readline())
array = [-1] + list(map(int, sys.stdin.readline().split()))
team_fail = 0
group_num = 1
visited = [0]*(n+1)
for i in range(1,n+1):
if visited[i] == 0:
team_check(array,i)
for i in range(1,n+1):
if visited[i] > 0:
team_fail += 1
print(team_fail)
풀이하면서 막혔던 점과 고민했던 점
시간 제한이 3초여서 연산이 많아도 상관없다는 생각을 했는데, 큰 오산이였다. 객체 안에 값이 존재하는지 보는 if i in list: 연산이 생각보다 시간을 많이 잡아먹어서 시간초과가 떴었다. 그래서 배열을 이용해서 마킹하는 방식으로 O(1)에 존재여부를 판단하는 코드로 바꿔서 해결할 수 있었다.
풀이 후 알게된 개념과 소감
객체 안에 값이 존재하는지 보는 if i in list: 연산이 생각보다 시간을 많이 잡아먹는다는 것을 배웠다. 앞으로 문제 풀 때, 잘 생각하면서 풀어야겠다.
