kdr06006   4년 전

C++ STL 안에 set을 사용해서 문제를 풀었습니다.

그런데 시간초과가 나서 다른 풀이 방법을 찾아보다가 안 떠올라서 unordered_set으로 바꿔서 냈는데 맞았습니다가 떴습니다.

물론 set을 사용해서 문제를 푸신 분들도 계실겁니다.

하지만 문제에서 요구하는 풀이는 단순히 set을 사용하는 풀이같은데 시간 제한이 너무 빡빡한 것 같습니다.

시간 제한을 조금만 늘려주시면 감사하겠습니다.

참고용으로 아래 두 소스코드를 첨부하겠습니다.

set을 사용해서 시간초과를 받은 소스코드 : https://www.acmicpc.net/source...

unordered_set을 사용해서 맞았습니다를 받은 소스코드 : https://www.acmicpc.net/source...

eric00513   4년 전

왜 요구하는 풀이가 단순히 std::set 사용하는 풀이인지 알 수 있을까요?

공식 풀이를 보면 이분 탐색이 의도된 풀이인 것 같습니다.

kdr06006   4년 전

아 그런가요?

알고리즘 분류와 solved.ac 티어를 기준으로 생각했었는데 잘못생각했던거같습니다!

답변 감사합니다!

eric00513   4년 전

현재 알고리즘 분류에 들어가 있는 '해시를 사용한 집합과 맵'은 std::unordered_set입니다.

만약 std::set을 사용해야 하는 문제라면 '트리를 사용한 집합과 맵' 태그가 추가되어 있을 것 같습니다.

알고리즘 분류는 solved.ac 기여에 따라 결정되기 때문에 분류 안에 있어도 그 알고리즘이 반드시 필요하지는 않다는 점 참고하시면 좋을 것 같아요!

kdr06006   4년 전

친절하게 알려주셔서 감사합니다!

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