프로그래머스_햄버거 만들기

💻 문제 출처 : 프로그래머스_햄버거 만들기

👉 내가 작성한 답

import java.util.*;

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

        return answer;
    }
}

📌 문제 풀이 설명

• Stack로 stackHamburger와 hamburger를 선언하고, hamburger에는 1, 2, 3, 1을 넣음
  • hamburger는 해당 스택과 같은지 비교할 햄버거 형태
• 향상된 for문으로 ingredient를 순회
  • stackHamburger에 push로 i를 넣음
  • 만약 stackHamburger의 크기가 3초과이고, stackHamburger의 크기 - 4번째 인덱스부터 마지막 인덱스까지의 값을 subList로 반환했을 때, hamburger와 같으면
    • stackHamburger에 pop을 4번 실행해서 값을 4개 제거
      • 스택에 하나씩 넣고 있으니 만약 같은 경우가 생기면 가장 마지막 네 개의 값이 햄버거라 제거하고 다시 쌓아야 하기 때문
    • answer에 1 증가
• for문 종료 후 return answer
  
  

📌 주의했던 부분

• 원래는 String의 contains와 replacFirst를 이용 → 시간 초과 발생
• 그 다음엔 StringBuilder를 이용 → 시간 초과 발생
  • toString()이나 delete 메서드에서 너무 많은 시간이 소요
• String으로 변환하지 않고 푸는 방법에 대해 고민해야 했고, Stack은 List를 구현한 자료구조라 List의 메서드들이 구현되어 있다는 점을 참조
  • 💻 Stack에 관한 레퍼런스
    
    
    
    
    

👉 다른 사람이 작성한 답

class Solution {
    public int solution(int[] ingredient) {
        int[] stack = new int[ingredient.length];
        int sp = 0;
        int answer = 0;
        for (int i : ingredient) {
            stack[sp++] = i;
            if (sp >= 4 && stack[sp - 1] == 1
                && stack[sp - 2] == 3
                && stack[sp - 3] == 2
                && stack[sp - 4] == 1) {
                sp -= 4;
                answer++;
            }
        }
        return answer;
    }
}

📌 문제 풀이 설명

• int배열인 stack을 ingredient의 길이로 생성
• 인덱스를 저장할 int 변수 sp를 선언하고 0으로 초기화, int 변수 answer를 선언하고 0으로 초기화
• 향상된 for문으로 ingredient를 순회
  • stack[sp]에 i를 넣고 sp를 1 증가
    • sp++은 실행되고 +1이 되는 연산이기 때문
  • 만약 sp가 4보다 크고(stack의 길이가 4이상인 경우) sp - 1 인덱스가 1, sp - 2 인덱스가 3, sp - 3 인덱스가 2, sp - 4 인덱스가 1인 경우
    • sp에서 4를 뺌
      • stack에서 햄버거가 생기면 4번 째 전 인덱스로 다시 돌아가서 햄버거가 된 값들에 다음 값들을 덮어 쓰는 형태
    • answer를 1 증가
• for문이 종료되면 return answer