프로그래머스 택배상자

문제 설명

영재는 택배상자를 트럭에 싣는 일을 합니다. 영재가 실어야 하는 택배상자는 크기가 모두 같으며 1번 상자부터 n번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 영재에게 전달됩니다. 컨테이너 벨트는 한 방향으로만 진행이 가능해서 벨트에 놓인 순서대로(1번 상자부터) 상자를 내릴 수 있습니다. 하지만 컨테이너 벨트에 놓인 순서대로 택배상자를 내려 바로 트럭에 싣게 되면 택배 기사님이 배달하는 순서와 택배상자가 실려 있는 순서가 맞지 않아 배달에 차질이 생깁니다. 따라서 택배 기사님이 미리 알려준 순서에 맞게 영재가 택배상자를 실어야 합니다.

만약 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면 그 상자를 트럭에 실을 순서가 될 때까지 잠시 다른 곳에 보관해야 합니다. 하지만 고객의 물건을 함부로 땅에 둘 수 없어 보조 컨테이너 벨트를 추가로 설치하였습니다. 보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다). 보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못 한다면, 더 이상 상자를 싣지 않습니다.

예를 들어, 영재가 5개의 상자를 실어야 하며, 택배 기사님이 알려준 순서가 기존의 컨테이너 벨트에 네 번째, 세 번째, 첫 번째, 두 번째, 다섯 번째 놓인 택배상자 순서인 경우, 영재는 우선 첫 번째, 두 번째, 세 번째 상자를 보조 컨테이너 벨트에 보관합니다. 그 후 네 번째 상자를 트럭에 싣고 보조 컨테이너 벨트에서 세 번째 상자 빼서 트럭에싣습니다. 다음으로 첫 번째 상자를 실어야 하지만 보조 컨테이너 벨트에서는 두 번째 상자를, 기존의 컨테이너 벨트에는 다섯 번째 상자를 꺼낼 수 있기 때문에 더이상의 상자는 실을 수 없습니다. 따라서 트럭에는 2개의 상자만 실리게 됩니다.

택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order가 주어졌을 때, 영재가 몇 개의 상자를 실을 수 있는지 return 하는 solution 함수를 완성하세요.

제한 사항

• 1 ≤ order의 길이 ≤ 1,000,000
• order는 1이상 order의 길이 이하의 모든 정수가 한번씩 등장합니다.
• order[i]는 기존의 컨테이너 벨트에 order[i]번째 상자를 i+1번째로 트럭에 실어야 함을 의미합니다.

입출력 예

order	result
[4, 3, 1, 2, 5]	2
[5, 4, 3, 2, 1]	5

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 모든 상자를 보조 컨테이너 벨트에 모두 넣고, 역순으로 하나씩 빼서 트럭에 싣습니다.

풀이

• 이 문제는 보자마자 스택 문제네?라고 생각했다.
  • 메인 컨테이너 벨트는 큐(FIFO)
  • 보조 컨테이너 벨트는 스택(LIFO)
• 노가다로 해보면
  • 큐 : 4,3,1,2,5 / 스택 : null
  • 큐 : 3,1,2,5 / 스택 : 4
  • 큐 : 1,2,5 / 스택 : 4, 3
  • 큐 : 2,5 / 스택 : 4, 3
  • 큐 : 5 / 스택 : 4, 3
  • 큐 : 5 / 스택 : 4
  • 큐 : 5 / 스택 : 
  • 큐 : / 스택 : 
• ...가 아니네 ㅡ.ㅡ 무지성 코딩하면 이렇게 시간을 낭비한다... 이말이야...
  • 메인 컨테이너 밸트에서 : 1, 2, 3, 4, 5가 순서대로 나오고...
  • 택배 기사의 오더가 : 4, 3, 1, 2, 5가 있고,
  • 보조 컨테이너 밸트로 스택이 하나 있는 구조.
• 다시 노가다로 해보면
  • 1이 나오는데 오더(4,3,1,2,5)에 없으니까 스택으로
  • 메인컨테이너밸트 : 1,2,3,4,5 / 보조컨테이너밸트
  • 메인컨테이너밸트 : 2,3,4,5 / 보조컨테이너밸트 1
  • 메인컨테이너밸트 : 3,4,5 / 보조컨테이너밸트 1,2
  • 메인컨테이너밸트 : 4,5 / 보조컨테이너밸트 1,2,3
  • 메인컨테이너밸트 : 5 / 보조컨테이너밸트 1,2,3
  • 메인컨테이너밸트 : 5 / 보조컨테이너밸트 1,2
  • 메인, 보조 컨테이너 양쪽 모두 오더에 있는 숫자가 없으니까 2를 리턴
• 뭔가 이상하지? 뭐가 이상하다. 근데 뭐가 이상한지 모르겠다.
• 그냥 이대로 구현해서 만들면 되나?
  • [4, 6, 8, 1...이 있다고 치자]
    • 4가 있으면, 1,2,3을 스택에 넣고,
    • 6이 있으면 5를 스택에 넣고,
    • 8이 있으면 7을 스택에 넣고,
    • 1을 뺄려면 스택에서 빼야되지만, 스택에선 7을 뺄 수 있으니 실패
  • [1, 3, 2 ]
    • 1 빼고, 2스택에 넣고, 3 빼고, 2 스택에서 빼고
  • [3,2,1]
    • 스택에 1, 2 넣고
    • 3빼고, 2빼고, 1뺀다. 
  • [3,2,1,4, 5]
    • 스택에 1, 2 넣고
    • 3빼고, 2빼고, 1뺀다.
    • 4빼고, 5뺀다.
• 뭔가 배열 값만 읽고 알 수 있을 거라 생각했는데 모르겠다.
  • 1시간 넘게 고민
  • 2시간 넘게 고민 중
  • 그냥 짜보자!
• 무지성 코딩 가즈아!
  • 말은 쉬웠지만 아무리 짜도 에러가 ㅋㅋㅋ

def solution(order):
    main_Container_Belt = 1
    order_index = 0
    stack = []
    while True:
        print(order[order_index], main_Container_Belt, stack)
        if order[order_index] == main_Container_Belt:
            order_index += 1
            pass
        elif len(stack) > 0 and order[order_index] == stack[-1]:
            order_index += 1
            stack.pop()
        else:
            stack.append(main_Container_Belt)
        
        main_Container_Belt += 1
        if main_Container_Belt > len(order):
            break
    return order_index
    
테스트 1
입력값 〉	[4, 3, 1, 2, 5]
기댓값 〉	2
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	4 1 []
4 2 [1]
4 3 [1, 2]
4 4 [1, 2, 3]
3 5 [1, 2, 3]

테스트 2
입력값 〉	[5, 4, 3, 2, 1]
기댓값 〉	5
실행 결과 〉	실행한 결괏값 1이 기댓값 5과 다릅니다.
출력 〉	5 1 []
5 2 [1]
5 3 [1, 2]
5 4 [1, 2, 3]
5 5 [1, 2, 3, 4]

• 개념을 다시 잡아야겠다.
  • 자료구조를 2개를 만들어서
  • order랑 비교해서 벨트2에 넣었다가 뺏다가 하는거 애매하다.
  • 구냥 배열 하나로 안되나?

 오더 4,3,1,2,5 

• 벨트 1 배열 (N 만큼 만들기) : 1,2,3,4,5
  • order[0] = 4 찾기
    • 찾으면 4를 0으로 변경하고 그 위치를 stack_pos에 저장
    • 1,2,3,s[0],5
  • 다음 거 체크했는데 5가 더 크면 belt_pos 저장하고, stack_pos에서 뒤로 후진
    • 1,2,3,s[0],b[5]
    • 1,2,s[0],0,b[5] 3찾았으니 0으로 변경하고 stack_pos에 저장
  • 다음거 belt_pos에서 찾았는데 없으면...  belt_pos 저장하고, stack_pos에서 뒤로 후진
    • 1,s[2],0,0,b[5]
      • stack_pos도 1을 몾 찾았으니 종료.
  • 카운터로 변환하고, 0의 갯수를 카운트. 0이 두개, 2를 리턴.

 오더 5,4,3,2,1 

• 벨트 1 배열 (N 만큼 만들기) : 1,2,3,4,5
  • belt_pos=0. stack_pos = 0, 벨트 1 배열 : 1,2,3,4,5 (5 못 찾음)
  • belt_pos=1. stack_pos = 1, 벨트 1 배열 : 1,2,3,4,5 (5 못 찾음)
  • belt_pos=2. stack_pos = 2, 벨트 1 배열 : 1,2,3,4,5 (5 못 찾음)
  • belt_pos=3. stack_pos = 3, 벨트 1 배열 : 1,2,3,4,5 (5 못 찾음)
  • belt_pos=4. stack_pos = 4, 벨트 1 배열 : 1,2,3,4,5 (5 찾음)
  • belt_pos=4. stack_pos = 4, 벨트 1 배열 : 1,2,3,4,0 (4 못 찾음)
  • belt_pos=4. stack_pos = 3, 벨트 1 배열 : 1,2,3,4,0 (4 찾음)
  • belt_pos=4. stack_pos = 2, 벨트 1 배열 : 1,2,3,0,0 (3 못 찾음)
  • ..
  • ...

만약 스택에 넣고, 벨트에서 빼고, 스택에 넣고, 벨트에서 빼고를 반복하는 경우는?

• 오더 : 2,1,4,3,6,5
  • belt_pos=0. stack_pos = 0, 벨트 1 배열 : 1,2,3,4,5,6 (2 못 찾음)
  • belt_pos=1. stack_pos = 1, 벨트 1 배열 : 1,2,3,4,5,6 (2 찾음)
  • belt_pos=1. stack_pos = 1, 벨트 1 배열 : 1,0,3,4,5,6 <- 0으로 변경
  • belt_pos=2. stack_pos = 2, 벨트 1 배열 : 1,0,3,4,5,6 (1 못 찾음)
  • belt_pos=2. stack_pos = 1, 벨트 1 배열 : 1,0,3,4,5,6 (1 못 찾음)
  • belt_pos=2. stack_pos = 0, 벨트 1 배열 : 1,0,3,4,5,6 (1 찾음)
  • belt_pos=2. stack_pos = 0, 벨트 1 배열 : 0,0,3,4,5,6 <- 0으로 변경
  • belt_pos=2. stack_pos = 2, 벨트 1 배열 : 0,0,3,4,5,6 (4 못 찾음)
  • belt_pos=3. stack_pos = 2, 벨트 1 배열 : 0,0,3,4,5,6 (4 찾음)
  • belt_pos=3. stack_pos = 2, 벨트 1 배열 : 0,0,3,0,5,6 <- 0으로 변경

어우... 이것도 느릴 것 같다.

• 벨트 1은 그냥 for문 돌리면 될 거 같음.
• 벨트 2 스택은 무조건 있어야 할 듯?
• 택배차는 필요없고,
• 택배기사의 오더는 있어야 함.

• 아오 머리야
  • 4,3,1,2,5는 4,3만 실을 수 있고 끝.
  • 4,3,2,1,5는 5개 다 실을 수 있음.
  • 2,1,4,3,5도 다 실을 수 있고,
  • 3,2,1,5,4도 다 실을 수 있음.
  • 5,1,4,2,3은? 5만 싣기 가능.
    • B1 5
    • B2 4,3,2,1
• 가만 보면 아무리 병신 같이 해도 맨 처음 1개는 무조건 실을 수 있다.
  • 그 맨 처음의 숫자가 중요한 것 같은디?

오더	4,3,1,2,5	4,3,2,1,5	2,1,4,3,5	3,2,1,5,4	5,1,4,2,3
벨트1	4,5	4,5	2,3,4,5	3,4,5	5
벨트2	3,2,1	3,2,1	1	2,1	4,3,2,1
실을 수 있는 상자	2	5	5	5	1

•  아무리 봐도 안된다. 그냥 다시 무지성으로 ㅋㅋㅋ
  • 잘 안될 땐 변수명을 한글로 적어보면 잘 풀리더라...? (미신)
  • 으... 어거지로 하다보니까 이게 되네? 일단 테스트 케이스는 통과. 좀 다듬어야지...
  • 일요일 하루를 이걸로 날렸네? ㅋㅋㅋ

def solution(order):
    택배기사님의오더 = 0
    메인컨테이너벨트 = 1
    보조컨테이너벨트STACK = []
    while True:
        보조컨테이너벨트STACK.append(메인컨테이너벨트)
        print(메인컨테이너벨트, 보조컨테이너벨트STACK)
        while True:
            if 보조컨테이너벨트STACK[-1] == order[택배기사님의오더]:
                print("보조컨테이터벨트에 있음")
                택배기사님의오더 += 1
                보조컨테이너벨트STACK.pop()
                print(메인컨테이너벨트, 보조컨테이너벨트STACK)
            else:
                print("보조컨테이터벨트에 없음")
                break
            if len(보조컨테이너벨트STACK) == 0:
                print("브레이크")
                break
        메인컨테이너벨트 += 1
        if 메인컨테이너벨트 == len(order)+1:
            break
    return len(order) - len(보조컨테이너벨트STACK)
    
테스트 1
입력값 〉	[4, 3, 1, 2, 5]
기댓값 〉	2
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	1 [1]
보조컨테이터벨트에 없음
2 [1, 2]
보조컨테이터벨트에 없음
3 [1, 2, 3]
보조컨테이터벨트에 없음
4 [1, 2, 3, 4]
보조컨테이터벨트에 있음
4 [1, 2, 3]
보조컨테이터벨트에 있음
4 [1, 2]
보조컨테이터벨트에 없음
5 [1, 2, 5]
보조컨테이터벨트에 없음

테스트 2
입력값 〉	[5, 4, 3, 2, 1]
기댓값 〉	5
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	1 [1]
보조컨테이터벨트에 없음
2 [1, 2]
보조컨테이터벨트에 없음
3 [1, 2, 3]
보조컨테이터벨트에 없음
4 [1, 2, 3, 4]
보조컨테이터벨트에 없음
5 [1, 2, 3, 4, 5]
보조컨테이터벨트에 있음
5 [1, 2, 3, 4]
보조컨테이터벨트에 있음
5 [1, 2, 3]
보조컨테이터벨트에 있음
5 [1, 2]
보조컨테이터벨트에 있음
5 [1]
보조컨테이터벨트에 있음
5 []
브레이크

• 다듬어서 제출!
• 속도가 아쉽군요.

def solution(order):
    N = len(order)
    택배기사님의오더 = 0
    메인컨테이너벨트 = 1
    보조컨테이너벨트STACK = []
    while 메인컨테이너벨트 != N+1:
        보조컨테이너벨트STACK.append(메인컨테이너벨트)
        while len(보조컨테이너벨트STACK) != 0:
            if 보조컨테이너벨트STACK[-1] == order[택배기사님의오더]:
                택배기사님의오더 += 1
                보조컨테이너벨트STACK.pop()
            else:
                break
        메인컨테이너벨트 += 1
    return N - len(보조컨테이너벨트STACK)
    
정확성  테스트
테스트 1 〉	통과 (32.06ms, 19.2MB)
테스트 2 〉	통과 (114.48ms, 53.1MB)
테스트 3 〉	통과 (148.02ms, 66.6MB)
테스트 4 〉	통과 (102.68ms, 46.5MB)
테스트 5 〉	통과 (232.50ms, 94.6MB)
테스트 6 〉	통과 (98.65ms, 19.5MB)
테스트 7 〉	통과 (295.80ms, 46.9MB)
테스트 8 〉	통과 (28.14ms, 12.1MB)
테스트 9 〉	통과 (218.01ms, 35.3MB)
테스트 10 〉	통과 (360.32ms, 53.1MB)

• 고수의 풀이를 보니
  • while 문이 아니라 for문으로 시작해도 되네요.
  • 그리고 "N - len(보조컨테이너벨트STACK)"을 리턴할 게 아니라 "택배기사님의오더"을 리턴해도 되는군요.

def solution(order):
    List=[]
    cnt=0
    for i in range(1, len(order)+1):
        List.append(i)
        while order[cnt]==List[-1]:
            List.pop()
            cnt+=1
            if len(List)==0:
                break

    return cnt
    
정확성  테스트
테스트 1 〉	통과 (13.80ms, 19.1MB)
테스트 2 〉	통과 (61.73ms, 53MB)
테스트 3 〉	통과 (81.85ms, 66.4MB)
테스트 4 〉	통과 (54.79ms, 46.3MB)
테스트 5 〉	통과 (121.31ms, 94.5MB)
테스트 6 〉	통과 (54.43ms, 19.3MB)
테스트 7 〉	통과 (213.81ms, 46.4MB)
테스트 8 〉	통과 (11.66ms, 11.8MB)
테스트 9 〉	통과 (147.47ms, 35MB)
테스트 10 〉	통과 (255.71ms, 53.1MB)

• 첨부터 이렇게 짤 수 있었으면 얼마나 좋았을까? 진짜 깔끔하네...
  • 근데 while 문에 조건 2개 걸면 느려지나봄...

def solution(order):
    택배기사님의오더 = 0
    보조컨테이너벨트STACK = []
    for 메인컨테이너벨트 in range(1, len(order)+1):
        보조컨테이너벨트STACK.append(메인컨테이너벨트)
        while len(보조컨테이너벨트STACK) != 0 and 보조컨테이너벨트STACK[-1] == order[택배기사님의오더]:
            택배기사님의오더 += 1
            보조컨테이너벨트STACK.pop()
    return 택배기사님의오더
    
정확성  테스트
테스트 1 〉	통과 (20.91ms, 19.3MB)
테스트 2 〉	통과 (105.58ms, 53.3MB)
테스트 3 〉	통과 (129.87ms, 66.6MB)
테스트 4 〉	통과 (106.39ms, 46.4MB)
테스트 5 〉	통과 (182.48ms, 94.7MB)
테스트 6 〉	통과 (66.75ms, 19.5MB)
테스트 7 〉	통과 (264.94ms, 46.9MB)
테스트 8 〉	통과 (14.32ms, 12.1MB)
테스트 9 〉	통과 (189.78ms, 35.4MB)
테스트 10 〉	통과 (317.26ms, 53.2MB)

• 진짜네. while 문제 조건 여러 개 달면 느려지네...? 신기한거 알았다.

def solution(order):
    택배기사님의오더 = 0
    보조컨테이너벨트STACK = []
    for 메인컨테이너벨트 in range(1, len(order)+1):
        보조컨테이너벨트STACK.append(메인컨테이너벨트)
        while 보조컨테이너벨트STACK[-1] == order[택배기사님의오더]:
            택배기사님의오더 += 1
            보조컨테이너벨트STACK.pop()
            if len(보조컨테이너벨트STACK) == 0:
                break
    return 택배기사님의오더

정확성  테스트
테스트 1 〉	통과 (16.18ms, 19.3MB)
테스트 2 〉	통과 (61.84ms, 52.9MB)
테스트 3 〉	통과 (89.09ms, 66.6MB)
테스트 4 〉	통과 (54.29ms, 46.3MB)
테스트 5 〉	통과 (122.20ms, 94.7MB)
테스트 6 〉	통과 (55.00ms, 19.3MB)
테스트 7 〉	통과 (218.76ms, 46.8MB)
테스트 8 〉	통과 (11.55ms, 12MB)
테스트 9 〉	통과 (169.14ms, 35.3MB)
테스트 10 〉	통과 (252.35ms, 53.2MB)