[TIL] 9월 23일

알고리즘 문제

---

햄버거 만들기

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

프로그래머스

문제 설명

 

 

처음에 짠 코드와 문제점

import java.util.*;
class Solution {
    public int solution(int[] ingredient) {
        StringBuilder str = new StringBuilder(Arrays.toString(ingredient).replaceAll("[^0-9]",""));
        return ing(str,0);
    }

    public static int ing(StringBuilder str,int cnt){
        int idx = str.indexOf("1231");
        if(idx != -1){
            cnt++;
            str.delete(idx,idx+4);
            return ing(str,cnt);
        }
        return cnt;
    }
}

제출결과

처음에는 StringBuilder 타입의 변수를 만들면서 ingredient 배열의 있는 문자열들을 replaceAll을 이용하여 한번에 대입한 뒤에 ing 메서드를 통해 indexOf의 리턴값이 -1이 나오기전까지 계속 돌아가도록 만들었더니 위 사진처럼 시간초과가 나오며, 통과한 케이스들도 시간을보면 굉장히 오래걸리는걸 볼 수 있다.

그래서 해결법을 찾아보다가 다른 분의 코드를 참고하여 코드를 고쳤다.

public int solution(int[] ingredient) {
        int answer = 0;
        StringBuilder str = new StringBuilder();

        for(int i : ingredient){
        // for문을 돌리면서 str에 이어붙인다.
            str.append(i);
            // str의 길이가 4이상면서 subString을 이용하여 
            // str의 총 길이에서 4를 뺀 인덱스부터 추출한 문자열을 
            // equals를 이용하여 "1231"과 일치한다면
            if(str.length() > 3 && str.substring(str.length()-4,str.length()).equals("1231")){
            // 이 if문으로 들어와서 answer의 수를 증가시켜 주고 
            // lastIndexOf를 이용하여 오른쪽에서부터 "1231"의 인덱스를 구한뒤
            // delete를 이용하여 삭제해준다.
                int idx = str.lastIndexOf("1231");
                answer++;
                str.delete(idx,idx+4);
            }
        }
        return answer;
    }

 

제출 결과

시간초과도 안날뿐더러 처음 작성했던 코드보다 실행 시간도 현저히 줄은걸 볼 수 있다.

요새 알고리즘 문제를 풀면서 시간초과를 보는 상황이 점점 많아지는데 시간복잡도를 생각하면서 문제를

풀어야겠다....