알고리즘 문제는 Stream을 사용해서 풀면 안되는 걸까?

알고리즘에 대한 감을 잃지 않기 위해 문제를 꾸준히 풀어가는 중이다.

기존에는 레거시 자바문법을 이용해서 풀어냈다면, 요즘은 모던 자바의 기능들을 활용해서 문제를 풀어나가고 있다.

그 중 가장 많이 사용하는 기법은 Stream을 이용하는 것인데, 이게 참 문제가 많은 것 같다...

 

백준의 2580 스도쿠 문제를 보자

www.acmicpc.net/problem/2580

2580번: 스도쿠

 

스도쿠 해답을 찾는 간단한 문제이다.

이전에 풀어본 경험이 있는데 소스가 많이 더러워서 깔끔하게 풀어보고자 다시 풀어봤다.

그런데 이상하게도 계속해서 시간초과가 발생한다.

분명 맞는 로직인것 같은데 왜 시간초과지...??? 라는 생각이 계속 맴돌았다. 당시 작성한 코드는 아래와 같다.

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class Main {
    static class Pair {
        int r, c;

        public Pair(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int[][] map = new int[9][9];

        List<Pair> list = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 0) {
                    list.add(new Pair(i, j));
                }
            }
        }

        dfs(map, list, 0);
    }


    public static int dfs(int[][] map, List<Pair> list, int depth) {
        if (depth == list.size()) {
            for (int i = 0; i < map.length; i++) {
                for (int j = 0; j < map[0].length; j++) {
                    System.out.print(map[i][j] + " ");
                }
                System.out.println();
            }
            return -1;
        }

        Pair now = list.get(depth);
        for (int i = 1; i <= 9; i++) {
            if (isRightNumber(now, map, i)) {
                map[now.r][now.c] = i;
                if(dfs(map, list, depth + 1) < 0) {
                    return -1;
                }
                map[now.r][now.c] = 0;
            }
        }

        return 0;
    }

    public static boolean isRightNumber(Pair pair, int[][] map, int number) {
        return Arrays.stream(map[pair.r]).noneMatch(i -> i == number)
                && IntStream.range(0, 9).map(i -> map[i][pair.c]).noneMatch(i -> i == number)
                && IntStream.range(pair.r / 3 * 3, pair.r / 3 * 3 + 3)
                .noneMatch(i -> IntStream.range(pair.c / 3 * 3, pair.c / 3 * 3 + 3)
                        .anyMatch(j -> map[i][j] == number));
    }
}

 

이리보고 저리봐도 잘못된 로직은 없는 것 같다. 그러다 문득, stream이 문제일거라는 생각이 들었고, stream의 코드를 레거시하게 변경해 봤다.

public static boolean isRightNumber(Pair pair, int[][] map, int number) {
    return col(pair, map, number) && row(pair, map, number) && square(pair, map, number);
}

public static boolean col(Pair pair, int[][] map, int number) {
    for(int i=0; i<9; i++) {
        if(map[pair.r][i] == number) return false;
    }
    return true;
}

public static boolean row(Pair pair, int[][] map, int number) {
    for(int i=0; i<9; i++) {
        if(map[i][pair.c] == number) return false;
    }
    return true;
}

public static boolean square(Pair pair, int[][] map, int number) {
    for(int i=pair.r/3*3; i<pair.r/3*3+3; i++) {
        for(int j=pair.c/3*3; j<pair.c/3*3+3; j++) {
            if(map[i][j] == number) {
                return false;
            }
        }
    }
    return true;
}

 

 

코드를 레거시 하게 바꿨더니 통과한다.... stream을 생성하는데 들어가는 오버헤드가 문제였던 것이다.

그러면 이때 드는 의문.. 알고리즘에서 stream의 사용은 금물인 것일까..?

최근 코드들이 모던하게 바뀌어 가는 추세이고, stream도 나온지 오래 됐는데, 알고리즘은 레거시 코드로만 통과된다면.. 기업들이 알고리즘으로 지원자들의 코딩 실력을 판단한다는 관점에서 이러한 현상은 참으로 아이러니 하다 😐