Today's Algorithm(2019-02-06)

programmers. 프렌즈4블록

이런 구체적인 상황이 있는 문제를 좋아하는데 시간은 꽤 오래걸렸습니다.. 그 이유를 생각해보면 다음과 같습니다.

• 새로운 클래스를 새로 만들어야할지, 여기에 어떤 상태값을 만들어야할지 충분히 고려하지 않고 문제를 푼 바람에 우왕좌앙 했습니다. 그러다보니 이를 담는 자료구조도 몇번 바꾸고, 또 막상 만들어놓고 필요없는 경우도 있었습니다.

  • 좀더 고민하고 문제를 푸는 것이 더 시간 절약에 효과적일 것 같습니다.

• 블록을 담는 자료구조에 순서를 잘못 담았습니다. 밑에부터 담아야하는데 위로부터 담았네요.

• List를 여러개 다루면서 각각의 인덱스가 무엇을 의미하는지, 제가 의도하는 인덱스를 정확하게 파악하는데 조금 시간이 걸렸습니다.

 

이 문제에서 가장 고민되었던 부분은 '동시에 지워야한다는 것'입니다. 그 이유는 지우는데 순서가 있으면 그것이랑 관련있는 다른 블록이 연관있어서 그렇습니다. 예를들어 4개가 갖추어져 지워진다고 생각했을 때, 그리고 그 중 하나의 블록이 다른 4개의 블록에 연관되어 있으면 그게 지워지면서 저희가 기대한 결과가 발생하지 않습니다. 그게 좀 고민이었는데 해결책은 이외로 간단했습니다. 그냥 삭제 표시해놓고 이후 다시 돌면서 삭제 표시한 것을 Index 간섭없도록 높은 순으로부터 지우는 것이죠.

 

문제를 풀 때 row단위로 List를 만들어서 지울때는 remove() 메서드를 이용하여 내려오게 만들었습니다. 그렇기 주의할 점은 List의 인덱스와 그 안의 인덱스를 실수없이 정확히 파악해야한다는 것입니다. 저는 여기에서 시간을 가장 많이 걸렸고 그 때문에 디버깅 출력을 여러번 하면서 실수를 찾을 수 있었습니다. 이 시간은 연습을 통해 좀 줄어야할 시간입니다!

 

class Solution {
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        List<List<Point>> lists = init(m, n, board);

        while (true) {
            int deleted = 0;

            for (int col = 0; col < n - 1; col++) {
                List<Point> list = lists.get(col);
                for (int row = list.size() - 1; row > 0; row--) {
                    if (haveSquare(lists, col, row) && canDelete(lists, col, row)) {
                        list.get(row).shouldBeDeleted = true;
                        list.get(row - 1).shouldBeDeleted = true;
                        lists.get(col + 1).get(row).shouldBeDeleted = true;
                        lists.get(col + 1).get(row - 1).shouldBeDeleted = true;
                    }
                }
            }

            for (int col = 0; col < n; col++) {
                for (int row = lists.get(col).size() - 1; row >= 0; row--) {
                    Point point = lists.get(col).get(row);
                    if (point.shouldBeDeleted) {
                        lists.get(col).remove(point);
                        deleted++;
                    }
                }
            }

            answer += deleted;
            if (deleted == 0) break;
        }

        return answer;
    }

    boolean canDelete(List<List<Point>> lists, int col, int row) {
        String s1 = lists.get(col).get(row).value;
        String s2 = lists.get(col).get(row - 1).value;
        String s3 = lists.get(col + 1).get(row).value;
        String s4 = lists.get(col + 1).get(row - 1).value;
        return s1.equals(s2) && s2.equals(s3) && s3.equals(s4);
    }

    private boolean haveSquare(List<List<Point>> lists, int col, int row) {
        return lists.get(col + 1).size() - 1 >= row;
    }

    public List<List<Point>> init(int m, int n, String[] board) {
        List<List<Point>> lists = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<Point> list = new ArrayList<>();
            lists.add(list);
        }

        for (int i = m - 1; i >= 0; i--) {
            String[] splitted = board[i].split("");
            for (int j = 0; j < n; j++) {
                lists.get(j).add(new Point(i, j, splitted[j]));
            }
        }

        return lists;
    }
}

class Point {
    int row;
    int col;
    String value;
    boolean shouldBeDeleted = false;

    public Point(int row, int col, String value) {
        this.row = row;
        this.col = col;
        this.value = value;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Point point = (Point) o;
        return row == point.row &&
                col == point.col;
    }
}