220909 금 Algorithms TIL

bongf·2022년 9월 9일
0

알고리즘TIL

목록 보기
151/153

프로그래머스 2019 카카오 개발자 겨울 인턴십 불량 사용자 lev3

  • 문제
  • 코드-파이썬
  • 코드-자바
  • 자바로 풀었을 때, 정규 표현식을 이용하면 훨씬 간단하게 풀 수 있다.
    • * 에 숫자나 문자가 올 수 있다고 가정하고
    • Patteren의 matches를 사용하는 String의 matches() 메소드를 사용하면 해당 패턴이 맞는지 쉽게 비교할 수 있다

리트코드 239. Sliding Window Maximum Hard

  • 문제
  • 코드-파이썬
  • 다른 블로그를 참고해서 풀었다
  • heapq를 이용한 풀이와 deque를 이용한 풀이가 있는데 heapq를 이용한 풀이가 더 느리다
  • heapq이용한 풀이
    • heapq를 이용하므로 최대값이 (max heap) 항상 배열의 맨 첫번째 요소로 오게 되어 있고, 매번 슬라이딩 윈도우 범위를 벗어나는 애는 빼주는 방식이다
    • heapq에 index를 함께 넣어 윈도우 범위를 체크해주는 것이 포인트
  • deque를 이용한 풀이
    • deque를 끝에서부터 순회하면서 지금 삽입하려는 값보다 작은 값은 다 pop해준다. ➡ queue에는 현재 삽입하려는 값보다 큰 값만 들어갈 수밖에 없다 ➡ 뒤로 삽입하므로 queue는 index순서별로 정렬 되어 있다
    • 매번 윈도우 범위를 벗어나는 애는 popleft() 해주기 때문에 queue에는 윈도우의 범위안에 있는 최대값이 저장되게 된다.
  • 참고한 블로그

프로그래머스 2021 Dev-Matching: 웹 백엔드 개발자(상반기) 헤비 유저가 소유한 장소 LEV3

profile
spring, java학습

0개의 댓글