jenhg999   1년 전

위에 코드로 처음에 풀어서 해결했는데요 다른 분들 풀이랑 제 답이랑 시간 차이가 많이 나더라구요

그래서 뭐지 하다가 아 쓸데없이 for문으로 다른 벡터에 입력을 받고 굳이 또 한 번 for문 돌면서 이분탐색을 했구나

그냥 두번째 입력받으면서 바로 이분탐색으로 찾아버리면 더 빠르겠네? 라는 생각으로 밑에 풀이를 제출했습니다.

저는 오히려 두번째가 더 빠르지 않을까 생각했는데 시간초과가 나네요 왜 그런걸까요???

kc0512   1년 전

두 코드의 알고리즘(시간 복잡도)은 동일해서 로직은 문제가 없는 것 같습니다.
시간 초과가 난 진짜 원인은 입출력(I/O) 방식 때문입니다.
두 번째 코드는 for문 안에서 입력(cin)과 출력(cout)을 번갈아 반복하는데, 이 방식이 매우 비효율적이라 느려진 것입니다.

main 함수 초반에 아래 두 줄을 추가하여 입출력 속도를 높이면 AC를 받습니다.

ios_base::sync_with_stdio(false);
cin.tie(NULL);

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