프로그래머스 - 택배상자

프로그래머스 - 택배상자

프로그래머스 2단계 택배상자를 풀어보겠습니다.

※ 문제 설명을 이해하신 분들은 스킵하셔도 됩니다!

문제 설명

문제 설명을 간단하게 하겠습니다.

1. 영재는 컨베이어 벨트에서 일렬로 오는 택배상자를 트럭에 싣는 일을 합니다.
   -> 컨베이어 벨트에는 1번부터 n까지의 상자가 오름차순으로 영재에게 옵니다.
   
   
2. 택배 기사님이 원하는 상자 순서대로 트럭에 싣어야 합니다.
   -> 배열 'order'는 택배 기사님이 원하는 상자 순서를 나타내는 정수 배열입니다.
   
   
3. '컨베이어 벨트'에서 온 상자가 택배 기사님이 원하는 상자가 아닐 경우, '보조 컨베이어 벨트'에 올려놓을 수 있습니다.
   
   
4. '보조 컨베이어 벨트'에서 택배 기사님이 원하는 박스를 꺼내 트럭에 싣을 수 있습니다.
   -> 단, '보조 컨베이어 벨트'에서는 영재가 가장 최근에 넣은 상자부터 꺼낼 수 있습니다. (넣은 순서와 반대)
   
   
5. 영재가 트럭에 싣은 상자의 개수를 반환합니다.

---

예시

입출력 예시 1번을 그림으로 설명하겠습니다.

---

풀이

※ 제가 푼 방법보다 더 좋은 방법으로 풀 수 있기 때문에, 참고용으로만 봐주셨으면 좋겠습니다.

1. '보조 컨베이어 벨트'에서 물건을 가져오는 방식은 '후입선출'이기 때문에, 'Stack'을 사용합니다.
   
   
2. 반복문을 이용하여 1부터 n까지의 상자를 가져옵니다.
   -> 해당 반복문이 '컨베이어 벨트'를 의미하게 되고, 반복문의 카운트 변수는 '상자 번호'를 의미합니다.
   
   
3. '상자 번호'가 택배 기사님이 원하는 상자 번호가 아니라면, '보조 컨베이어 벨트'에 상자 번호를 추가하고 반복문을 'continue'합니다.
   -> 여기서, '보조 컨베이어 벨트'에 있는 상자를 확인하지 않은 이유는 '컨베이어 벨트'에서 온 상자가 택배 기사님이 원하는 상자 번호를 만족하지 않았기 때문에, 기존에 '보조 컨베이어'에 들어가 있는 상자들도 상자 번호를 만족하지 않거나, 상자 번호를 만족하더라도 가져올 수 없기 때문입니다.
   
   
4. 상자 번호가 택배 기사님이 원하는 상자 번호라면, 'order'에서 다음 상자 번호를 가져오고 트럭에 싣은 박스의 개수를 1 증가시킵니다.
   
   
5. 반복문 안쪽에 또 다른 반복문을 이용하여 '보조 컨베이어 벨트'에서 택배 기사님이 원하는 택배 상자가 있는지 확인하여 있다면, 4번을 실행합니다.

---

코드

import java.util.Stack;

class Solution {
    public int solution(int[] order) {
        
        // 보조 컨베이어 벨트
        Stack<Integer> assistance = new Stack<>();
        // 트럭에 싣은 상자의 개수
        int answer = 0;
        // 택배 기사님이 원하는 상자 번호를 가져오기 위한 index
        int i = 0;
        
        // 반복문은 컨베이어 벨트를 의미 (가장 높은 상자 번호는 order의 length)
        for(int box = 1; box <= order.length; box++)
        {
            // 컨베이어 벨트에서 온 상자가 택배 기사님이 원하는 상자 번호가 아닌 경우
            if(order[i] != box)
            {
                // 보조 컨베이어 벨트에 상자 추가
                assistance.add(box);
                continue;
            }
            
            // 컨베이어 벨트에서 온 상자가 택배 기사님이 원하는 상자 번호일 경우
            
            // 택배 기사님이 원하는 다음 상자를 가져오고, 트럭에 싣은 상자 개수 증가
            i++;
            answer++;
            
            // 보조 컨베이어 벨트에 다음 상자가 있는지 확인
            while (assistance.size() != 0 && order[i] == assistance.peek())
            {
                // 보조 컨베이어 벨트에 만족하는 상자 번호가 있으므로 보조 컨베이어 벨트에서 빼고 트럭에 싣기
                assistance.pop();
                i++;
                answer++;
            }
        }

        return answer;
    }
}

---

테스트

• 'static class Solution'에 본인이 적은 코드를 복붙하여 정답 코드와 확인해 틀렸을 경우, 주어진 'order'와 '본인의 코드의 반환값', '정답 코드의 반환값'을 출력해주는 코드입니다.
  
  
• 원래 문제에서 주어진 order.length는 1,000,000까지지만, 1,000,000으로 잡게되면 order를 만드는 과정에서 상당한 시간이 걸리고, 해당 문제가 길이 때문에 틀리는 경우는 많이 없을거라 생각해 order.length를 10까지 줄였습니다.

import java.util.*;

public class Test {

    static class Solution
    {
        // 본인 코드 복붙!
    }

    static class Source
    {
        Random random;
        int[] order;

        Source()
        {
            random = new Random();
            order = new int[random.nextInt(10)+1];
            setOrder();
        }

        public void setOrder()
        {
            for(int i = 0; i < order.length; i++)
            {
                int box;

                do {
                    box = random.nextInt(order.length)+1;
                } while (!chkDuplicatedBox(i,box));

                order[i] = box;
            }
        }

        public boolean chkDuplicatedBox(int index, int box)
        {
            for(int i = 0; i < index; i++)
            {
                if(order[i] == box)
                    return false;
            }

            return true;
        }
    }

    static class Answer {
        public static int solution(int[] order) {
            int answer = 0;
            Stack<Integer> assistance = new Stack<>();
            int i = 0;

            for(int box = 1; box <= order.length; box++)
            {
                if(order[i] != box)
                {
                    assistance.add(box);
                    continue;
                }

                i++;
                answer++;

                while (assistance.size() != 0 && order[i] == assistance.peek())
                {
                    assistance.pop();
                    i++;
                    answer++;
                }
            }

            return answer;
        }
    }
    
    public static void main(String[] args) {
        Source source;
        Solution solution = new Solution();
        
        for (int i = 0; i < 100; i++)
        {
            source = new Source();
            int a = Answer.solution(source.order);
            int s = solution.solution(source.order);

            if(a == s) continue;

            System.out.println("주어진 order: "+Arrays.toString(source.order));
            System.out.println("정답 코드 답: "+a);
            System.out.println("내 코드 답: "+s+"\n");
        }
    }
}

#썸네일 제작 : 미리 캔버스

#예시 그림 제작 : 미리 캔버스