stoi 함수가 느려서 그렇습니다. 파싱을 다른 방식으로 해주세요.
5430번 - AC
파싱을 이렇게 하니까 됩니다. 질문에 답해주셔서 감사합니다!
이와 별개로 다른 궁금한 게 있는데
원래 방식의 stoi함수는 문자열이 [12,123,123,123,123,123]이고 인덱스가 1이면
12를 읽고 tmp에 2를 주고 끝난다고 알고 있습니다.
그리고 바꾼 방식에서 문자열이 같다고 할 때 "12"를 stoi()함수 돌리고 끝나는 거면
이전 방식과 지금 방식은 문자열의 길이만 다르고 처리 과정은 똑같은데 왜 이렇게 시간 차이가 나는지 궁금합니다.
원래 방식에서 제가 생각한 대로 처리하지 않는건가요?
stoi 자체에는 문제가 없으나, stoi의 첫 번째 인자가 const string& 이기 때문에 &input[i]를 전달할 때 char *가 string으로 변환되는 과정에서 문제가 발생합니다.
char *을 string으로 변환할 때 그 string 객체는 널 문자가 나올 때까지의 모든 문자를 복사하게 되는데, 그러면 [12,123,123,123,123,123]이라는 문자열의 1번째 문자부터 널 문자가 나올 때까지 무려 12,123,123,123,123,123] 라는 문자들이 전부 새로운 string 객체에 복사되어야 합니다.
각 stoi가 실제로 읽는 문자들은 몇 개씩밖에 되지 않겠지만, 이 함수의 호출을 위해 복사되는 문자열은 매번 전체 길이에 비례하기 때문에 n개의 수를 읽어들이기 위해 O(n^2)개의 문자들이 복사되는 결과를 초래합니다.
사실 간단한 다른 해결책으로는 atoi 함수를 대신 사용하는 것이 있습니다. atoi는 원래부터 const char*를 인자로 받기 때문에 string으로 변환하는 과정이 없어 이러한 문제가 발생하지 않습니다.
궁금한 걸 정확히 집어서 설명해주시네요!
게다가 문제의 대안까지 언급해주셔서 감사합니다!
댓글을 작성하려면 로그인해야 합니다.
dlalstjq612 1년 전
16%에서 시간초과가 납니다.
입력에서 문자를 숫자로 뽑아서 받는 작업은 stoi()로 하고
R, D는 포인터를 바꾸거나 포인터에 더해서 상수 시간동안 작업하게 만들었습니다.
출력도 그냥 일반적인 출력이라고 생각하는데 어디서 문제인지 잘 모르겠습니다.