[프로그래머스/JAVA] 햄버거 만들기

 

 

https://github.com/ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다. 😊
초보들로 구성되어 있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
참여 문의는 댓글 혹은 GitHub 주소를 참고해 주세요.

---

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/133502#qna

프로그래머스

 

 

풀이 방법

문자열("1231")을 공백으로 치환하면 된다.

 

내 코드(JAVA)

 

public static int solution(int[] ingredient) {
    final String MAKE_BURGER = "1231";
    int answer = 0;
    StringBuilder sb = new StringBuilder();

	// 미리 다 담고
    for (int i : ingredient) {
        sb.append(i);
    }
	
    // 반복문을 돌며 "1234" -> ""로 치환하며 갯수를 샌다
    while (sb.indexOf(MAKE_BURGER) > -1) {
        int from = sb.indexOf(MAKE_BURGER);

        sb.delete(from, from + 4);
//            sb.replace(from, from + 3, "");
        answer++;
    }


    return answer;
}

 

해당 코드는 3개의 케이스에서 시간초과가 발생한다.

미리 담아두지 말고 담을 때마다 검사하거나, indexOf를 한 번만 하도록 개선하거나, replace를 delete로 바꾸는 등 리팩토링을 해봤지만 잘 되지 않았다.

 

public static int solution(int[] ingredient) {
    final String MAKE_BURGER = "1231";
    int answer = 0;
    StringBuilder sb = new StringBuilder();

    for (int i : ingredient) {
        sb.append(i);

        // 1(빵)이 나오고, 쌓인 재료가 4개 이상(만드는데 필요한 갯수)이고, 끝자리부터 뒷 4자리의 문자열이 "1231"인지 확인
        if(i == 1 && sb.length() >= 4 && sb.subSequence(sb.length() - 4, sb.length()).equals(MAKE_BURGER)) {
            sb.delete(sb.length() - 4, sb.length()); // 햄버거 만들기
            answer++;
        }
    }

    return answer;
}

 

 

- 문제를 잘 보면 빵이 나왔을 때만 햄버거를 만들 수 있는지 확인하여 만들 수 있다.

- 한 번 만드는데 4개의 재료가 필요하니 최소 쌓인 문자열의 길이는 4보다 커야 한다.

- 재료를 쌓을 때마다 검사하므로 마지막 문자열에서 필요 재료의 개수인 4자리만 검사하면 된다.

  StringBuilder의 subSequence()를 활용했는데, 문자열의 위치를 사용하여 잘라내 새로운 문자 시퀀스를 만들어낸다.

  미리 다 쌓아두고 찾을 때 쌓인 데이터가 많거나, 가장 뒤에 나온다면 탐색해야 할 양이 많아진다.

 

StringBuilder sb = new StringBuilder("12345678");

println(sb.subSequence(sb.length() - 4, sb.length())); // 5678
println(sb.subSequence(0, 4)); // 1234