7-M 시간초과 질문있습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

7-M

작성

135

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. http://boj.kr/ef8ad015457e4bbba05ac351eb5ae0d8안녕하세요 강사님 7-M 문제에서 살아있는 나무는 정렬을 위해 deque를 사용했고죽은 나무는 queue를 사용해서 양분으로 바꿔줬는데 계속 시간초과에서 막혀 질문글 남깁니다...이 문제는 deque로 풀면 안되는 문제일까요? 아니면 제 코드에서 시간을 단축 시킬만한 곳이 있을까요?

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 인창님 ㅎㅎ

솔직히 인창님의 로직이나 코드 자체가 괜찮다고 생각합니다.

저도 사실 이런 식으로 몇번 시도해봤는데... 시간초과가 뜨네요.

흠... 의심가는 부분은 deque의 sort부분인데요.

벤치마크를 돌려본 결과 vector에 비해 느리긴 하지만.. 뭐 이건 느리다고도 할 수 없는 수준입니다.

벤치마크 코드.

#include <bits/stdc++.h>
using namespace std;  
void A(){
  vector<int> v; 
  for(int i = 500; i >= 1; i--){
    v.push_back(i);
  }
  sort(v.begin(), v.end()); 
}
void B(){
  deque<int> v;  
  for(int i = 500; i >= 1; i--){
    v.push_back(i); 
  } 
  sort(v.begin(), v.end()); 
}
void test_latency(size_t iteration) {  

  PROFILE_START("A"); 
  A();
  PROFILE_STOP("A");
  PROFILE_START("B");
  B();
  PROFILE_STOP("B");
}

int main() {
  const size_t warmups = 1000;
  const size_t tests = 100;
 
  PROFILE_RUN_ALL(warmups, tests, 
    test_latency(__loop);
  );

  return 0;
}

사이트 : https://perfbench.com/

부족한 답변을 드려 죄송하다는 말씀을 드립니다. ㅜ

P.S

제가 이거는 좀 더 보다가 맞는 답변이 생각나면 다시 달겠습니다.

감사합니다.

인창

질문자

좋은 강의 만들어주셔서 감사합니다ㅠㅠ

인프런 커뮤니티 질문&답변

7-M 시간초과 질문있습니다.