![]()
문제 링크: https://neetcode.io/problems/find-target-in-rotated-sorted-array NeetCode neetcode.io 굉장히 특이한 문제였다.O(n)으로 하면 풀기 쉽지만 O(log n)의 시간 복잡도로 문제를 풀라고 되어있다.딱 보자마자 binary search가 떠올랐는데 문제는 문제 조건이다. binary search는 알다시피 정렬된 배열에서 사용하는 sort 알고리즘이다.하지만 이 문제는 기존 정렬 배열에서 특정 횟수만큼 rotate된 배열을 input으로 두었다.binary search를 활용하여 푸는 문제들은 봤어도 이렇게 응용한 문제는 처음봐서 굉장히 신선했다.- 풀이 찾아 해매기1. 처음에는 기존 sorted array에서 rotate가 된..
n의 약수를 찾고 그 중 k번째 숫자를 리턴하는 문제이다.간단한 문제였다. class Solution: def kthFactor(self, n: int, k: int) -> int: divisor = set([]) for i in range(1, int(n**(1/2)) + 1): if (n % i == 0): divisor.add(i) divisor.add(n // i) if k > len(divisor): return -1 return sorted(list(divisor))[k-1] 시간 복잡도약수를 구할 숫자: N=> O(1/2N) 다른..
import sys from collections import deque input = sys.stdin.readline n, k = map(int, input().split()) # n: 플러그 개수 usage = list(map(int, input().split())) plug = usage[:1] # 앞 두개가 모두 같은 숫자일 수 있으므로 1개만 꽂아넣기 usage = deque(usage[1:]) result = 0 while usage: i = usage.popleft() # 이미 꽂혀있을 경우 if i in plug: continue # 플러그 자리가 남았을 경우 if len(plug) < n: plug.append(i) continue # 꽂혀있는 것들 중 뽑을 것 고르기(plug inde..
![]()
import sys from collections import deque input = sys.stdin.readline q = deque() for _ in range(int(input())): command = input().rstrip() if command == "pop": print(-1 if len(q) == 0 else q.popleft()) elif command == "size": print(len(q)) elif command == "empty": print(+(not q)) elif command == "front": print(-1 if len(q) == 0 else q[0]) elif command == "back": print(-1 if len(q) == 0 else q[-1])..
