프로그래머스 - 133502 : 햄버거 만들기 (시간 초과 , String 의 replace, + 연산에 대한 고찰) 풀이 및 리마인딩

🍔햄버거 만들기

 

https://school.programmers.co.kr/learn/courses/30/lessons/133502

프로그래머스

 

✔️문제 설명

햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다. 상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며, 재료의 높이는 무시하여 재료가 높이 쌓여서 일이 힘들어지는 경우는 없습니다.

예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 2개의 햄버거를 포장하게 됩니다.

상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때, 상수가 포장하는 햄버거의 개수를 return 하도록 solution 함수를 완성하시오.

 

✔️제한사항

1 ≤ ingredient의 길이 ≤ 1,000,000
ingredient의 원소는 1, 2, 3 중 하나의 값이며, 순서대로 빵, 야채, 고기를 의미합니다.

 

 

✔️입출력 예

ingredien	result
[2, 1, 1, 2, 3, 1, 2, 3, 1]	2
[1, 3, 2, 1, 2, 1, 3, 1, 2]	0

 

✔️입출력 예 설명

• 입출력 예 #1
  문제 예시와 같습니다.

 

• 입출력 예 #2
  상수가 포장할 수 있는 햄버거가 없습니다.

 

---

📝풀이 및 리마인딩(스포주의)

 

public class LS_133502 {
    public int solution(int[] ingredient) {
        int answer = 0;
        StringBuilder sb = new StringBuilder();
        for (int j : ingredient) {
            sb.append(j);
            if (sb.length() > 3 && sb.subSequence(sb.length() - 4, sb.length()).equals("1231")) {
                answer++;
                sb.delete(sb.length() - 4, sb.length());
            }
        }
        return answer;
    }
 
    public int solution2(int[] ingredient) {
        int answer = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ingredient.length; i++) {
            sb.append(ingredient[i]);
        }
        String str = sb.toString();
        while(str.contains("1231")){
            str = str.replaceFirst("1231","");
            answer++;
        }
        return answer;
    }
}

 

위의 solution() 은 맞은 풀이 solution2()은 틀린 풀이이다.

 

 

 

❌틀린 풀이 결과 

테케 12번에서 상수 햄버거 쌓다가 골병났다는...썰이 있다.... 우리가 이렇게 만들었다....... 덜 힘들게 해주자......ㅜ,ㅜ

 

⭕맞은 풀이 결과

 

틀린 풀이와 맞은 풀이의 시간 차이를 보면 압도적인 시간 차이가 있다는 걸 확인할 수 있다.

 

 

🔑해설

 

문제를 보자마자 배열을 문자열로 바꿔서 subString 이 있는지 확인하면 될 거라 생각했다. 

이때 String 그자체를 다루는 게 아니라 StringBuilder 로서 다뤄야하는데, 이 사실을 알고 문제를 풀었지만 많은 사람들이 잘 모르는 거 같아 글도 쓸겸 리마인딩할겸 작성해 보았다.

 

많이들 푸는 방법이 

[2, 1, 1, 2, 3, 1, 2, 3, 1] 의 배열이 주어 진다면 "211231231" 로 문자열을 만들고 이어진 "1231"을 공백으로 replace 시켜 그 횟수를 카운트 하는 방법을 떠올렸을 것이다.

방법론 적으론 맞지만 String 으로 로직을 다룬다면 시간 초과가 날 것이다.

 

 

우리는 String 클래스의 특징을 알아야한다.

특히나 String 에서 += 또는 + 연산을 지양 해야한다.

 

String str = "1";
str += "2";
str += "3";
str += "4";

위 와 같이 연산을 한다면 한 문자열에 1234 가 합쳐지 문자열이 되는게 아니라 + 연산 할때마다 새로운 객체를 만들어서 연산을 수행하기 때문이다.

Constant Pool에서는 기존의 데이터의 변경이 아닌 새로운 리터럴의 추가가 계속해서 이루어 진다.

위의 코드의 경우, "1" , "12" , "123" , "1234"가 각각 String Constant Pool에 새로운 리터럴로 저장되며 아무도 참조하지 않은 리터럴은 GC가 회수해 가는 과정을 거치게 된다.

 

이러한 과정은 성능 저하의 원인이 된다.

 

 

🤔어느 부분에서 성능이 떨어진다는 것일까?

 

성능을 따질때는 항상 시간복잡도나 공간복잡도를 따져야 한다.

결론만 말하자면 Java에서 String의 '+=' 또는 '+' 연산의 경우 O( N + K )의 시간복잡도를 가진다.

N은 기존의 문자열(lhs)의 길이, K는 더하려고 하는 문자열(rhs)의 길이다.

 

아래의 코드를 예시로 연산횟수에 대한 시간복잡도를 계산해보자.

s += "A"; 에서 i번째에서 s의 길이 + "A"의 길이1 만큼의 시간이 소요되고 그과정을 N번만큼 반복하므로

연산횟수는 N * (N+1) / 2 * N 이고, 총 시간복잡도는 O( N^3 )이 된다.

N * (N+1) / 2   는 1부터 N까지의 합, N은 반복문 횟수)

 

public class Main {
    public static void main(String[] args) {
        String str = "";
        int n = 1000000;
        for(int i = 0; i < n; i++){
        	s += "A";
        }
    }
}

 

 

 

이러한 '+' 연산은 StringBuffer 또는 StringBuilder를 이용하면 일반적인 경우 O(1)에 해결할 수 있으며

위의 코드를 아래처럼 바꾼다면 sb.append("A"); 의 시간복잡도는 O(1)이 되므로 전체 시간복잡도를 O(N)으로 줄일 수 있는 효과를 가져온다 !

public class Main {
    public static void main(String[] args) {
        StringBuider sb = new StringBuider();
        int n = 1000000;
        for(int i = 0; i < n; i++){
        	sb.append("A");
        }
    }
}

 

 

String 내장함수 replace의 시간복잡도는 O(문자열의 길이 * (교체할 문자열의 길이 + 교체되는 문자열의 길이/교체할 문자열의 길이))이다.

 즉, str.replace(a, b)라면 O(len(str) * (len(a) + len(b)/len(a)))이다.

replace 함수는 문자열 str의 길이만큼 전체적으로 문자열을 하나씩 탐색하고 교체할 문자열의 길이만큼 이전값을 탐색해서 교체해야하는 문자열인지 아닌지를 판별한다.

교체해야 하는 경우, 교체되는 문자열의 길이에 따라 추가 연산이 필요하다.

교체되는 문자열의 길이가 교체할 문자열의 길이와 같은 경우, 할당된 길이만큼(교체할 문자열의 길이만큼)만 연산을 수행하면 되기 때문에 O(len(b) / len(a)) = O(1)로 상수의 시간이 소요된다.

교체되는 문자열의 길이가 교체할 문자열의 길이보다 큰 경우, 초과된 길이만큼 새 위치를 만들고 교체가 이뤄지므로 O(len(b) / len(a))만큼의 추가 연산이 소요된다. 따라서 이 경우가 최악의 경우다.

 

 

 

마무리

String을 이용하면 문자열을 리터럴로 초기화 할 수 있어 빠르게 생성이 가능하고

리터럴은 불변하기 때문에 재사용할 경우 메모리 소모가 적다는 장점이 있었다.

 

하지만 String의 문자열 추가 연산은 느리고 추가할 때마다 매번 새로운 문자열을 추가하기 때문에

잦은 변경이 이루어 진다면 StringBuffer또는 StringBuilder를 사용하는것이 좋다.

또한 

 

StringBuffer와 StringBuilder와의 차이점은 thread-safe의 유무이다.

StringBuffer가 thread-safe하다.

분류	String	StringBuffer	StringBuilder
변경	Immutable	Mutable	Mutable
동기화		Synchronized 가능 (Thread-safe)	Synchronized 불가능.

 

 

 따라서 이 햄버거 만들기 문제는 String의 replaceFirst를 StringBuilder 를 쓰며 풀 수 있는지 그리고 이것을 인지하고 있는지를 묻는 문제이다.

 

 

 

📑참고

https://hwayomingdlog.tistory.com/134

https://barbera.tistory.com/45