프로그래머스 != 알고리즘

# 개요

---

프로그래머스를 처음 알게 된 것은 2017년 카카오 페스티벌로 처음 알게 됐습니다.

당시 신생 플랫폼인데다가, ICPC 스타일이 아니라 정해진 함수 포맷을 구현하는 문제는 처음 봤기 때문에 거부감이 상당히 강했습니다.

비단 저 뿐만 아니라, 같이 공부하던 분들도 모두 처음 보는 플랫폼에 대한 막연한 거부감이 생겼습니다.

 

하지만, 복학 이후에 사실상의 메이저 플랫폼이 되어있었고, 상당히 많은 기업에서 자사 코딩테스트 플랫폼으로 채용하게 되었습니다.

때문에 저도 프로그래머스에서 진행하는 여러 대회/채용에 지원하게 되었고, 프로그래머스에서 진행한 채용 프로세스에 합격하여 결국 취업에 성공하게 되었습니다.

이제는 본계정이 된 부계정의 대회/채용 참여 내역

 

# 문제

---

C++로 ps를 쭉 해왔는데, Java에 더 익숙해 지기 위해 최대한 Java8의 Stream을 활용하여 문제를 풀어보려고 노력하고 있습니다.

그런데, 문제는 프로그래머스에서 연습문제로 주어지는 문제 중에 Stream으로 풀게 되면 반드시 TLE가 뜨는 문제가 존재한다는 것입니다.

 

프로그래머스

프로그래머스 lv.3 최고의 집합 문제입니다.

 

## Stream 풀이

---

import java.util.stream.Stream;

class Solution {
    public int[] solution(int n, int s) {
        if (n > s) {
            return new int[]{-1};
        }
        return Stream.iterate(0, i -> i < n, i -> i + 1)
                .mapToInt(i -> s / n + (i >= n - s % n ? 1 : 0))
                .toArray();
    }
}

더 이상 최적화할 건덕지가 없는 Stream 풀이임에도 불구하고, TLE가 뜨게 됩니다.

 

## For loop 풀이

---

class Solution {
    public int[] solution(int n, int s) {
        if (n > s) {
            return new int[]{-1};
        }
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            answer[i] = s / n + (i >= n - s % n ? 1 : 0);
        }
        return answer;
    }
}

위 Stream 풀이와 완전히 동일한 동작을 하는 코드임에도 불구하고, for loop은 100점이 나오게 됩니다.

 

# 왜?

 

Java Stream API는 왜 for-loop보다 느릴까?

 

정말 설명이 잘 되어 있습니다. 제가 궁금한 점만 인용하여 요약해보자면,

primitive 배열의 단순 참조 또는 단순 계산에서는 for-loop이 더 빠를 가능성이 높다.
순회 비용이 커지거나(ArrayList<Integer> 순회) 계산 비용이 커지면(각 원소에 적용하는 연산이 오래 걸리는 경우) Stream과 for-loop의 시간차이가 적어진다.
Stream은 일반적으로 더 느리나, 가독성과 유지보수성을 위해 필요한 존재다.

 

# 결론

---

프로래머스에서 Java Stream이 느려 TLE가 뜨게 된다면, 쓰지 않으면 그만입니다.

하지만 더 큰 문제는, 각 문제의 시간 제한을 알려주지 않는 것입니다.

ICPC를 지향하는 다른 OJ에서는 모두 시간제한 또는 메모리 제한을 언급하고 있습니다.

그런데, 프로그래머스는 문제에 따라 언급하고 있는 경우도 있고, 아닌 경우도 있습니다(대부분 언급하지 않습니다).

그렇기 때문에 어떤 문제가 TLE가 뜨게 되면 Stream문제인지 비효율적인 알고리즘의 문제인지 전혀 파악할 수가 없습니다.

 

시간 제한을 알려주지 않을 뿐 아니라, 언어별 시간 차이에 따른 차등적인 시간 제한을 적용하지 않는다는 것 또한 문제가 됩니다.

DP문제 중 재귀로 해결할 경우 TLE로 통과되지 않는 경우가 다수 있습다. 

동일한 로직의 C++ 코드는 당연하게도 재귀로 통과하게 됩니다.

 

언어별 특징을 고려하지 않고, 일단 구현해둔 뒤, 발생하는 문제는 사용자가 알아서 해결하도록 방치하는게 맞는지 의문입니다.