문제 링크

문제

분석

팀이 될 수 있는 경우는 결국 사이클이 만들어지는 경우임.
학생 s1이 자기자신을 가리키는 경우.

혹은 s1 -> s2 ->s3 -> s1 처럼 가리키는 사람이 자기자신으로 돌아오는 경우임.

사이클이 만들어진다는 뜻은 사이클 내 모든 인원이 가리킴을 따라가면 결국 자기자신으로 돌아온다는 뜻으로, 이런 조건을 만족하는 경우만 같은 팀이라는 것.

조건 두번째

학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다.

일단 n이 100,000이라서 시각복잡도 n^2 이상을 사용할 수 없음.
또한 대량으로 입력받는 경우를 생각해서 sys.stdin.readline() 함수를 사용해야함.

구현

초기 코드

import sys
input = sys.stdin.readline


t = int(input())

테스트 케이스 마다 반복시킬 코드

for _ in range(t):

	# n을 입력받음.
    n = int(input())
    
    # n개의 학생이 가리키는 상대를 입력받음. 
    # 학생 번호가 1부터 시작해서 맨 처음 더미로 하나 넣어둠.
    l = [None] + [*map(int,input().split())]
    
    # 팀 형성 유무를 나타내는 데이터
    team = dict()
            
    # 팀으로 맺어진 학생수 
    matchedMember = 0
    
    # 1번부터 n번까지 진행
    for start in range(1,n+1):
    	# 팀원으로 형성 되지 않은 경우만 팀원 찾기 진행
     	if start not in team:
        	#findTeam 함수로 팀 매칭 시도함.
        	# 팀이 형성되었다면 팀의 팀원수를 얻음.
        	# 안되었으면 0을 받음.
        	result = findTeam(start)
        	matchedMember += result
    
    # 전체인원 - 팀으로 매칭된 인원
    answer = n - matchedMember 
    
    # 출력
    print(answer)

findTeam 함수

 def findTeam(start):
        global n,l,team
        cur = start
        
        history = dict()
        memberNum = 1

        while True:
            next = l[cur]
            
            
            if next == start:
                team[cur] = True
                for key in history:
                    team[key] = True
                return memberNum
            
            if next in history and next != start : 
                
                for key in history:
                    if key == next :
                        break
                    else:
                        team[key] = False
                return 0
                        
            if next not in team:
                history[cur] = None
                cur = next 
                memberNum += 1
                
                
            else:
                for key in history:
                    team[key] = False
                    
                return 0

findTeam 함수는 global 키워드 사용을 원활하게 하기 위해서 t로 돌아가는 for문 안에다가 작성함.

결과

반례 추천

1
3
2 3 3
ans:2


1
5
2 3 4 5 4
ans=3

1
4
2 3 4 2
ans=1


1
5
1 1 1 1 1
ans=4

1
5
2 3 4 5 3
ans=2