hyemin1826   1년 전

안녕하세요 ㅠㅠ 도저히...어디서 시간 초과가 나는지 모르겠습니다.


getline 대신 cin 사용해서 시간 줄이고, reverse는 실제로 안 뒤집어서 O(1) time으로 처리했고, 심지어 c++이라 string 이어 붙이는 것도 O(1) 시간에 끝날텐데...

대체 왜...???

zenith82114   1년 전

cin/cout을 그냥 쓰면 scanf/printf보다 느리고 "빠른 입출력"이라고 불리는 아래의 처리를 해주어야 빨라집니다.

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    /* 실제 프로그램 */
}

또한, 빠른 입출력을 사용한다면 두 가지 방식을 혼용하면 안 됩니다. 즉, 모든 입출력을 scanf/printf으로 통일하든지, 아니면 빠른 입출력을 적용하면서 cin/cout으로 통일하면 됩니다.

자세한 원리는 여기서 보실 수 있습니다.

hyemin1826   1년 전

좋은 자료 알려주셔서 감사합니다! 실례가 되지 않는다면, tie에 관한 개념을 좀 더 여쭤봐도 괜찮을까요?

해당 링크에서 cin과 cout가 tie 되어 있으면 cin 실행 전에 출력 버퍼를 flush한다고 되어 있는데, 이 부분이 헷갈립니다.

cin과 cout을 tie시킨 후, cin 입력 시 입력버퍼, 출력버퍼의 동작이 어떻게 되는 걸까요? 

제가 이해한 바로는 [ 키보드에서 입력 -> 입력 스트림 -> 입력 버퍼에 입력 -> variable에 값 지정  ]인데, 이렇게 되면 출력 버퍼를 flush를 해도 빈 버퍼를 flush 하니 무거운 동작이 아니게 되고..  헤갈리네요 ㅠㅠ

hyemin1826   1년 전

마음이 아프군요. 아래처럼 입출력을 바꿔도 계속 시간 초과가 뜨네요 ㅠㅠ

zenith82114   1년 전

substr의 시간복잡도가 O(1)이 아니고 만들어질 substring의 길이에 비례하기 때문에, while문 안에 있는 tmp_s = tmp_s.substr(pos+1); 라인이 소모하는 총 시간이 O(N^2)이 됩니다. 이 부분만 개선하시면 통과가 될 것 같고, 입출력 방식은 바꿀 필요가 없었을 수도 있습니다.

hyemin1826   1년 전

substr이 문제였군요!! 감사합니다. 덕분에 해결했어요 ㅠㅠ

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