2493번 - 탑
안녕하세요. 문제 풀다가 코드는 짰는데 저는 이중 for문으로 구현하여서 O(N2)이라서 자꾸 시간 초과가 나는 것을 알았습니다. 그렇다면 이 문제는 꼭 O(N)으로만 짜야 통과할 수 있는 문제인건가요?? 그렇다는 것을 문제 풀기 전에 어떻게 알 수 있는 것인가요..
이 문제는 의도적으로 O(N) 또는 O(N log N) 풀이만 통과하게 설계된 문제입니다.
문제를 풀기 전에 “아, 이건 O(N²) 안 되겠구나”를 어떻게 알 수 있을까?N의 크기를 먼저 본다 (가장 중요)N의 범위 허용 시간 복잡도N ≤ 2,000 O(N²) 가능N ≤ 10⁵ O(N log N)N ≤ 5×10⁵ O(N)이 문제는 N = 500,000 O(N²) 시도 자체가 탈락
너무 감사드립니다! 앞으로 N을 먼저 보고 풀이법을 생각해야겠네요.
댓글을 작성하려면 로그인해야 합니다.
zheld1217 9달 전
안녕하세요. 문제 풀다가 코드는 짰는데 저는 이중 for문으로 구현하여서 O(N2)이라서 자꾸 시간 초과가 나는 것을 알았습니다. 그렇다면 이 문제는 꼭 O(N)으로만 짜야 통과할 수 있는 문제인건가요?? 그렇다는 것을 문제 풀기 전에 어떻게 알 수 있는 것인가요..