프로그래머스) 햄버거 만들기 풀이 (Java)

 > 휴일 동안 풀었던 코테 문제 중 가장 오래 걸린 '햄버거 만들기' 문제의 풀이를 작성해보았다.

 

학습 키워드: Java, Stack, StringBuilder

 

133502 - 햄버거 만들기

1) 문제 설명 요약 (원문은 하단 링크 참고):

 - 햄버거 가게에서 일하는 알바생 앞으로 재료가 쌓이는데, 빵-야채-고기-빵 순서로 쌓여 있을 때만 버거를 조립한다. 재료가 쌓이는 순서 ingredients가 주어지고, 빵은 1, 야채는 2, 고기는 3일 떄, 알바생이 몇 개의 버거를 조립할 수 있는지를 세어 반환해야한다.

 - 조건: 1 <= ingredients.length() <= 1000000

 

2) 작성한 코드의 기본 틀:

 - 문제 자체는 보자마자 Stack이나 recursion의 냄새가 나는 구조다. 그치만 제한사항을 보면 ingredients 크기가 100만이라서 잘 못 구현했다가는 시간 초과나 stack overflow가 날 수 있다.

import java.util.Stack;

class Solution {
    public int solution(int[] ingredients) {
        int start = findFirstBreadIndex(ingredients);
        if (start == -1) return 0;
        return getBurgerCount(ingredients, start);
    }

    private int getBurgerCount(int[] ingredients, int start) {
        int burgerCount = 0;
        // do some counting

        return burgerCount;
    }

    private int findFirstBreadIndex (int[] ingredients) {
        for (int i = 0; i < ingredients.length; i++) {
        	if (ingredients[i] == 1) return i;
        }
        return -1;
    }
}

 - 여러 버전으로 코드를 작성했었는데, 기본적으로 위의 형식에서 getBurgerCount 함수의 내용만 바뀌었다. 처음에는 recursion이나 array만을 사용해서 풀려고 시도했었는데, array는 버거의 완성 이후 index 관리가 힘들고, recursion의 경우 잘 못하면 call stack이 100만개가 쌓여 overflow가 날 수도 있고, 두 가지를 섞자니 코드가 너무 난잡해져서 이렇게 저렇게 바꿔보다가 결국 포기하고 Stack을 사용하기로 했다.

 

3) Stack을 사용한 풀이 (오답):

import java.util.Stack;

...

private int getBurgerCount (int[] ingredients, int start) {
    Stack<Integer> stack = new Stack<Integer>();
    int burgerCount = 0;
    stack.push(ingredients[start]);
    for (int i = start + 1; i < ingredients.length; i++) {
        int cur = ingredients[i];
        if (cur == 1 && stack.peek() == 3) {
            int meat = stack.pop();
            if (stack.peek() == 2) {
                int veggie = stack.pop();
                if (stack.peek() == 1) {
                    stack.pop();
                    burgerCount++;
                    continue;
                }
                stack.push(veggie);
            }
            stack.push(meat);
        }
        stack.push(ingredients[i]);

    }
    return burgerCount;
}

 - Stack을 사용한 첫 번째 코드인데, 루프를 돌면서 ingredients의 항목들을 스택에 추가하고, 빵이 나타날 때 마다 스택의 꼭대기에 고기가 있는지 확인하고, 고기가 맞으면 야채와 빵을 차례대로 확인하여 버거의 카운트를 늘리는 방식이다. 결과는 두 개의 케이스가 런타임 에러로 실패했다. 런타임 에러로 실패하는 경우는 런타임에서 exception이 발생하여 프로그램이 종료되었을 때 나타나는 결과다. 위 코드에서는 Stack 밖에 사용하지 않았으므로, 발생할 수 있는 에러는 for loop의 OutOfBounds나 Stack의 pop()과 peek()가 발생시키는 EmptyStackException 밖에 없다. For loop는 아무런 문제가 없으므로, 결국 스택이 비어있을 때 해당 method를 호출했다는 뜻이 된다. 문제는 자바의 Stack이 스스로의 크기를 기억하지 않기 때문에 코드를 수정하려면 스택에 들어가고 나가는 항목들의 수를 일일이 세어야한다. 코드가 지저분해지고 안그래도 스택이라 동작 시간이 길어졌는데 길이 잰다고 덧셈 뺄셈까지 했다간 더 길게 나오겠다 싶어 스택 또한 드랍하고 다른 방식을 사용하기로 했다.

 

4) StringBuilder를 이용한 풀이 (오답):

import java.lang.StringBuilder;

...

private int getBurgerCountSB (int[] ingredients, int start) {
    StringBuilder sb = new StringBuilder();
    int burgerCount = 0;
    sb.append(ingredients[start]);
    for (int i = start + 1; i < ingredients.length; i++) {
        int cur = ingredients[i];
        if (cur == 1 && sb.charAt(sb.length() - 1) == '3') { // #2 out of bounds (test 18)
            int begin = sb.length() - 3;
            if (begin < 0) continue; // #1 resolves out of bounds (test 2)
            int end = sb.length();
            if (sb.substring(begin, end).equals("123")) {
                sb.delete(begin, end);
                burgerCount++;
                continue;
            }
        }
        sb.append(cur);
    }
    return burgerCount;
}

 - 다음은 StringBuilder를 Stack처럼 이용한 풀이다. StringBuilder는 String과 동일하게 length()라는 method를 이용하여 크기를 알 수가 있는데, 이를 사용하여 #1 처럼 begin의 값이 0 아래로 내려가서 OutOfBounds에러가 발생하지 않도록 설정해주었다. 이렇게 테스트 케이스 2번이 해결되었으나 18번은 여전히 실패했는데, 알고보니 내가 간과하고 있던 사실이 하나 있었다. 처음에 getBurgerCount에 진입할 때는 이미 ingredients의 첫 번째 빵의 위치를 찾아뒀기 때문에 sb.append로 빵 하나를 추가하고 시작할 수 있어서 바로 앞 인덱스가 비어있을 일이 없다고 착각했으나, [1, 2, 3, 1, 1, 2, 3, 1] 과 같은 구성의 ingredients가 주어지면 첫 번째 버거가 완성 된 이후 sb가 빈 문자열이 되어 다음 1에서 sb의 length() - 2가 -1이 되어 OutOfBounds가 출력된다.

 

5) StringBuilder를 이용한 풀이 (정답):

private int getBurgerCountSB (int[] ingredients, int start) {
    StringBuilder sb = new StringBuilder();
    int burgerCount = 0;
    sb.append(ingredients[start]);
    for (int i = start + 1; i < ingredients.length; i++) {
        int cur = ingredients[i];
        if (sb.length() > 2) { // #1
            if (cur == 1
                 && sb.charAt(sb.length() - 1) == '3'
                 && sb.charAt(sb.length() - 2) == '2'
                 && sb.charAt(sb.length() - 3) == '1') {
                sb.setLength(sb.length() - 3);
                burgerCount++;
                continue;
            }
        } 
        sb.append(cur);
    }
    return burgerCount;
}

 - 18번 테스트 케이스를 해결하기 위해 #1 처럼 sb.length()의 길이가 2 이상일 때만 버거 확인 작업을 하도록 제한하고, 속도를 조금이라도 더 줄여볼까 싶어 내부 if문의 조건에서 substring과 equals를 빼고 charAt을 사용하여 문자별로 하나씩 비교하도록 변경했는데, 뺄셈 작업이 여럿 끼어서 그런지 생각만큼 단축되는 느낌은 아니었다. 또한, delete와 setLegnth도 케이스마다 줄기도 하고 늘기도 하여 무엇이 더 효율이 좋다 라고 얘기할 정도는 아니라고 생각된다.

 

6) 마무리:

 - 주말동안 풀었던 6개의 문제 중 가장 많은 시간을 쓴 문제인데, 원인은 결국 array만으로 풀려던 고집이다. 실제로 코딩 테스트에 주어지는 시간은 짧기 때문에 복잡한 방법을 고민하기 보다는 Stack처럼 직관적으로 해결할 수 있는 방법을 선택하는게 좋겠다. 또한, 요즘에 풀이마다 Array로 카운트하는 습관이 들어있는데, 이번 문제처럼 적용이 어려운 형태에서는 스택 구조와 동일하게 사용할 수 있고 추가와 제거가 빠른 편인 StringBuilder를 활용하는 방식을 빠르게 떠올리도록 문제를 꾸준히 풀며 반복 숙달 해야겠다.

 

 

--

 

REFERENCES:

 

프로그래머스

 > programmers.co.kr, 햄버거 만들기