[Study] 11월 14일 Algorithm Study

목표

---

• 오늘은 알고리즘 스터디와 개인적으로 문제를 풀어보면서 나의 알고리즘 풀이 실력이 많이 모자라다는 것을 느꼈다. 하지만, 알고리즘 문제는 풀면 풀수록 실력이 늘어난다고 하기 때문에 꾸준히, 성실하게 풀다 보면 성장해 있을 것이라고 생각한다. 오늘 푼 문제를 회고하면서 관련 실수를 다시 하지 말자.

 

Programmers Lv. 1 햄버거

---

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

프로그래머스

 

풀이 개요

• 해당 문제는 1(빵), 2(야채), 3(고기)로 분류되는 정보를 담고있는 ingredient 배열을 이용해 1,2,3,1가 연속으로 쌓여있다면 완성된 햄버거로 판단하고 재료목록에서 제거한 후 계속해서 1,2,3,1의 시퀀스 갯수의 총합을 문제이다.
• 숫자 시퀀스를 제거한다고 하더라도 먼저 쌓여있던 재료들은 유지되고 그 위로 다시 새로운 재료들이 쌓이기 때문에 그 구조가 Stack과 매우 유사하다고 생각했다.

 

발견한 문제

• Stack을 사용해야겠다는 생각을 계속 이어갔어야 했다. 코드를 작성하기 전 전체적인 로직을 그려봤는데 현재 Stack의 가장 위에있는 원수부터 아래로 3개까지의 원소를 기억하거나, Stack의 크기가 4가 넘을때마다 pop()을 4번 해서 원소를 빼내는 로직을 구현해야 했다. 매우 번거롭고 중복 코드를 여러줄 작성하는것이 매우 보기 싫은 코드가 작성될 것 같다는 생각을 했다.
• 그래서 다른 방법을 생각해봤는데, 내가 생각한 방법은 ingredient를 string으로 변환해 타겟인 "1231"을 ""으로 계속 replace하고, 더 이상 바꿀 타겟이 없다면 로직을 종료하는 것이었다. Stack을 이용하는 것보다 코드가 깔끔해보이고 효율적이라고 생각해서 Stack을 이용하지 않았다.
• 문제를 푼 결과 엄청난 시간초과가 발생했다. 이후, 다시 Stack을 이용해 풀었는데 손쉽게 다 맞았다. 코드가 좀 보기싫더라도 성능적인 측면에서 이전 알고리즘보다 효율적이었던 것이다.

 

배운점

• 지금까지 깔끔한 코드와 효율적인 코드를 동일하게 생각했던 것이 매우 한심하게 느껴졌다. 주관적으로 깔끔한 코드가 항상 효율적인결과를 만들어 내지는 않는다는 사실을 깨달을 수 있었다. 깔끔한 코드 작성은 물론 매우 중요하지만 뭐니뭐니해도 성능이 최고인 것 같다. 앞으로는 깔끔하되 성능을 고려한 코드를 작성하려고 노력해야겠다.

 

작성 코드

import java.util.*;

class Solution {
    public int solution(int[] ingredient) {
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<ingredient.length; i++) {
            sb.append(ingredient[i]);
        }
        
        int answer = 0;
        String sequence = sb.toString();
        while(true) {
            String newSequence = sequence.replaceFirst("1231", "");
            if(newSequence.length() != sequence.length()) {
                sequence = newSequence;
                answer++;
            }
            else break;
        }
        
        return answer;
    }
}

• 사실 원래 StringBuilder를 쓰지 않고 ingredient[]의 원소를 String 변수에 '+='로 직접 추가했는데, 이 과정이 생각보다 시간을 잡아먹는다는 것을 깨닫고 신나서 StringBuilder를 이용해서 다시 풀어봤는데 몇개 더 풀긴 했지만 역시나 시간 초과가 발생했다. sequence를 replaceFirst()를 통해 타겟 넘버가 없어질때까지 조작하는 과정에서 시간을 많이 잡아먹는 것 같다. 앞으로 String 라이브러리도 신중하게 써야겠다.

 

수정 코드

import java.util.*;

class Solution {
    public int solution(int[] ingredient) {
        int answer = 0;
        
        Stack<Integer> stack = new Stack<>();
        for(int i : ingredient) {
            stack.push(i);
            int size = stack.size();
            if(size >= 4 && i == 1) {
                if(stack.get(size-1) == 1 && stack.get(size-2) == 3 && stack.get(size-3) == 2 && stack.get(size-4) == 1) {
                    for(int j=0; j<4; j++) stack.pop();
                    answer++;
                }
            }
        }
        
        return answer;
    }
}

• 다시보니 이전 코드가 Stack에 비해 막 깔끔해보이지도 않는다. 아 그리고 팀원 한 분이 size에 관한 피드백해주셨는데 라이브러리 내부적으로 최적화를 해주지만 size()를 한 번 호출할때마다 O(n)의 시간이 발생한다는 사실을 뇌 깊은곳에 파뭍어 놓고 있었다. if안에 모두 stack.size()로 적어뒀었는데 창피해서 바로 바꿨다. 위 코드는 size를 한 번만 호출하도록 바꾼 코드이다.