📌 첫 번째 풀이 (시간 초과) 우선 제일 먼저 생각난 것은 for문을 돌리면서 자신을 제외한 모든 수를 곱한 것을 새로운 arr배열에 넣는 것이었다. 하지만 이를 위해서는 필수적으로 이중 for문이 들어가게 되고 문제의 조건인 시간 복잡도 O(N)을 만족할 수 없게 되어 시간 초과가 나오게 되었다. class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: arr = [] for i in range(len(nums)): num = 1 for j in range(len(nums)): if i == j: continue else: num *= nums[j] arr.append(num) return arr 📌 두 번째 풀이 그렇다면 ..

📌 투 포인터를 활용한 풀이 가장 일반적인 투 포인터 문제이다. 투 포인터는 주로 정렬된 대상을 대상으로 한다. (파이썬 알고리즘 인터뷰 - 박상길 에 의하면) 우선 고유 번호들을 정렬한 뒤 투 포인터로 풀기 위해 left = 0 right = len(nums) - 1 로 둔다. 그 다음 left와 right의 합이 원하는 결과(여기서는 m) 보다 작으면 left를 +1 크다면 right을 -1 해주면서 만족하는 값을 찾아 가운데로 조여 나간다. 그러다가 원하는 결과가 나오면 count를 +1 해주고 left와 right을 각각 +1, -1 해준다.(결과를 하나 찾았으므로 한 칸씩 조인다고 생각하면 편하다.) 풀이 코드 import sys input = sys.stdin.readline n = int(i..

📌 풀이 1 : 브루트 포스 가장 먼저 생각 난 풀이는 브루트 포스이다. 하지만 세 수를 비교하는 문제이기 때문에 for문을 3번이나 돌리게 돼서 시간 복잡도는 O(N^3)이 된다. num.length의 범위가 3000까지 이므로 이 시간 복잡도로는 시간 초과가 나오게 된다. 그래도 풀이과정을 소개하자면 처음 i 일 때는 len(nums)-2까지 다음 j 일 때는 i+1부터 len(nums)-1까지 마지막 k 일 때는 j+1부터 len(nums)까지 for문을 돌려가면서 nums [i]+nums [j]+nums [k] == 0 가 된다면 arr 리스트에 [nums [i], nums [j], nums [k]] 를 append 해주는 것이다. 이때 앞뒤로 같은 값이 있을 경우를 처리해주기 위해 처음에 num..

📌 투 포인터를 활용한 풀이 이 문제는 투 포인터를 생각해서 풀 수 있다. 우선 투포인터 방식답게 양쪽에 left와 right로 포인터를 정해준다. 이때 이 두 포인터는 index가 되어야 하므로 left는 0 right는 가로길이 -1 즉 블록 리스트의 길이 -1 여기서 핵심은 양쪽 포인터가 전체 중 가장 높은 블록을 향해 나아가야 한다는 점이다. 오른쪽이 더 크다면 left += 1 을 해줘서 왼쪽 포인터를 오른쪽으로 왼쪽이 더 크다면 right -= 1을 해줘서 오른쪽 포인터를 왼쪽으로 이를 공식으로 나타내면 다음과 같다. if left_max

📌 첫 번째 풀이 : 리스트의 pop을 이용한 풀이 # 리스트의 pop을 이용한 풀이 n = int(input()) arr = [] for i in range(n): arr.append(int(input())) while 0 in arr: for i in range(len(arr)): if arr[i] == 0: arr.pop(i) arr.pop(i-1) break print(sum(arr)) 첫 번째로 생각한 방법은 미리 리스트를 받아 놓고 처음부터 순차적으로 탐색한 뒤 0을 발견하면 그 자리와 그 앞자리를 pop 해줌으로써 리스트의 길이를 줄여나가는 방법이다. deque를 쓰고 싶었으나 deque에는 특정 인덱스를 pop 할 수 없어기에 일반 리스트 pop을 사용했다. 통과는 하였으나 시간이 3400..