백준 1212번 왜 시간초과가 나는걸까요..?? ㅠㅠ

Question

1212번: 8진수 2진수 (acmicpc.net)이 문제입니다.8진수 길이 때문에 for문 내 조건문에 .size()나 length()와 같은 함수를 넣지말라는 의도의 문제인데요, 그걸 인지하고 for문내 조건문에 함수사용을 제외하였습니다.근데 이상하게 for문을 인덱스 1부터 탐색하는건 정답 처리가 되는데 for문을 인덱스 마지막부터 1까지 탐색하는건 시간초과가 뜨네요...즉 이건 정답으로 처리가 되었지만 for (int i = 0; i < strsize; i++) {이건 시간초과가 되네요... for (int i = strsize-1; i >= 0; i--) {무슨이유일까요? 정말 궁금하네요 ㅠ 진짜 for문 탐색하는 방향이 다른거 말곤 다른점이 없는데...시간초과 처리가 된 코드입니다.#include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string str; cin >> str; if (str == "0") { cout << 0; return 0; } string answer = ""; int strsize = str.size(); for (int i = strsize - 1; i >= 0; i--) { int num = str[i] - '0'; if (i == 0) { if (num == 0) { answer = "0" + answer; } else if (num == 1) { answer = "1" + answer; } else if (num == 2) { answer = "10" + answer; } else if (num == 3) { answer = "11" + answer; } else if (num == 4) { answer = "100" + answer; } else if (num == 5) { answer = "101" + answer; } else if (num == 6) { answer = "110" + answer; } else if (num == 7) { answer = "111" + answer; } } else { if (num == 0) { answer = "000" + answer; } else if (num == 1) { answer = "001" + answer; } else if (num == 2) { answer = "010" + answer; } else if (num == 3) { answer = "011" + answer; } else if (num == 4) { answer = "100" + answer; } else if (num == 5) { answer = "101" + answer; } else if (num == 6) { answer = "110" + answer; } else if (num == 7) { answer = "111" + answer; } } } cout << answer; }정답 처리가 된 코드입니다.#include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string str; cin >> str; if (str == "0") { cout << 0; return 0; } string answer = ""; int strsize = str.size(); for (int i = 0; i < strsize; i++) { int num = str[i] - '0'; if (i == 0) { if (num == 0) { answer += "0"; } else if (num == 1) { answer += "1"; } else if (num == 2) { answer += "10"; } else if (num == 3) { answer += "11"; } else if (num == 4) { answer += "100"; } else if (num == 5) { answer += "101"; } else if (num == 6) { answer += "110"; } else if (num == 7) { answer += "111"; } } else { if (num == 0) { answer += "000"; } else if (num == 1) { answer += "001"; } else if (num == 2) { answer += "010"; } else if (num == 3) { answer += "011"; } else if (num == 4) { answer += "100"; } else if (num == 5) { answer += "101"; } else if (num == 6) { answer += "110"; } else if (num == 7) { answer += "111"; } } } cout << answer; }

운체조교 · Answer

지금 하신 std::string의 덧셈의 구현을 잘 생각해보면 O(N)입니다. 특히 한 digit을 추가 할 때마다 O(N)번 삽입이 이루어지게 작성이 되어있습니다. 만약 숫자가 커지면 digit의 수를 M이라고 할 때 O(N*M) 의 시간이 필요하겠죠.

fromis_9 · Answer

if elseif else 대신에switch case 써 보시는건 어떠실까요?

yeori · Answer

+= 는 append 메소드 호출해서 속도가 빠르고, a +b 는 문자열을 복사해서 연결해서 O(n^2) 걸린다고 구글링하면 문서가 많이 나오네요.

비정규분포 · Answer

문제집 링크 안뜹니다. 로그인 해야하나요?Callgrind 사용해서 어디서 CPU시간 많이 잡아먹는지 분석하실 수 있어요, 정 안된다면

비정규분포 · Answer

참고로 저런 상황에서는 stringstream이나 cout을 직접 사용합니다. C++은 다른 상위 언어처럼 사용하면 안되요.그리고 문제에서는 쓰지 말라하겠지만, std::hex나 std::bin 쓰면 다른 처리 안해도 된다는건 함정.

백준 1212번 왜 시간초과가 나는걸까요..?? ㅠㅠ

5개의 답변

기타 목록