[python, JavaScript, Java, c, c++]두 정수 사이의 합[프로그래머스]

문제 : 두 정수 사이의 합(프로그래머스)

풀이 1.

Python

def solution(a, b): return (a+b)*(abs(a-b)+1)/2

점화식으로 풀면 input의 크기에 무관하게 $O(1)$ 시간이 나온다. 식을 세울수 있으면 식으로 풀자. 계산도 간단하고 시간도 빠르다. 편의를 위해 작은 수를 a, 큰 수를 b라 하고 두 수를 포함하고 a~b사이 정수의 합을 S라 하면

2S 에서 (a+b)의 수는 (b-a)+1개 이므로 $2S = (a+b)(b-a)$ 이다. 식을 정리하면 S는 위와같이 되는데 절대값을 이용해 a와 b의 값에 무관하게 식을 다음과 같이 정리할 수 있다.

위와 같은 방식에 의하여

$S=\frac {(|a-b|+1)(a+b)} {2}$를 리턴하면 위의 풀이와 같다.

JavaScript

function solution(a, b) {return (a+b)*(Math.abs(a-b)+1)/2;}

Javascript 같은 풀이

Java

class Solution {public long solution(int a, int b) {return (long)(((double)(a+b)/2)*(Math.abs(a-b)+1));}}

class Solution {
    public long solution(int a, int b) {
        return (long)(((double)(a+b)/2)*(Math.abs(a-b)+1));
    }
}

Java 같은풀이
위의 코드는 억지 한 줄 코드
Java에서는 범위를 고려해야한다.

datatype	range
int	-2147483648 ~ 2147483647
long	-9223372036854775808 ~ 9223372036854775807
float	1.4E-45 ~ 3.4028235E38
double	4.9E-324 ~ 1.7976931348623157E308

이기 때문에 int의 범위를 넘기 때문에 long으로 해야한다.
2로 먼저 나누지 않으면 long범위를 벗어나기 때문에 나누고 정수타입으로 두면 값이 변할 수 있기 때문에 double로 바꾼다. 여기서 float를 쓰게되면 범위를 벗어나는 테스트케이스가 존재하고 double에서 계산 한 후에 최종 값을 long으로 변환시켜 리턴한다.

Java로 문제를 풀다보면 범위를 고려해야할 상황이 빈번하다. c와 다르게 long long도 없어서 범위도 더 좁고 BigInteger를 사용해야 할 상황도 자주 있고 그만큼 불편하고 코드도 길어진다.

C++

#include <string>
#include <vector>
#include <stdlib.h>
using namespace std;
long long solution(int a, int b) {
    return ((double)(a+b))/2*(abs(a-b)+1);
}

Java와 유사하다 long long이 있지만 여기서도 2로 먼저 나누지 않으면 범위를 벗어난다.

C

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
long long solution(int a, int b) {
    return ((double)(a+b))/2*(abs(a-b)+1);
}

C++하고 거의 똑같다.

풀이 2.

def solution(a, b): return (a+b)*(max(a,b)-min(a,b)+1)/2

풀이1에서 절대값을 사용하지 않고 최대와 최소를 이용하면

$|a-b|=max(a,b)-min(a,b)$ 이므로 $S=\frac {(max(a,b)-min(a,b)+1)(a+b)} {2}$ 를 리턴하면 같은식이다.

풀이 3.

def solution(a, b): return sum(range(min(a,b),max(a,b)+1))

풀이2에서 점화식을 이용하지않고

$min(a,b)≤ x < max(a,b)+1 = min(a,b)≤ x ≤ max(a,b)+1$ 의 정수 범위를 더하는 식이다. 점화식이 생각나지 않는다면 이러한 방식으로 풀면된다. 수의 범위를 n이라 하면 모든 값을 더하기 때문에 $O(n)$ 시간이 걸리므로 풀이1,2 보다 느리다.