[알고리즘 - 구현] 기둥과 보 설치

☀️ 시작

이번 문제는 2020 신입 개발자 블라인드 채용 1차 코딩 테스트의 5번 문항 '기둥과 보 설치' 문제이다. 확실히 구현문제는 어렵지만 머릿속으로 풀이 과정을 생각하고 이를 코드로 구현해내는 과정이 재밌고 뿌듯하다.

정답률이 1.9%라는데 나도 그랬지만 카카오 코테는 블라인드라 일단 지원하고 보는 사람이 너무 많아서 정답률에 크게 의미를 두지 않아야 할 것 같다는 생각이 든다. 그래도 항상 손도 못대던 카카오 코테인데 이번엔 직접 풀 수 있어서 기분이 좋았다.

📖 문제

문제 링크

먼저 문제의 구현 요구사항을 간단히 요약하면, 죠르디가 '기둥'과 '보'를 사용해 구조물을 만들려고 하는데 입력으로 주어지는 '설치'와 '삭제' 요청을 시뮬레이션하면서 가능한 요청만 반영하여 최종 완성된 구조물을 출력하면 되는 문제이다.

'기둥'과 '보'의 설치 조건은 각각 아래와 같다. (기둥과 보는 모두 길이가 1인 선분이며 보는 주어진 좌표에서 '우측'으로, 기둥은 주어진 좌표에서 '위'로 설치된다)

기둥 설치 조건

1. 바닥(y좌표가 0)위에 설치 가능
2. 보의 한쪽 끝에 위치하면 설치 가능

보 설치 조건

1. 양쪽 끝 중 하나가 기둥 위에 있으면 설치 가능
2. 양쪽 끝 부분이 각각 다른 보와 연결되면 설치 가능

또한, 입력은 2차원 배열로 주어지는데 각 행 [x, y, a, b]는 각각 [가로좌표, 세로좌표, 설치할 구조물 종류, 삭제 or 설치]를 의미하며 기둥(0), 보(1), 삭졔(0), 설치(1)로 표현된다.

🧑🏻‍💻 풀이

먼저 크게 경우의 수를 4가지로 나누었다.

1. 기둥 설치
2. 보 설치
3. 기둥 삭제
4. 보 삭제

설치 조건 검사

이 중 기둥이나 보를 설치하는 경우에는 문제에서 제시된 조건을 토대로 설치가 가능한지 판단한다. 구체적인 방법으로는 먼저 x, y 좌표를 갖는 Position 클래스를 만들고 기둥과 보의 리스트를 각각 만들어둔다.

Position 클래스 (List에 넣을 것이므로 equals() 구현)

static class Position{
    int x, y;
    public Position(int x, int y) {
        this.x = x;
        this.y = y;
    }

    // 주어진 dx, dy를 더해 새로운 Position 반환
    // 조건 검사 시 주어진 좌표에서 원하는 좌표를 쉽게 만들어내기 위해 사용
    public Position adjustedNewPosition(int dx, int dy) {
        return new Position(x + dx, y + dy);
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        if (!(o instanceof Position)) {
            return false;
        }
        Position p = (Position) o;
        return this.x == p.x && this.y == p.y;
    }
}

기둥과 보의 리스트

List<Position> columns = new ArrayList<>(); // 기둥(0)
List<Position> rows = new ArrayList<>(); // 보(1)

그리고 입력이 들어올 때 마다 순회하면서 새로운 좌표가 기존 기둥, 보들 사이에 설치 가능한지 (문제에서 주어진 조건을 토대로) 검사한다.

기둥 설치 검사 메서드

public boolean canBuildColumn(List<Position> columns, List<Position> rows, Position newPosition) {
    // 주어진 좌표가 바닥인가?
    if (newPosition.y == 0) {
        return true;
    }

    // 주어진 좌표 "아래"에 기둥이 있는가?
    if (columns.contains(newPosition.adjustedNewPosition(0, -1))) {
        return true;
    }

    // 해당 좌표 || "좌측" 좌표에 보가 있는가?
    if (rows.contains(newPosition) || rows.contains(newPosition.adjustedNewPosition(-1, 0))) {
        return true;
    }

    return false;
}

보 설치 검사 메서드

public boolean canBuildRow(List<Position> columns, List<Position> rows, Position newPosition) {
    // 주어진 좌표 아래"나" 주어진 좌표 우측 아래에 기둥이 있는가?
    if (columns.contains(newPosition.adjustedNewPosition(0, -1)) ||
       columns.contains(newPosition.adjustedNewPosition(1, -1))) {
        return true;
    }

    // 현재 좌표의 좌측 좌표"와" 우측 좌표에 보가 있는가?
    if (rows.contains(newPosition.adjustedNewPosition(-1, 0)) &&
       rows.contains(newPosition.adjustedNewPosition(1, 0))) {
        return true;
    }

    return false;
}

이를 사용해 설치가 가능한지 판단하게 된다.

위 메서드를 실제로 사용하는 코드

// 시뮬레이션 시작
for (int[] build : build_frame){
    Position newPosition = new Position(build[0], build[1]); // 가로, 세로
    if (build[3] == 1) { // 설치
        if (build[2] == 0) {
            // 기둥 설치 조건 검사
            if(canBuildColumn(columns, rows, newPosition)) {
                columns.add(newPosition);
            }

        } else {
            // 보 설치 조건 검사
            if (canBuildRow(columns, rows, newPosition)) {
                rows.add(newPosition);
            }
        }
    }
    // 이후에는 삭제하는 경우에 대한 처리 진행

삭제 조건 검사

이제 반대로 삭제하는 경우를 생각해보자. 처음에는 설치 시와 마찬가지로 직접 삭제가 가능한 조건을 따져보고 있었다. 예를 들면 기둥을 삭제할 수 있는 조건은 주어진 좌표 위 좌표에 기둥이 없어야 하고, 주어진 좌표의 위좌표와 위+좌측 좌표에 보가 없어야 하고… 이를 따지다보니 너무 복잡하고 실수할 확률이 높아보여서 방법을 바꾸었다.

새로운 방법은 삭제 요청이 들어올 때 기존 기둥/보 리스트에서 임시로 새로운 좌표를 삭제한 뒤 나머지 기둥/보가 그대로 존재할 수 있는지를 확인해보는 방법이다. 그리고 기존 기둥/보 중 하나라도 그 자리에 유지되지 못한다면 다시 해당 좌표를 원복시킨다. 즉, 아래와 같이 코드로 작성할 수 있다.

// 상단은 설치 요청에 대한 처리 코드

else { // 삭제
    boolean canRemove = true;

    if (build[2] == 0) {
        // 임시로 기둥 삭제
        columns.remove(newPosition);

        // 기존 기둥, 보가 유지 가능한지 검사
        for(Position column: columns) {
            canRemove = canBuildColumn(columns, rows, column);
            if (!canRemove) {
                break;
            }
        }
        if (canRemove) {
            // 최적화를 위함
            for(Position row: rows) {
                canRemove = canBuildRow(columns, rows, row);
                if (!canRemove) {
                    break;
                }
            }                        
        }

        // 삭제 불가능하면 다시 추가
        if (!canRemove) {
            columns.add(newPosition);
        }
    } else {
        // 임시로 보 삭제
        rows.remove(newPosition);

        // 기존 기둥, 보가 유지 가능한지 검사
        for(Position column: columns) {
            canRemove = canBuildColumn(columns, rows, column);
            if (!canRemove) {
                break;
            }
        }
        if (canRemove) {
            for(Position row: rows) {
                canRemove = canBuildRow(columns, rows, row);
                if (!canRemove) {
                    break;
                }
            }
        }

        // 삭제 불가능하면 다시 추가
        if (!canRemove) {
            rows.add(newPosition);
        }
    }
}

이 처럼 기존에 설치 요청 검증을 위해 만들어 두었던 메서드에 현재 삭제 요청이 반영된 리스트를 넣고 해당 리스트의 원소를 순회하면서 삭제 요청이 반영되어도 그 자리에 계속 있을 수 있는지를 확인한다. 이렇게 하면 삭제 요청은 시간복잡도 O(N^2)가 되지만 어차피 입력은 1000개 안쪽으로 주어지므로 이렇게 구현해도 문제가 되지 않을 것 같았다. (카카오 코테 때 이 문제에 효율성 채점을 하지 않긴 했다)

정답 배열 구성

이렇게 순회를 마치면 리스트 columns, rows에 모든 요청을 처리하고 마지막 상태에 남아있는 기둥과 보가 담겨있게 된다. 문제에서 이를 [가로좌표, 세로좌표, 코드](코드 - 기둥(0), 보(1)) 을 행으로 갖는 2차원 배열 형태(앞의 원소부터 오름차순 정렬)로 반환하라고 했으므로 자바의 Stream을 사용해 2차원 배열을 만들어준다.

return Stream.concat(
    columns.stream().map(column -> new int[]{column.x, column.y, 0}),
    rows.stream().map(row -> new int[]{row.x, row.y, 1}))
    .sorted(Comparator.comparingInt((int[] arr) -> arr[0])
           .thenComparingInt(arr -> arr[1])
           .thenComparingInt(arr -> arr[2]))
    .toArray(int[][]::new);

이렇게까지 스트림을 써본건 처음인데, 위 코드를 원래는 아래와 같이 풀어냈었다.

// 배열로 만들어서 반환
int answerSize = columns.size() + rows.size();
int[][] answer = new int[answerSize][3];

int index = 0;
for(Position column: columns) {
    answer[index][0] = column.x;
    answer[index][1] = column.y;
    answer[index][2] = 0; // 기둥
    index++;
}
for(Position row: rows) {
    answer[index][0] = row.x;
    answer[index][1] = row.y;
    answer[index][2] = 1; // 보
    index++;
}

// 정렬 후 반환
Arrays.sort(answer, 
            Comparator.comparingInt((int[] arr) -> arr[0])
           .thenComparingInt(arr -> arr[1])
           .thenComparingInt(arr -> arr[2]));

return answer;

그런데 문제를 풀고 나서 찾아보니 Stream.concat()을 써서 각 리스트를 1차원 배열의 Stream으로 만들고 합쳐서 해결할 수 있는 방법이 있었다. 확실히 스트림을 쓰는게 가독성과 (코드 작성 시의) 효율성면에서 엄청난 이점이 있는 것 같다. 내가 모르는 Stream 함수를 좀 더 찾아보고 써봐야겠다는 생각을 하게 됐다.

전체 코드

github 링크

참고자료

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설