본문 바로가기

전체 글

 (107)
[백준] 20922 겹치는 건 싫어 / 구현 / Python 실1 https://www.acmicpc.net/problem/20922 보자마자 필이 짜르르 옴이건 슬라이딩 윈도우다 윈도우 범위 조절을 위해 start, end 두개 사용범위 내 숫자 빈도는 딕셔너리 사용 현재 윈도우 범위에서 특정 숫자가 K개를 초과하면start를 움직여서 k개가 되도록 while문을 돌면서 이동 윈도우 최장 길이는end-start+1로 업데이트 from collections import defaultdictn,k = map(int,input().split())a = list(map(int,input().split()))count = defaultdict(int)start=0max_l = 0for end in range(n): count[a[end]]+=1 while count..
[백준] 21921 블로그 / 구현 / Python 실3 https://www.acmicpc.net/problem/21921 슬라이딩 윈도우로 푸는 문제! 처음에는 for문 돌면서 배열에 s = a[i:i+k] 값을 저장하고, max 값을 업데이트 하는 방식으로 구현했는ㄴ데이렇게 하면 O(n*x)가 되어 시간초과가 났다 그래서 슬라이딩 윈도우를 사용하면서 전역변수에서 현재 a[i]값을 더하고 이전 a[i-x] 원소 값을 빼서현재 sum이 x개의 원소 합으로 유지되도록 구현한다이렇게 하면 slicing으로 탐색해서 끊지 않아도 된다 만약 현재 sum이 이전 max값보다 크다면count값을 1로 리셋하고max값을 현재 sum으로 대체한다 만약 현재 sum과 max값이 같다면 count을 1 증가한다 max값이 0보다 크면 max값과 count값을 출력하고그 외에는..
[백준] 9935 문자열 폭발 / 구현 / Python 골4 https://www.acmicpc.net/problem/9935 처음에 파이썬 replace로 비벼보려고 했는데, 칼같이 시간초과 나온대서 포기;; 다른 블로그 아이디어를 참고했다 stack에 문자열 요소를 하나씩 집어넣으면서그때마다 stack의 가장 최근에 집어넣어진 요소를 기준으로 폭발문자열 길이만큼 탐색했을 때그 문자열이 폭발문자열과 일치하면 stack에서 폭발문자열 길이만큼 pop하며 지워준다 stack이 비어있으면 FRULA를 출력하고그렇지 않으면 stack을 join을 써서 문자열로 만들어 출력한다 s = input()bomb = input()b = len(bomb)stack=[]for el in s: stack.append(el) if ''.join(stack[-b:])==bom..

티스토리툴바