[프로그래머스] 없는 숫자 더하기(Java)

지금까지 알고리즘 풀이를 python으로만 진행했는데, Java도 조금씩 연습하기로 했다

물론 업무의 대부분에서 Java를 사용하고 있지만, 다양한 툴 사용이 가능한 업무환경과 코딩테스트 환경은 다르기에 별도의 연습이 반드시 필요하다고 생각했다.

차근차근 환경에 익숙해지기 위해서 Java로 프로그래머스 레벨1 문제부터 다시 풀어보기로 했다.

문제 링크

프로그래머스

문제의 출제의도

이 문제는 푸는 사람이 어떻게 접근하느냐에 따라 출제의도를 다르게 느낄 수 있는 문제였다

• (배열을 이용한 풀이로 접근할 경우) 배열을 순회하며 원소와 인덱스를 확인하고 더할 수 있는가
• (사칙연산 문제로 접근할 경우) 숫자의 합을 효율적으로 구할 수 있는가

처음에는 배열을 이용해서 풀었지만, 조금 더 생각해 보니 사칙연산을 이용하면 훨씬 간단하게 문제를 해결할 수 있었다

역시 코딩하고나서 생각하는 것이 아니라 생각부터 하고 코딩하는 것이 중요하다.

아래에서 두가지 풀이를 비교하며 어떤 식으로 접근하는지 확인해보자.

 

배열을 이용한 풀이

특정 숫자가 출현한 적이 있는지, 출현했다면 몇 번이나 출현했는지 확인하는 가장 쉬운 방법은 해당 숫자의 출현빈도를 저장하는 것이다.

위 문제에서는 0부터 9까지의 출현 빈도만 파악하면 되므로, 길이 10의 배열에 각 숫자의 출현빈도를 저장하면 된다.

 

풀이 과정을 정리하면 아래와 같을 것이다.

1. 0~9까지의 숫자별 출현빈도를 저장하는 길이 10의 numberCnt 배열을 만든다
2. numberCnt 배열을 순회하면서, 출현빈도가 0인 숫자들을 더한다

코드로 작성하면 아래와 같다

class Solution {
    public int solution(int[] numbers) {
        int answer = 0;
        
        int[] numberCnt = new int[10];
        for(int number: numbers){
            numberCnt[number] += 1;
        }

        for(int i = 0; i<numberCnt.length; ++i) {
            if (numberCnt[i] == 0) answer += i;
        }
        return answer;
    }
}

python에서는 enumerate로 배열의 index를 추출하기 쉽지만, Java의 배열에서는 그렇게 할 수 없다는 점이 아쉬웠다.

어쩔 수 없이 index를 직접 명시해서 for-loop를 수행해 주었다.

 

실행 시간은 아래와 같다.

테스트 1 〉	통과 (0.01ms, 76.2MB)
테스트 2 〉	통과 (0.03ms, 75MB)
테스트 3 〉	통과 (0.02ms, 74.8MB)
테스트 4 〉	통과 (0.02ms, 77.6MB)
테스트 5 〉	통과 (0.02ms, 75.9MB)
테스트 6 〉	통과 (0.02ms, 70.3MB)
테스트 7 〉	통과 (0.03ms, 71.8MB)
테스트 8 〉	통과 (0.03ms, 76.7MB)
테스트 9 〉	통과 (0.01ms, 78.3MB)

 

사칙연산으로 접근하는 풀이

이 풀이는 0부터 9까지의 합은 45로 고정되어 있다는 점을 이용한다. 즉 특정 숫자가 출현하지 않으면, 총합은 45에서 그 숫자만큼 줄어들게 된다!

 

이를 이용하면 아래와 같은 흐름으로 풀 수 있다

1. 배열을 순회하면서 모든 수를 더해 변수 sum에 저장한다
2. 45 - sum이 바로 우리가 원하는 답이 된다.

다만 이때 배열의 합을 구하는 방법에는 여러가지가 있을 수 있는데

①배열의 합을 구해주는 라이브러리를 사용하는 방법과

②직접 배열을 순회하면서 더하는 방법이 있다

 

우선 배열의 합을 구해주는 라이브러리를 사용하는 코드는 아래와 같다

import java.util.Arrays;

class Solution {
    public int solution(int[] numbers) {
        return 45 - Arrays.stream(numbers).sum();
    }
}

배열의 합을 쉽게 구하기 위해 Arrays.stream()으로 Stream으로 만들어 준 후 sum()을 이용해 합쳤다

for문이 없기에 굉장히 간결하고 좋긴 하지만, 이 코드의 문제점은 실행시간에 있었다

 

프로그래머스의 실행 시간은 아래와 같다

테스트 1 〉	통과 (0.63ms, 72.6MB)
테스트 2 〉	통과 (7.45ms, 71.7MB)
테스트 3 〉	통과 (0.79ms, 73.3MB)
테스트 4 〉	통과 (1.52ms, 71.8MB)
테스트 5 〉	통과 (0.77ms, 73MB)
테스트 6 〉	통과 (0.74ms, 72.1MB)
테스트 7 〉	통과 (0.72ms, 75.1MB)
테스트 8 〉	통과 (0.74ms, 78.2MB)
테스트 9 〉	통과 (1.08ms, 73.7MB)

전체적으로 실행시간이 증가했고 특히 2번 케이스는 7ms로 기존 풀이의 0.03ms에 비하면 200배가 넘는 실행시간을 보여줬다. 왜일까?

배열을 순회하며 연산을 처리하는 경우, 필요한 비용은 각각의 원소에 대한 계산비용 + 배열의 다음 원소로 넘어가는 순회비용으로 계산될 수 있다.

위의 문제에서 stream이 for-loop에 비해 압도적으로 느린 것은 sum 연산의 계산 비용이 낮기 때문에, for-loop에 비해 순회 비용이 큰 stream이 불리하기 때문이다

 🎯순회 비용과 계산 비용, Stream과 for-loop의 속도차이에 대한 설명은 Sigrid Jin님의 글을 참조하면 좋다
 Java Stream API는 왜 for-loop보다 느릴까? | by Sigrid Jin | Medium

 

그렇다면 직접 배열을 순회하면서 더하는 경우는 어떨까? 코드와 실행시간은 아래와 같다.

class Solution {
    public int solution(int[] numbers) {
        int sum = 45;
        for (int i : numbers) {
            sum -= i;
        }
        return sum;
    }
}

테스트 1 〉	통과 (0.02ms, 79.8MB)
테스트 2 〉	통과 (0.02ms, 75.8MB)
테스트 3 〉	통과 (0.02ms, 72.9MB)
테스트 4 〉	통과 (0.02ms, 74.3MB)
테스트 5 〉	통과 (0.02ms, 69.4MB)
테스트 6 〉	통과 (0.01ms, 72.5MB)
테스트 7 〉	통과 (0.03ms, 73.7MB)
테스트 8 〉	통과 (0.02ms, 78.3MB)
테스트 9 〉	통과 (0.03ms, 71.3MB)

훨씬 낮은 실행시간을 보여준다. 간단한 문제에서는 큰 차이가 나지 않지만 효율성 테스트까지 통과해야 하는 고난도 문제에서는 통과여부를 결정할 수 있을 만큼 큰 차이다

 

문제에서 배울 점

정말 쉬운 level 1 문제지만 배워갈 기본기와 생각해볼 점이 많은 문제였다. 고난이도 문제들로 갈 수록 이런 기본기들의 조합을 얼마나 능숙하게 다루는가에 따라 풀이가 결정되므로, 반드시 명심하고 넘어가야 할 것이다

• 각 언어별 built-in에 따라 풀이가 달라질 수 있음을 이해할 것 (항상 python처럼 쉽게 풀수 없을지도 모른다)
• 자료구조나 라이브러리를 사용할 때는, 내부 구현으로 인한 성능 차이를 확인하고 사용할 것