o(n) 시간 안에 해결해야 되는 문제들을 잘 못 푸는데 이런 방법이 있다는 것을 알았다 여기저기 쓰일 것 같으니 잘 봐놔야지 1. 파이썬 풀이 def solution(s): answer = [] for i in range(len(s)): if len(answer)==0: answer.append(s[i]) elif answer[-1]==s[i]: answer.pop() else: answer.append(s[i]) if len(answer): return 0 else: return 1 2. javascript function solution(s) { var answer = 0; const stack=[]; for(let i=0;i
def solution(n, results): answer = 0 win={x:set() for x in range(1,n+1) } lose={x:set() for x in range(1,n+1)} for winner,loser in results: win[winner].add(loser) lose[loser].add(winner) for i in range(1,n+1): for winner in lose[i]: win[winner].update(win[i]) for loser in win[i]: lose[loser].update(lose[i]) for i in range(1,n+1): if len(lose[i])+len(win[i])==n-1: answer+=1 return answer
vis배열을 -1로 초기화시키고 bfs를 돌며 vis가 -1인 원소들을 집어넣으며 현재 길이를 vis배열에 다시 집어넣는다 from collections import deque def solution(n, edge): answer = 0 vis=[-1]*(n+1) adj=[[] for _ in range(n+1)] for e in edge: adj[e[0]].append(e[1]) adj[e[1]].append(e[0]) q=deque([[1,0]]) vis[1]=0 while q: cur,cnt=q.popleft() for a in adj[cur]: if vis[a]!=-1: continue vis[a]=cnt+1 q.append([a,vis[a]]) return vis.count(max(vis))
내림차순으로 정렬하고 가장 위치가 큰 애부터 passed배열에 넣고 단속카메라에 걸리는 애들을 모두 passed에 넣으며 현재 존재하는 카메라를 만나지 못하는 애들의 진입점을 새로운 카메라 위치로 넣어준다 포인트 : for ~ else 문법, set 문법 def solution(routes): answer = 0 routes=sorted(routes,reverse=True) print(routes) camera=[routes[0][0]] passed=[0] while len(passed)!=len(routes): for i,r in enumerate(routes): if i in passed: continue for c in camera: if r[0]
l, r은 시간 기준이며 모든 사람이 다 처리될 수 있는 최소 시간을 구해준다 mid(기준 시간)을 각 줄에서 처리할 수 있는 시간으로 나눠주면 전체 처리된 인원 수가 나오게 된다 1. 파이썬 def solution(n, times): l=min(times)*n//len(times) r=max(times)*n//len(times) answer=r while l=n: if answer>mid: answer=mid r=mid-1 else: l=mid+1 return answer 2. javascript 사람 수가 n보다 큰 경우도 시간을 갱신하는 조건이다. 가장 오래는 걸리는 시간을 right으로 해서 전체 시간을 각 시간으로 나눠준 것으로 사람 수를 계산한다. function solution(n, time..
c++에서 파이썬으로 바꾸는 중인데 c++보다 쉽다고 생각하다가도 가끔 잘 안되는 부분은 어렵다 풀이 : 바로 실행할 수 있는 일들을 우선순위큐에 넣어주고 없으면 현재 시간을 1씩 증가시킨다 import heapq def solution(jobs): answer = 0 count,last,answer=0,-1,0 heap=[] jobs.sort() time=jobs[0][0] while count