카카오 포크레인 문제

알고리즘을 풀다 보면, break 의 범위가 어디까지 적용되는지 헷갈릴 때가 많다. 

break를 블록 안에 넣어줄 때와, 그렇지 않을 때 답이 달라서 한참을 삽질하다가 break 를 다시 공부하는 계기가 되었다. 

 

문제 참고 

https://programmers.co.kr/learn/courses/30/lessons/64061

 

2차원 배열 : int[][] doub

옮기면서 쌓는 스택 배열: movedArr 

답안 코드 (인프런 강의 참고) 

 

break 를 설명하기 전에, 문제 풀 때 염두해야 하는 것은 

 

1) 인형을 뽑고 나면, 0으로 바꿔줘야 한다. 이때, tmp 에 0으로 바꿔주기 전의 값을 복사해주지 않으면, 0과 값을 비교하게 됨.

2)stack.isEmpty()! 를 걸어주지 않으면, peek()을 적용할 수 없고 emptyStackException 이 발생한다.  

public class Puppet {
    public int solution(int[][] doub, int n, int[] moves) {
        int answer = 0;
        Stack<Integer> movedArr = new Stack<>();
        for(int pos: moves) {
            for (int j = 0; j < doub.length; j++) {
                //0이 아님 = 인형을 찾았다.0이 아니라면, 무조건 0으로 만들어야 함 (원소 같음여부와 상관없이.
                if (doub[j][pos-1]!=0) {
                    int tmp = doub[j][pos-1];
                    doub[j][pos-1] = 0;
                    //movedArr가 비어있지 않고 peek 과 현재 원소가 같다면 Pop
                    if(!movedArr.isEmpty()&&tmp == movedArr.peek()){
                            answer = answer + 2;
                            movedArr.pop();
                    //그 외 모든 조건 movedArr 가 비어있던, peek 과 같지 않던 push 한다.
                    } else {
                        movedArr.push(tmp);
                        break; //가장 가까운 반복문은 doub.length 도는 for문,
                    }
                }
                }
//            break; //break: 자신이 포함된 가장 가까운 반복문을 벗어난다.
            }
        return answer;
    }

    public static void main(String[] args){
        Puppet T = new Puppet();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //2차원 배열을 먼저 만들고 스택화하기
        int[][] doub = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++) {
                    doub[i][j] = sc.nextInt();
            }
        }
        int movesCnt = sc.nextInt();
        int[] moves = new int[movesCnt];
        for(int i=0;i<movesCnt;i++){ //movesCnt 길이의 배열이 생긴다.
            moves[i] = sc.nextInt();
        }
        System.out.println(T.solution(doub, n, moves));
    }
}

문제의 오답코드는 아래와 같다 

 

//옮기는 배열이 비어있지 않고, 맨 위 값이 현재 값과 같다면 두 값 모두 사라지니까 answer가 2 늘어남. 
if(!movedArr.isEmpty()&&tmp == movedArr.peek()){
        answer = answer + 2;
        movedArr.pop();

//그 외 모든 경우는 옮기는 배열에 값을 넣는다. 
} else {
    movedArr.push(tmp);
    break; //가장 가까운 반복문은 doub.length 도는 for문,
}

우선 자바의 정석에서 break 문의 정의를 다시 보자. 

break 문은 자신이 포함된 가장 가까운 반복문을 벗어난다. 

위의 코드 처럼 break가 else 블록 안에 있다면, if 블록이 실행 된 이후에는 break가 접근할 방법이 없다. 

위의 경우에는 5번째 칼럼에서 이미 1을 뺐는데, 다음에 탐색할 값인 2를 한번 더 뺴게 된다

(아래 캡처를 보면, 임시 값인 tmp가 2라는 것을 알 수 있다) 

 

if 와 else 모두 break에 접근할 수 있게, break를 블록에서 꺼내준다. 

그러면 한번 더 인형을 꺼내지 않고, moves 다음 배열로 넘어간다. 

if(!movedArr.isEmpty()&&tmp == movedArr.peek()){
        answer = answer + 2;
        movedArr.pop();
} else movedArr.push(tmp);
    break; 
}