https://school.programmers.co.kr/learn/courses/30/lessons/131704
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 지문이 못 알아 듣게 작성해서
문제 이해하느냐고 어려웠다.
프로그래머스 - 택배상자
프로그래머스 - 택배상자 문제의 풀이와 코드, 테스트용 코드를 작성했습니다.
velog.io
이 블로그때문에 문제 이해함.떙큐!
첫번째 for문 시도(실패)
보조는 stack으로 써야겠다는건 지문 읽을 때 깨달음
어떻게 해야 더 돌지?? 흠
return 2;를 원하는데 return 1; 나옴
더 돌아야 함. 도는 기준이 틀림.
문제점 분석
- orderIndex의 증가: orderIndex는 현재 컨베이어 벨트에서 꺼낼 상자를 나타냅니다. 이 인덱스는 order 배열의 인덱스와 별개로 유지되어야 하며, 벨트에서 꺼낸 상자를 기준으로 업데이트되어야 합니다.
- orderIndex 범위: orderIndex는 1부터 시작하여 order.length + 1까지 가지만, 실제로 order.length로 제한해야 합니다.
- 내부 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)
문제점 분석
- totalCount <= order.length 조건이 루프를 끝없이 돌게 만들 수 있습니다.
- currentBoxNum++가 여러 곳에서 사용되고 있어, 로직이 다소 복잡하게 보일 수 있습니다.
- 서브 컨베이어 벨트에 상자를 넣고 꺼내는 작업이 명확하지 않아 가독성이 떨어집니다.
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;
}
}
}
ㅋㅋㅋㅋ 제일 먼저 풀었다 ㅋㅋㅋㅋ기부니가 좋네요 ㅋㅋㅋㅋㅋ
