프로그래머스 Lv.3) 리틀 프렌즈 사천성

2017 카카오코드 본선

리틀 프렌즈 사천성

코딩테스트 연습 - 리틀 프렌즈 사천성

풀이

문제를 꼼꼼히 읽지 못해서 푸는데 많은 삽질과 시간을 투자했다.. 

첫번째로 간과한 부분은

경로는 두 개 이하의 수평/수직 선분으로 구성되어 있고, 이들은 모두 연결되어 있다. (즉, 경로를 한 번 이하로 꺾을 수 있다)
참고: 프렌즈 사천성은 경로가 세 개 이하의 선분으로 구성되어야 한다는 점이 다르다. (즉, 경로를 두 번 이하로 꺾을 수 있다)

선분이 3개 이하일 경우 블록을 제거할 수 있다고 생각했는데, 선분이 두개인 경우(한번만 경로를 꺾는경우)만 제거할 수 있다는 부분이었다. 이걸 간과한게 아주 컸다. 코드를 짜는 시간, 효율적인 코드를 생각하는 시간 등 에너지 소비가 불필요하게 많았다.. 그래서 이 부분에 따라서 다시 코드를 짜니까 바로 통과했다.. ㅠ

 

두번째로 간과했던 부분은

같은 모양의 타일은 두 개씩 배치되어 있다

이 부분이었다. 타일이 여러개 있을 수 있다고 생각하고 코드를 진행했었는데, 두개만 있다니... ㅠ 아무튼, 이 부분을 고치는데는 오래 걸리지 않았다. 첫번째로 언급한 부분보다 이걸 먼저 캐치해서 금방 고쳤었다.

 

내가 짠 로직은 먼저 String 1차원 배열인 board를 2차원 char 배열로 변경해주는 것이다. 처음에는 String에 따라 charAt으로 문자를 가져오고, StringBuffer의 setCharAt 메소드로 문자열을 바꿔주는 방식으로 구성했었는데, 너무 비효율적이라는 생각이 들었기 때문이다.

다음은 board를 돌면서 알파벳과 좌표를 담는 Pos 클래스를 만들어 ArrayList에 저장해주었다.

이후, 알파벳 오름차순에 따라 제거하는게 더 빠르다는 생각에, Collections의 sort 메소드를 이용해 알파벳 오름차순으로 저장해주었다.

새로운 char[][] Board을 돌면서 블록을 지울 수 있을 때 까지 반복하고, Pos가 담겨있는 ArrayList를 순서대로 돌며 제거 가능한지 파악했다. 삭제할 수 있다면 리스트에서도 해당 블록들을 지워주고, 해당 좌표에 '.'을 저장해주었다. 동시에 StringBuffer에 문자를 붙이면서 while문이 종료된 다음, ArrayList에 남아있는 블록이 없다면 StringBuffer의 toString으로 문자열을 반환했다.

 

이해하기 어려운 부분이 아마 increaseX,Y 메소드 부분일거라고 생각한다. 이 부분은 원래 같은 두 블록이 존재할 수 있는 모든 경우를 따져, 기준점이 board의 오른쪽 위에, 비교할 대상이 좌측 아래있을 때를 위해 만들었던 메소드다.

모든 경우의 수에는

1. 블록이 같은 세로 직선상에 있는 경우(X좌표가 같음)

2. 같은 가로 직선상에 있는 경우(Y좌표가 같음)

3. 좌측 상단에 기준블록이 있고 우측 하단에 비교블록이 있는 경우, 

4. 우측 상단에 기준블록이 있고 좌측 하단에 비교블록이 있는 경우

가있다.

 

3번과 4번같은 경우는 경로가 두 가지가 존재하는데, 어차피 직선이기 때문에 탐색할 직선에 대해서 출발점과 종료점만 잘 잡아주면 1~2개의 메소드로 처리가 가능할 것 같았기 때문에, 2개의 메소드로 모든 경우를 커버했다. x축과 y축 각각 기준점으로 부터 도착지점까지 '.' 이나 같은 블록을 탐색하며 하나의 직선을 먼저 확인하고, x축이 먼저였다면 다음에는 y축을, y축이었다면 x축을 각각 다시 검사하면서 두 직선을 검사할 수 있게 만든 메소드이다.

 

로직

1. String[] Board를 char[][] chBoard로 저장해준다.

2. chBoard를 한번 쭉 돌면서, .과 *을 제외한 블록과 위치를 미리 만들어둔 Pos클래스를 이용해 ArrayList에 담아준다.

3. while문을 통해 블록을 제거할 수 있을 때 까지 반복해준다.

 3-1. Pos가 담겨있는 ArrayList를 돌면서 삭제할 수 있다면 블록 삭제, chBoard에 해당 위치를 . 으로 변경, 답이 될 String에 해당 블록의 이름을 추가하고  for문을 종료해준다.

 3-2. ArrayList를 돌면서 2씩 증가하는 부분과, blockList가 전체 사이즈의 -1만큼 도는 이유는, 같은 블록은 연달아 두개씩 저장되어있기 때문이다.

 3-3. 지울 수 있는지 검증하는 부분은, 위에서 적어둔 모든 경우의 수에 따라 각각 다르게 검증해준다.

 

코드

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    String IMPOSSIBLE = "IMPOSSIBLE";
    
    public String solution(int m, int n, String[] board) {
        StringBuffer sb = new StringBuffer();
        char[][] chBoard = getChBoard(m,n,board);
        ArrayList<Pos> blockList = getBlockList(m, n, chBoard);
        
        boolean isRemoved = true;
        while(isRemoved) {
            isRemoved = false;
            for(int i=0; i<blockList.size()-1; i+=2) {
                Pos origin = blockList.get(i);
                Pos target = blockList.get(i+1);
                if(canRemove(chBoard, origin,target)) {
                    // 삭제
                    blockList.remove(i);    // origin 삭제
                    blockList.remove(i);    // target 삭제
                     //board 수정
                    chBoard[origin.y][origin.x] = '.';
                    chBoard[target.y][target.x] = '.';
                    //타일 추가
                    sb.append(origin.ch);
                    // 삭제 표시
                    isRemoved = true;
                    break;
                }
            }
        }
        
        if(blockList.size() !=0) {
            return IMPOSSIBLE;
        }
        
        return sb.toString();
    }
    
    private ArrayList<Pos> getBlockList(int m, int n, char[][] board) {
        ArrayList<Pos> result = new ArrayList<>();
        
        for(int y=0; y<m; y++) {
            for(int x=0; x<n; x++) {
                if(board[y][x] >=65 && board[y][x]<=90) { // 알파벳
                    if(!result.contains(board[y][x])) {
                        result.add(new Pos(x,y,board[y][x]));
                    }
                }
            }
        }
        Collections.sort(result);
        
        return result;
    }
    private char[][] getChBoard(int m, int n, String[] board) {
        char[][] result = new char[m][n];
        for(int i=0; i<m; i++) {
            result[i] = board[i].toCharArray();
        }
        return result;
    }
    
    private boolean canRemove(char[][] board, Pos origin, Pos target) {
        boolean result = true;
        if(origin.x == target.x) {  // 세로로 일직선 상
            result = increaseY(origin.x, origin.y, target.y, board, origin.ch);
        } else if(origin.y == target.y) {   // 가로로 일직선 상
            result = increaseX(origin.y, origin.x, target.x, board, origin.ch);
        } else {    // 좌상, 우하   || 우상, 좌하에 두개가 위치함
            if(origin.x < target.x) {   // 좌상 우하
                // 아래부터 가는 경우
                boolean down = increaseY(origin.x, origin.y, target.y, board, origin.ch);
                if(down) {
                    down = increaseX(target.y,origin.x,target.x,board,origin.ch);
                    System.out.println(origin.ch);
                }
                
                // 오른쪽부터 가는 경우
                boolean right = increaseX(origin.y, origin.x, target.x, board, origin.ch);
                if(right) {
                    right = increaseY(target.x, origin.y, target.y, board, origin.ch);
                }
                if(!(down || right)) {
                    result = false;
                }
            } else {    // 우상 좌하
                //아래부터 가는경우
                boolean down = increaseY(target.x, origin.y,target.y,board, origin.ch);
                if(down) {// 오른쪽 확인
                    down= increaseX(origin.y,target.x,origin.x,board,origin.ch);
                }
                
                // 오른쪽부터 가는경우
                boolean right = increaseX(target.y,target.x,origin.x,board,origin.ch);
                if(right) { // 위에 확인
                    right = increaseY(origin.x,origin.y,target.y,board,origin.ch);
                }
                if(!(down||right)) {
                    result = false;
                }
            }
        }
        
        return result;
    }
    
    private boolean increaseY(int standardX, int standardY, int targetY, char[][] board, char ch) {
        for(int y=standardY; y<=targetY; y++) {
            if(board[y][standardX] != '.' && board[y][standardX] != ch) {
                return false;
            }
        }
        return true;
    }
    
    private boolean increaseX(int standardY, int standardX, int targetX, char[][] board, char ch) {
        for(int x=standardX; x<=targetX; x++) {
            if(board[standardY][x] != '.' && board[standardY][x] != ch) {
                return false;
            }
        }
        return true;
    }
}

class Pos implements Comparable<Pos>{
    int x;
    int y;
    char ch;
    
    public Pos(int x, int y, char ch) {
        this.x = x;
        this.y = y;
        this.ch = ch;
    }
    
    @Override
    public int compareTo(Pos p) {
        return this.ch >= p.ch ? 1:-1;
    }
}