cmys1022   1년 전

여기저기 찾아보면서 map을 unordered_map으로 바꿔도보고 cin.tie()도 해봤는데 시간초과 나네요ㅜㅜ

어느 점을 개선해야 할까요??

tjgus1668   1년 전

32~44번째 줄에 있는 로직의 시간복잡도는 O(N)이고 Q번 실행하므로 총 시간복잡도는 O(NQ)입니다. N, M은 최대 100'000이므로 총 연산량은 대략 10^10인데, 보통 10^8을 1초에 연산할 수 있다고 보면 작성자님 코드는 100초가 걸리는 코드입니다.

힌트: map의 장점을 하나도 활용하지 못하고 있습니다. unordered_map은 key에 대한 임의 접근을 O(1), 즉 상수시간에 할 수 있다는 장점이 있는데, 현재 코드는 그저 컨테이너 내부를 순회하고 있습니다. 사용 방법을 다시 한번 공부해보시면 좋을 것 같습니다!

pokemonList.find 를 사용해보세요

hero00   1년 전

18번 라인에서 unordered_map에 값을 세팅했으니, 41번 라인처럼 굳이 map 전체를 순회하실 필요가 없습니다.

우선 15번 라인에서 시작하는 for 루프에서 포켓몬 이름들도 배열에 미리 받아둔 후에, strQ가 정수인 경우 이름 배열의 index로 접근하여 바로 값을 가져오고 문자열인 경우 윗분 말씀대로 find를 사용하거나, strQ가 (지문에 의해) 도감에 있는 이름만 주어지므로 map[strQ]로 접근하여 번호를 가져오심 될 것 같습니다.

zenith82114   1년 전

endl 대신 '\n'을 쓰세요.

cmys1022   1년 전

http://boj.kr/40497364104049cf...

@tjgus1668 @hero00 @zenith82114

세 분 말씀 모두 신경써서 코드 다시 수정해나가서 성공했습니다. 감사합니다!

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