[Programmers] 택배상자 / ⭕

프로그래머스

 

1. 제출 코드 (23분 20초 / 스택)

import java.util.*;

class Solution {
    public int solution(int[] order) {
        int answer = 0;
        ArrayDeque<Integer> dq = new ArrayDeque<>();
        int num = 1;
        int idx = 0;
        while(idx < order.length) {
            if(num < order[idx]) {
                dq.add(num++);
            } else if(num == order[idx]) {
                answer++;
                idx++;
                num++;
            } else {
                if(!dq.isEmpty() && dq.pollLast() == order[idx]) {
                    answer++;
                    idx++;
                } else {
                    break;
                }
            }
        }
        
        return answer;
    }
}

 

2. 구현 로직

• order를 앞에서부터 하나씩 탐색
  • 만약, order[idx] > num이라면 스택에 삽입 /  num 증가
  • 만약, order[idx] == num 이라면 idx, num answer +1 증가
  • 만약, order[idx] < num이라면 스택 peek == order[idx] 인지 확인하고 같다면 answer, idx++
    • 아니면 반복문 종료 및 정답 추출

 

3. 유의할 점

• order[idx] == num 일 경우에도 num을 증가시켜야 한다.