#level2 #프로그래머 #Python #스택 #큐문제
이번에도 스택/큐 문제를 가져왔다.입출력 순서를 묻는 문제는 스택/큐이다. 내가 정한 공식인지 확인해볼게.
처음 문제를 봤을 때 문제의 의도를 잘 파악하지 못하는 사람은 나뿐이었는지…? 두 가지 정도의 블로그 해설을 확인하고 문제 의도가 어떤 것인지 파악했다. 과정
배열의 인덱스를 고려하고 글로는 1,2,3,4,5초로 제시했지만 필자는 0,1,2,3,4초로 설명한다.step1.0초 때 1\의 돈은 나열 요소에 하나씩 훑어볼 때 떨어지는 것이 하나도 없다. 그러므로 4번 비교하면 결과는 4초이다.[4]step2.1초 시점 2\의 돈은 나열 요소에 끝까지 하나씩 훑어볼 때 같은처럼 떨어지는 것이 아니므로 결과는 3초이다.[4,3]step3.2초 시점 3\의 돈은 next원소와 비교했을 때 떨어져서 1초 떨어지고 그 이후에는 빠지지 않아서 결과는 1초이다.[4,3,1]step4.3초 시점 2\의 돈은 나열 요소에 끝까지 하나씩 훑어보다가 떨어지는 것이 없어서 결과는 1초이다. (끝까지 비교한 count개수)[4,3,1,1]step5.4초 시점 마지막 부분은 더 이상 떨어지지 않고, 다음의 원소와 비교할 필요도 없으니 0을 append하면 좋다.[4,3,1,1,0]얼핏 brute force에서 이중 loop주변면서 비교하는 코드를 구성하면 좋을 것 같지만, 스택과 큐 사인이 카테고리이다.어떻게 해야 좋을지 생각하고 보고, 저는 시간에 대한 부분을 stack에 넣어 문제를 풀려고 했다. (무리한 느낌이 있지만)step1. 하늘의 stack에 ‘0’을 넣는다. 이로써 prices를 돌며 next prices가 더 낮은 경우는 count가 추가된다.prices[0]은[2,3,2,3] 낮을 것이 없으니 count가 4회 누를 것이다.step1.[4]이 포함된 stack에[0]를 하나 더 추가한다. 이는 prices를 돌며 똑같이 count을 넣어 줄 겁니다. prices[1]은[3,2,3]보다 낮은 것이 없으니 count이 3이다.이렇게 진행한다면 결과적으로 return배열이 완성될 것이다. 이 알고리즘을 그대로 적용하고 보지 않나!!!코드
배열의 인덱스를 고려해서 문장에서는 1, 2, 3, 4, 5초로 제시했는데 필자는 0, 1, 2, 3, 4초라고 설명한다.step 1.0초 시점 1의 돈은 리스트 요소를 하나씩 훑어볼 때 떨어지는 것이 하나도 없다. 따라서 네 번 비교해 보면 결과는 4초일 것이다.[4]step 2.1초 시점 2의 돈은 리스트 요소를 끝까지 하나씩 훑어볼 때 똑같이 떨어지지 않으며 따라서 결과는 3초일 것이다.[4,3] step 3.2초 시점 3의 돈은 next 원소와 비교했을 때 떨어지기 때문에 1초간 떨어지고 그 이후에는 떨어지지 않으므로 결과는 1초일 것이다.[4,3,1] step 4.3초 시점 2의 돈은 리스트 요소를 끝까지 하나씩 훑어볼 때 떨어지는 것이 없기 때문에 결과는 1초일 것이다. (끝까지 비교할 count 개수) [4,3,1,1] step 5.4초 시점 마지막 부분은 더 이상 떨어지지 않으며 다음 원소와 비교할 필요도 없으므로 0을 append 해주면 된다.[4,3,1,1,0] 얼핏 보면 brute force로 이중 loop 돌면서 비교하는 코드를 구성하면 될 것 같지만 스택과 큐가 카테고리다.어떻게 해야 할지 생각해봤고, 나는 시간에 대한 부분을 stack에 넣어서 문제를 풀려고 했어. (무리한 느낌이 있지만) step1. 빈 stack에 ‘0’을 넣는다. 이에 따라 prices를 돌며 next prices가 더 낮을 경우 count가 추가된다.prices[0]는 [2,3,2,3] 낮아질 수 없기 때문에 count가 4번 눌릴 것이다.step1.[4]가 포함된 stack에 [0]을 하나 더 추가한다. 이것은 prices를 돌아다니면서 똑같이 count를 더해줄 것입니다. prices[1]는 [3,2,3]보다 낮은 것이 없으므로 count가 3이 될 것이다.이렇게 계속 진행한다면 결과적으로 return 배열이 완성될 것이다. 이 알고리즘 그대로 적용해보자…코드
def solution(resolution): i の場合 time_stack=[]: time_stack.stack(0) count=0 in range(i+1, len(resolution)): price[i]>price[j]: break time_stack[-1]=count return time_stack
채점결과 정확성 : 66.7 효율성 : 33.3 합계 : 100.0/100.0time_stack이라는 시간을 넣는 stack을 담고 prices의 길이만큼 forloop을 돌 때마다 추가해주는 다이는 다음 원소를 비교하면서 count를 누적시키고 만약 가격이 떨어지면 바로 break하여 time_stack 꼭대기에 count 값을 할당한다.loop 반복, append(0)를 넣고 count 세고 떨어지면 count값 stack 위에 저장 아마 정석해가 아닐까?? 좋겠네요.좀 받을 것 같아 🙂 정리
2단계의 문제, 무서워하지 않도록^^
