pcgos1   4년 전

처음에 C++로 구현했다가 ㅠㅠ 

시간초과가 떠서 cin과 cout을 없애고, 동적할당 역시 그냥 일정 크기로 배열로 만들어서 사용했습니다.

함수같은경우도 최소한으로 줄였는데 시간초과가 뜨는데 해결방법을 모르겠습니다. ㅠㅠ

고수분들 조금만 도와주세요.

sgchoi5   4년 전

이 문제는 최대값이 1000000 이라는게 힌트입니다. 

소팅을 할 필요가 없습니다.

pcgos1   4년 전

머지소팅을 할 필요가 없다는 의미입니까???

소팅은 정렬 시키는걸 의미하는데, 필요한거 아닌가요? ㅠㅠ

sgchoi5   4년 전

수의 개수 N(1<=N<=1,000,000) 이지만, 수는 절대값이 1,000,000보다 작거나 같은 정수이고, 수는 중복되지 않는다라고 되어 있습니다.

그럼, bool array 의 크기를 2000000 + 1 으로 하고 (대략 1MB) 들어오는 입력에 1000000 를 더해 줍니다. 그럼, 입력값은 array 가 cover 하는 범위내에 있습니다.

-1000000 ~ 1000000 에서 +1000000 해서 0~2000000 로 입력값을 array index 로 맞춰줌

입력마다 해당 array index 로 true 를 설정하면 됩니다. 입력이 끝나면 0 부터 검사하면서 true 이면 -1000000 해서 원래 값으로 만들고 출력만 해주면 됩니다.

그럼, sort 안 해도 됩니다.

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