택배상자

 

 

---

 

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

프로그래머스

 

문제 지문이 못 알아 듣게 작성해서

문제 이해하느냐고 어려웠다.

https://velog.io/@biny22/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%83%9D%EB%B0%B0%EC%83%81%EC%9E%90

프로그래머스 - 택배상자

이 블로그때문에 문제 이해함.떙큐!

주 컨베이어 벨트의 숫자는 1부터 점점 커지고, order번호는 고정된 값

 

주 컨테이너에 끝에 도달해도, stack에서 계속 검색해야함

---

첫번째 for문 시도(실패)

보조는 stack으로 써야겠다는건 지문 읽을 때 깨달음

어떻게 해야 더 돌지?? 흠

return 2;를 원하는데 return 1; 나옴

더 돌아야 함. 도는 기준이 틀림.

문제점 분석

1. orderIndex의 증가: orderIndex는 현재 컨베이어 벨트에서 꺼낼 상자를 나타냅니다. 이 인덱스는 order 배열의 인덱스와 별개로 유지되어야 하며, 벨트에서 꺼낸 상자를 기준으로 업데이트되어야 합니다.
2. orderIndex 범위: orderIndex는 1부터 시작하여 order.length + 1까지 가지만, 실제로 order.length로 제한해야 합니다.
3. 내부 for문: 내부 for문은 불필요하며, order 배열을 순회할 필요가 없습니다.

import java.util.Stack;

public class 택배상자 {

	public static void main(String[] args) {
		Solution solution = new Solution();
		int result = solution.solution(new int[] {4, 3, 1, 2, 5});
		System.out.println(result);// 2

	}

	static class Solution {
		public int solution(int[] order) {
			int totalCount = 0;
			Stack<Integer> subConveyBelt = new Stack<>();
			int currentBoxNum = 1;


			for (int i = 0; i < order.length; i++) { // 여기가 틀렸음.. 더 돌아야함

				if (subConveyBelt.empty()) {
					if (currentBoxNum == order[i]) {
						totalCount++;
						currentBoxNum++;
					} else {
						subConveyBelt.push(currentBoxNum);
						currentBoxNum++;
					}
				} else {
					boolean check1 = false;
					boolean check2 = false;

					if (subConveyBelt.peek() == currentBoxNum) {
						subConveyBelt.pop();
						totalCount++;
						currentBoxNum++;
						check1 = true;
					}

					if (currentBoxNum == order[i]) {
						totalCount++;
						currentBoxNum++;
						check2 = true;
					}

					if (check1 == false && check2 == false) {
						subConveyBelt.push(currentBoxNum);
						currentBoxNum++;
					}

				}


			}

			return totalCount;
		}
	}
}

 

 

 

---

두번째 while문 시도

while문으로 변경해서 도는 조건을 수정

그러나 메모리 초과..

1 ≤ order의 길이 ≤ 1,000,000

이중 for문이라 O(N^2)

 

문제점 분석

1. totalCount <= order.length 조건이 루프를 끝없이 돌게 만들 수 있습니다.
2. currentBoxNum++가 여러 곳에서 사용되고 있어, 로직이 다소 복잡하게 보일 수 있습니다.
3. 서브 컨베이어 벨트에 상자를 넣고 꺼내는 작업이 명확하지 않아 가독성이 떨어집니다.

메모리 초과

import java.util.Stack;

public class 택배상자2 {

	public static void main(String[] args) {
		Solution solution = new Solution();
		int result = solution.solution(new int[] {5, 4, 3, 2, 1});
		System.out.println(result);// 5

	}

	static class Solution {
		public int solution(int[] order) {
			int totalCount = 0;
			Stack<Integer> subConveyBelt = new Stack<>();
			int currentBoxNum = 1;
			// while문 O, for문 X
			// currentBoxNum은 조건에 따라 증가한다


			// 택배 번호 상자는 자신과 같은 값이 나올때까지 기다린다
			for (int box : order) {
				// currentBoxNum 마지막 숫자 == 배열의 길이와 일치하면(틀림)
				// 연속에서 stack에서 꺼낼 수 없음

				// totalCount == 배열의 길이와 일치하면(맞음)
				// 계속해서 stack 뒤질 수 있음

				// 모든게 끝나는 조건: 주 컨베이터 벨트가 끝 && 서브 컨테이너 끝
				// 서브를 마지막까지 더 돌려아함
				while (totalCount <= order.length) {
					boolean check = false;
					boolean check2 = false;

					// 먼저 주 컨베이터 벨트 체크
					if (currentBoxNum == box) {
						totalCount++;
						currentBoxNum++;
						check = true;
						break;
					}

					// 서브 컨베이터 벨트 체크
					if (!subConveyBelt.empty() && subConveyBelt.peek() == box) {
						totalCount++;
						currentBoxNum++;
						subConveyBelt.pop();
						check2 = true;
						break;
					}

					// 둘 다 아니면 서브 컨베이터 벨트에 넣기
					if (!check && !check2) {
						subConveyBelt.push(currentBoxNum);
						currentBoxNum++;
					}

				}// while end
			}// for end

			return totalCount;

		}// func end
	}
}

 

 

---

해결 코드

 

import java.util.Stack;

public class 택배상자2 {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int result = solution.solution(new int[] {5, 4, 3, 2, 1});
        System.out.println(result); // 5
    }

    static class Solution {
        public int solution(int[] order) {
            int totalCount = 0;
            Stack<Integer> subConveyBelt = new Stack<>();
            int currentBoxNum = 1;

            for (int box : order) {
                // 메인 컨베이어 벨트에서 목표 상자를 찾을 때까지 상자를 서브 벨트로 보낸다.
                while (currentBoxNum <= order.length && currentBoxNum != box && (subConveyBelt.isEmpty() || subConveyBelt.peek() != box)) {
                    subConveyBelt.push(currentBoxNum++);
                }

                // 메인 컨베이어 벨트에 목표 상자가 있는 경우
                if (currentBoxNum == box) {
                    totalCount++;
                    currentBoxNum++;
                }
                // 서브 컨베이어 벨트의 맨 위에 목표 상자가 있는 경우
                else if (!subConveyBelt.isEmpty() && subConveyBelt.peek() == box) {
                    subConveyBelt.pop();
                    totalCount++;
                }
                // 더 이상 작업을 진행할 수 없는 경우
                else {
                    break;
                }
            }

            return totalCount;
        }
    }
}

 

 

---

ㅋㅋㅋㅋ 제일 먼저 풀었다 ㅋㅋㅋㅋ기부니가 좋네요 ㅋㅋㅋㅋㅋ

 

---