attack1021   1년 전

std::set 을 사용했구요,

set이 중복값들을 걸러주는 것을 이용해서 사이즈가 달라지면 0 / 그대로면 1 로 처리했습니다.

그런데 시간초과가 나는 이유가 무엇일까요...?ㅠㅠㅠㅠ

not_strober   1년 전

이렇게 입출력이 많은 문제는 빠른 입출력 코드를 쓰지 않으면 올바른 풀이로도 시간 초과를 받을 수 있습니다.
빠른 A + B 를 풀어보지 않으셨다면 풀어보시는 걸 추천합니다.
여담으로, set의 count 함수를 쓰면 insert -> size 조회를 하지 않고 바로 알 수 있고 시간도 더 빠릅니다.

azruine   1년 전

1. set은 정렬된 상태를 유지해야 해서, 삽입과 검색에 log 시간이 걸립니다. 이런 오버헤드가 없는 unordered_set의 경우에는 빠른 입출력 코드 없이도 통과가 됩니다.

2. 위와 연결되어서, 50만개를 삽입하고 또 50만개를 추가로 삽입하는 것보다는 50만개를 삽입하고, set에서 검색만 하는게 더 빠릅니다.

attack1021   1년 전

해결했습니다 감사합니다!

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