deque 방식과 lt / rt while 문 방식의 차이

Question

안녕하세요? 강사님께서 영상에서는 deque 자료형으로 바로바로 pop 하는 방식으로 코드를 짜셨는데요 강의 내용: arr.sort() arr = deque(arr) cnt = 0 while arr: if len(arr)==1: cnt += 1 break if arr[0]+arr[-1] > limit: arr.pop() cnt += 1 else: arr.popleft() arr.pop() cnt += 1 print(cnt)   그런데 비슷하다고 생각한 인덱스 이동 방식은 오답인 거 같습니다   arr.sort() lt = 0 rt = n - 1 while lt <= rt: if len(arr) == 1: cnt += 1 break sum = arr[lt] + arr[rt] if sum <= limit: cnt += 1 lt += 1 rt -= 1 else: cnt += 1 rt -= 1 # 맨 끝 가장 큰 수 pop print(cnt)   테스트 케이스는 강사님께서 댓글에 알려주신 8 149 71 72 73 74 75 76 77 78 149 로 돌려보니, 강의 내용은 5가 나오고 두번째 방식은 4가 나오네요?   근데 제가 이해가 딸려서 그런지 인덱스 이동하는 방식과 pop 방식의 차이가 잘 머리로 들어오지 않습니다..

김태원 · Answer

안녕하세요^^ 위에 입력은 4가 정답입니다. 그리고 강의내용의 코드로도 4가 나옵니다. from collections import deque p = [71, 72, 73, 74, 75, 76, 77, 78] limit = 149 n = len(p) p.sort() p=deque(p) cnt=0 while p: if len(p)==1: cnt+=1 break if p[0]+p[-1]>limit: p.pop() cnt+=1 else: p.popleft() p.pop() cnt+=1 print(cnt) 그리고 아래 인프런 인턴이 말한 lt, rt를 쓸경우 len(arr)의 값이 처음값 그대로이니 if break 문은 제거해도 됩니다. arr = [71, 72, 73, 74, 75, 76, 77, 78] limit = 149 n = len(arr) arr.sort() lt = 0 rt = n - 1 cnt = 0 while lt <= rt: sum = arr[lt] + arr[rt] if sum <= limit: cnt += 1 lt += 1 rt -= 1 else: cnt += 1 rt -= 1 # 맨 끝 가장 큰 수 pop print(cnt)

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 질문해주신 deque 방식과 인덱스 이동 방식의 차이에 대해 설명드리겠습니다. 먼저 deque 방식에서는 popleft() 와 pop() 을 통해 실제로 배열의 요소를 맨 앞이나 맨 뒤에서 제거합니다. 이는 덱(deque) 자료구조의 특성을 활용한 것으로, 양쪽 끝에서의 추가 및 삭제 작업이 아주 빠르게 이루어집니다. 따라서 배열의 크기가 실시간으로 줄어들면서 len(arr) 값이 바로바로 반영됩니다. 반면, 인덱스 이동 방식에서는 배열의 크기 자체를 변화시키지 않고, 두 개의 인덱스 포인터 lt 와 rt 를 이동시키면서 조건에 따른 연산만을 수행합니다. 이 방식으로 배열의 양 끝에서 조건을 확인하나 물리적으로 배열의 크기를 변경하지 않으므로, 배열의 길이를 따로 관리하거나 확인할 필요가 없습니다. 문제가 되는 부분은 두 번째 코드의 while 문 내 조건에서 lt <= rt 인 경우에 대한 처리입니다. 두번째 방식에서는 if len(arr) == 1: 조건이 실제로는 의미가 없으며, 이것이 while lt <= rt: 와 겹쳐져서 실제로 오답을 유발할 수 있습니다. 또한, 두 방식의 차이점 중 하나는 두번째 방식에서 cnt += 1 이라는 연산이 if 문과 else 문 양쪽에 중복되어 작성되어 있는 점입니다. if 문과 else 문의 공통된 처리를 반복문의 끝에서 단 한 번만 처리하면 더 효율적입니다. 정확한 문제 파악을 위해서는 사용하신 테스트 케이스와 limit 값, 그리고 n 의 정의가 필요합니다만, 주어진 코드를 보면 알고리즘 로직의 오류로 보입니다. 위와 같은 두 가지 방식 모두 의도하는 문제 해결에 대한 접근이 올바르지만, 구현 세부사항에서의 차이로 인해 오류가 발생한 것 같습니다. 더 구체적인 해결 방법을 알아보시려면 작성하신 코드의 전체적인 맥락과, 사용하신 변수들에 대한 정의를 다시 한번 확인하시는 것을 추천드립니다.