• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

이건 무슨차이인가요?

20.01.25 02:33 작성 조회수 138

0

배열크기를 300001로 하는거랑 30001로 하는거랑

success 갯수가 다른데 무슨차이인가요?

300001로하면 4번까진 성공나오고 5번은 타임리밋인데

30001로 배열크기로하면 2번부터 타임리밋이 나옵니다..

#pragma warning(disable:4996)
#include <stdio.h>
#include <string.h>
#include <math.h>
#include<time.h>
#include<iostream>
#define endl '\n';

using namespace std;


int a[300001];
int b[300001];
int r[300001];

int main() {
   int n1,n2,k=0,j=0,max=0;
   
   scanf("%d",&n1);
   for(int i=1;i<=n1;i++)
      scanf("%d",&a[i]);
      
   scanf("%d",&n2);
   for(int i=1;i<=n2;i++)
      scanf("%d",&b[i]);
      
   for(int i=1;i<=n1;i++) {
      
      k=a[i];
      
      if(k>max)
      max=k;
      
      r[k]++;
   }
   
   for(int i=1;i<=n2;i++) {
      j=b[i];
      if(j>max)
      max=j;
      r[j]++;
   }
   
   for(int i=1;i<=max;i++) {   
      if(r[i]==2)
      printf("%d ",i);
   }
   

}

답변 1

답변을 작성해보세요.

0

저번 LRU 질문에서 재질문에 대한 댓글을 3일 후쯤 수정해서 올렸는데 한 번 보시기 바랍니다.

내가 만든 프로그램의 성능을 좌우하는 것은 시간복잡도도 있지만 공간복잡도도 있습니다. 공간복잡도란 메모리를 절약해야 한다는 것입니다. 실제를 메모리 사용량이 늘어나면 프로그램은 속도가 확연히 느려집니다.

입력되는 데이터의 값을 배열의 인덱스로 사용할 때는 조심해야 합니다. 이 문제의 경우 입력되는 값이 정수범위니까 

21억크기의 값까지 입력되니, a, b, r 배열의 크기를 int a[2147483648] 식으로 잡아야 합니다 엄청난 메모리 낭비가 일어납니다. 제가 만든 입력데이터는 100만까지만 했기 때문에  a, b, r 세개의 배열을 int a[1000001]; 식으로 잡으면 5번까지 통과는 될겁니다. 하지만  이 문제는 제가 영상에서 설명한 방식으로 해결하기 바랍니다.