정수 오버플로우(Integer overflow)

정수형 오버플로우는 정수 값이 증가하면서 허용된 가장 큰 값보다 커져 실제 저장되는 값이 의도치 않게 아주 작은 수 이거나 음수가 되는 것이다.

특히 반복문 제어, 메모리 할당, 메모리 복사 등을 위한 조건으로 사용자가 제공하는 입력값을 사용하고 그 과정에서 정수형 오버플로우가 발생하는 경우 보안상 문제를 유발할 수 있다.

 

 

프로그래머스 문제를 풀면서 정수 오버플로우를 겪은 문제에 대해서 써보겠다.

 

 

전날 프로그래머스 Lv.1 문제(아래 참고)를 푸는데 배열과 형변환을 활용해서 해결해야 하는 문제였다.

풀이 도중 형변환을 한 후 답을 작성했다.

코드 실행은 모두 성공하고 제출 후 채점하기를 눌렀는데... 테스트 케이스 13, 14를 통과하지 못했다...

1시간 동안 생각해봤는데 해결되지 않아서 식을 바꿔봤는데 바로 통과해 버렸다...!

 

아래는 내가 적은 코드의 성공과 실패 사례를 보며 이유를 찾아보자

// 테스트 통과 코드
class Solution {
    public long[] solution(int x, int n) {
        long[] answer = new long[n];
        for (int i = 0; i < n; i++) {
            answer[i] = (long)x * i + x;
        }
        return answer;
    }
}


// 테스트 실패 코드
class Solution {
    public long[] solution(int x, int n) {
        long[] answer = new long[n];
        for (int i = 0; i < n; i++) {
            answer[i] = (long)x + x * i;
        }
        return answer;
    }
}

테스트 성공(오), 테스트 실패(왼)

 

1부터 12까지의 테스트 케이스는 통과하지만 테스트 13, 14를 통과하지 못하는 것을 보았을 때, 테스트 13과 14는 형변환에 문제가 있는 것을 생각해 볼 수 있다.

 

정수형 타입	할당 메모리 크기	데이터의 표현 범위
int	4바이트	-2^31 ~ (2^31 - 1)
		-2,147,483,648 ~ 2,147,483,647
long	8바이트	-2^63 ~ (2^63 - 1)
		-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

 

다시 생각해 보니 x는 int형으로 지정되었지만 문제 제한 조건은 'x는 -10000000 이상, 10000000 이하인 정수입니다.'로 명시되어 있었다.

 

 

다시 위로 올라가 테스트를 실패한 코드를 보면 answer[i] = (long)x + x * i; 부분에서 x * i의 연산이 먼저 수행되기 때문에 x는 int형으로 지정되어 처리되는 것을 알 수 있다.

 

 

x가 int형으로 표현되었다면 i와 곱셈이 이루어지는 과정에서 값이 int형의 표현 범위를 초과(정수 오버플로우)할 가능성이 있기 때문에 테스트 케이스 13, 14는 매우 큰 x와 i의 값이 주어졌을 것이라고 생각한다.

 

 

따라서 테스트를 성공한 코드의 answer[i] = (long)x * i + x;에서 x * i를 먼저 수행하기 때문에 x는 long형으로 형변환되어 연산된다.

 

 

주의!! answer[i] = (long)x * i + x;에서 앞에 있는 x가 long형으로 형변환되어 연산되었을지라도 x의 자료형을 변경하는 것이 아니기 때문에 뒤에 있는 x는 long형이 아닌 int형으로 유지된다!

 

 

 

 

 

참조

x만큼 간격이 있는 n개의 숫자 - 프로그래머스

[Java] 정수 오버플로우(Integer overflow) - M1naWorld님