학생마다 연결된 목록을 찾아들어가면서 List에 기록하고 

싸이클이 생기면(List에 포함되어있는 값을 다시 넣으려고하면) 

list에 있는 학생중, 싸이클에 포함되지 않는 학생은 -1로 처리하고 포함되면 1로 처리하는 방식으로 풀어서 80%까지 채점됐는데 

시간초과가 떴습니다.

그래서 시간이 걸릴 만한 부분이 어디일까 보던중 79번줄에 selected.contains(iWant) 여기가 반복마다 확인하려면 오래 걸릴꺼같아서 


54번줄 아래에 boolean isSelected[] = new boolean[stNum+1]; 를 두고 isSelected[iWant]로 상수시간에 확인 하도록 하였습니다.

근데 제출하니깐 1%에서 시간초과가 뜨네요? 속도는 훨씬 빨라졌을 텐데 

어디서 루프가 도는 걸까요? 입력문제일까요?


-> 루프 인지 확인하려고 while(true) 속에서 학생수 이상으로 반복 돌면 "dasdasd" 문자열 출력하게 했는데 

"틀렸습니다"가 아니라 여전히 1%에서 시간초과가 나네요 도대체 무슨 경우에 걸려서 80%까지 가던게 

boolean 배열로 상수시간 접근하니깐 1%에서 멈추는 건지 이해가 안되네요  

zlzmsrhak   9달 전

1. 확인된 점을 확인하는 부분에서, teamflag의 값은 -1도 가능하기 때문에 그부분을 확인해야 할 것 같습니다.

2. 말씀하신대로 79번 줄이 남아있으면 N^2이 될 것 같고, boolean 배열을 써야 하는 것 같습니다. 다만 구현상에서 문제가 생겨 시간초과가 나는 것 같습니다.

감사합니다 ㅎㅎ
boolean 배열을 사용하는건 계속 1%에서 시간초과 나서 같은위치에 map을 사용해서 꾸역꾸역 풀었습니다 
boolean 배열을 쓰면 뭐가 문제였을까요??
아래는 boolean배열을 사용한 코드입니다

zlzmsrhak   9달 전

앞쪽에 큰 데이터가 있는것인지는 모르겠지만, isSelected 배열을 N번 선언하기 때문에 N^2 시간복잡도를 가지게 되어 시간초과가 나는 것 같습니다.

오 그러면 전역으로 선언하고 넣고 빼는 식으로 테스트 해보겠습니다~!

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