글 읽기 - 도와주세요…도저히 시간이 줄여지지 않습니다.

owj0421 1년 전 1

이 방법에서 더이상 어떻게 시간을 줄여야할지 모르겠습니다.

혹시나 스택이 아닌, 재귀함수로 구성하면 빠를지 똑같은 구성으로 재귀로 시도해도 시간초과가 뜨니…

제 머리에선 한계인 것 같습니다.

고수분들 제발 도와주시면 감사하겠습니다.

import sys
read = sys.stdin.readline

def getTeamByDFS(startPerson):
  tempTeam = [startPerson]
  isVisitedList[startPerson] = True
  stack = [startPerson]
  
  while stack:
    currentPerson = stack.pop()
    candidate = candidateList[currentPerson]

    if candidate in tempTeam:
      team = tempTeam[tempTeam.index(candidate):]
      return team
      
    elif not isVisitedList[candidate]:
      tempTeam.append(candidate)
      isVisitedList[candidate] = True
      stack.append(candidate)

  return []

TEST_CASE = int(read())
for _ in range(TEST_CASE):
  PEOPLE_NUM = int(read())
  candidateList = [0] + list(map(int, read().split()))
  isVisitedList = [False] * (PEOPLE_NUM + 1)

  peopleWithTeamList = []
  
  for person in range(1, PEOPLE_NUM + 1):
    if isVisitedList[person] == False:
      peopleWithTeamList += getTeamByDFS(person)

  print(PEOPLE_NUM - len(peopleWithTeamList))

bamgoesn 1년 전 1

이거 하나 해결하면 다 될지는 확실하지 않지만, 저라면 제일 먼저 13, 14행을 고쳐보려고 시도할 것 같습니다. 13행에서 리스트에 in 키워드를 사용함으로써 candidate가 tempTeam에 있는지 선형탐색을 하고 있습니다. 덤으로 14행에서 tempTeam.index()로 그 위치를 다시 한 번 선형탐색하고 있습니다.

tempTeam은 입력 내에서 매우 길게 연결된 체인이 있을 경우 크기가 커질 수 있습니다. 사람이 10만명 있는데 10만명이 모두 다음 사람을 가리킨다면 이 부분에서 시간복잡도가 O(n^2)으로 발생하겠죠? 이 부분을 최적화해보는 게 좋을 거라 생각합니다.

owj0421 1년 전 0

@bamgoesn

감사합니다! tempTeam에 있는지 확인 하는 과정을 Set를 이용해 O(1)로 바꾸니 해결되었습니다! 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

도와주세요…도저히 시간이 줄여지지 않습니다.

owj0421 1년 전 1

bamgoesn 1년 전 1

owj0421 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말