글 읽기 - 4256 시간 초과

yongwhan 8년 전 0

다음과 같은 코드로 작성하였는데 시간 초과가 걸리네요. 알고스팟에서 풀었던 문제라 그대로 제출했는데.. 뭐가 잘못된 것일까요?

#include<bits/stdc++.h>
using namespace std;

vector<int> Slice(const vector<int> &v, int a, int b) {
  return vector<int>(v.begin()+a,v.begin()+b);
}

bool first;
void printPostOrder(const vector<int> &preorder, const vector<int> &inorder) {
  const int N=preorder.size();
  if(preorder.empty()) return;
  const int root=preorder[0];
  const int L=find(inorder.begin(),inorder.end(),root)-inorder.begin();
  const int R=N-1-L;
  printPostOrder(Slice(preorder,1,L+1),Slice(inorder,0,L));
  printPostOrder(Slice(preorder,L+1,N),Slice(inorder,L+1,N));
  if(!first) cout << " ";
  cout << root;
  first=false;
}

int main() {
  int t; cin>>t;
  while(t--) {
    int n; cin>>n;
    vector<int> preorder(n), inorder(n);
    for (int i=0; i<n; i++) cin>>preorder[i];
    for (int i=0; i<n; i++) cin>>inorder[i];
    first=true;
    printPostOrder(preorder,inorder);
    cout << endl;
  }
  return 0;
}

indioindio 8년 전 0

cin대신 scanf를 사용해보세요

yongwhan 8년 전 0

다음과 같이 고쳤는데도 시간초과네요.. ㅠㅠ;

혹시 다른것 놓친게 있나요?

#include<bits/stdc++.h>
using namespace std;
 
vector<int> Slice(const vector<int> &v, int a, int b) {
  return vector<int>(v.begin()+a,v.begin()+b);
}
 
bool first;
void printPostOrder(const vector<int> &preorder, const vector<int> &inorder) {
  const int N=preorder.size();
  if(preorder.empty()) return;
  const int root=preorder[0];
  const int L=find(inorder.begin(),inorder.end(),root)-inorder.begin();
  const int R=N-1-L;
  printPostOrder(Slice(preorder,1,L+1),Slice(inorder,0,L));
  printPostOrder(Slice(preorder,L+1,N),Slice(inorder,L+1,N));
  if(!first) printf(" ");
  printf("%d", root);
  first=false;
}
 
int main() {
  int t; scanf("%d", &t);
  while(t--) {
    int n; scanf("%d", &n);
    vector<int> preorder(n), inorder(n);
    for (int i=0; i<n; i++) scanf("%d", &preorder[i]);
    for (int i=0; i<n; i++) scanf("%d", &inorder[i]);
    first=true;
    printPostOrder(preorder,inorder);
    printf("\n");
  }
  return 0;
}

WeissBlume 8년 전 0

테스트케이스가 무지막지하게 많아서 Slice부분(O(n))이 시간초과를 발생시키는건 아닐까요?

pl0892029 8년 전 0

Slice 연산으로 매 연산마다 vector를 복사하게 되네요.
이 부분 비용도 적은 비용이 아니니, 복사하지 않고 푸시는걸 추천드려요.

그 외에는 병목 부분이 딱히 보이지 않네요.

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

문제

문제

출처

ICPC

4256 시간 초과

yongwhan 8년 전 0

indioindio 8년 전 0

yongwhan 8년 전 0

WeissBlume 8년 전 0

pl0892029 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말