inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

24. Jolly Jumpers

오버플로우 관련 질문이 있습니다

185

kkt169

작성한 질문수 47

0

안녕하세요 선생님.

수업을 듣고있는 김용준 이라고 합니다.

채점결과로는 5가지 case 전부 success가 나왔지만, 

Q.제가 짠 코드에서 오버플로우를 고려해야 하는지를 여쭤보고 싶습니다. 

-------------------------------------------------------

int isJollyJumper(int*arr, int N);

int main(void)

{

int *arr1, *arr2;

int N;

int i;

scanf("%d",&N);

arr1 = (int*)calloc(N,sizeof(int));

arr2 = (int*)calloc(N-1,sizeof(int));

  // 1. 사용자로 부터 수열을 입력받는다 

       for(i=0; i<N; i++)

{

scanf("%d",&arr1[i]);  

        }

    

//2. 입력받은 수열에서 인접한 값의 차를 구한다 

// 이때, 큰수에서 작은수를 빼서 차를 구하도록 함

    for(i=1; i<N; i++)

    {

     if(arr1[i] > arr1[i-1])

     arr2[i-1] = arr1[i] - arr1[i-1];

    

     else

     arr2[i-1] = arr1[i-1] - arr1[i];

}

// 3. 위에서 구한 차 값을 기반으로, 입력한 수열이

// jolly jumper인지 여부를 구하여, 화면에 결과 출력

if(isJollyJumper(arr2,N) == 1)

printf("YES\n");

else

printf("NO\n");

free(arr1);

free(arr2);

return 0;

    

}

int isJollyJumper(int*arr, int N)

{

int i;

int *isJolly;

isJolly = (int*)calloc(N,sizeof(int));

       

// N개의 수열을 입력받은 경우, 크기가 N인 배열을 생성해

// 0번 element를 사용하지 않고, 1~N-1번 element를

// 사용 하여 jolly jumper 여부를 판별

// 차이가 1에서 N-1 사이에 존재하면, isJolly 배열의 해당 

 // 인덱스를 1증가

       for(i=0; i<N-1; i++)

{

if(arr[i] >= 1 && arr[i] <= N-1)

isJolly[arr[i]]++;

}

for(i=1; i<N; i++)

{

if(isJolly[i] != 1)

return 0;

}

return 1;

}

------------------------------------------------------

저는 위와같이 코드를 작성하였습니다.

이때 저는 큰수에서 작은수를 빼서 차를 구하는 방식으로 작성하였으므로, 이러한  방식으로 차이를 구할 때 오버플로우가 나게 되면 그 결과는 -2147483648 ~ -1 이 됩니다.

그런데 어차피 N의 값의 범위가 3~100 이므로 

오버플로우가 났을 때 적어도 1에서 99사이의 수가 나온다면 jolly jumper가 아닌 수열인데 jolly jumper로 잘못 해석할 수 있겠지만,  큰수에서 작은수를 빼는 방식으로는 오버플로우가 나더라도 1에서 99사이의 수가 나올 수 없으므로,

제가 짠 코드대로 하면은 오버플로우가  나더라도 결과가 정상적으로 구해진다고 생각하였습니다.

Q.제가 맞게 생각한건지 궁금합니다. 

C++ 코테 준비 같이 해요!

답변 1

0

김태원

안녕하세요^^

1부터 N-1로 범위를 지정해주었으니 인덱스 에러는 방지되는 코드입니다.

제가 문제를 명확하게 수정해야 할 것 같네요. 인접한 두 수 차가 정수형 범위에 있다고 수정해 놓겠습니다.

테스트 케이스 질문

0

371

1

병합정렬 시간복잡도 질문

0

461

1

41.연속된 자연수의 합 문제풀이에서 수학적인 원리를 모르고 있습니다.

0

1341

2

질문드립니다.

0

374

1

질문드립니다!

0

428

1

dev 프로그램 질문

0

272

1

문제가 이해가 안되요

0

374

1

4번 나이차이 문제 접근법 질문 드립니다.

0

305

1

source file not compiled

0

1033

3

59번 질문드립니다.

0

370

1

25번 문제 질문

0

346

1

4. 나이차이 문제 질문입니다.

0

367

1

90번 라이언 킹 심바 1번 테스트 케이스

0

468

1

71번 문제 전역 변수 질문 있습니다

0

357

1

75번, 79번 priority_queue관련

1

353

1

75.최대 수입 스케줄

0

394

2

복면산 정답의 수

0

428

1

테스트 케이스에 대해서

0

443

1

수업 내용 질문입니다!

1

229

1

풀어보면 좋은 문제 목록 - 2580 스토쿠 DFS 질문입니다!!

0

818

2

12. 플로이드-와샬(그래프 최단거리) . 27:25초

0

251

1

다른 풀이 방식

0

314

1

크루스칼 vs 프림

0

303

1

숫자 총개수 small 질문있습니다.

0

234

1