PS 2

[프로그래머스]Lv.4 가사 검색(Python)

문제https://school.programmers.co.kr/learn/courses/30/lessons/60060풀이굉장히 복잡한 문제였다.문제의 설명대로 구현하면 예제 케이스는 통과할 수 있다.하지만, 각 데이터의 범위로 인해서 시간초과가 발생할 수 있다.쿼리마다 글자수가 동일한지 여부를 체크한다던가, 접미사에 붙은 와일드 카드를 비교한다던가, 조건에 맞는 단어마다 1씩 카운팅 한다던가...이런식으로 코드를 작성하면 O(n^2)의 시간복잡도가 등장하므로 시간초과가 발생한다. 1. 글자수별로 분류한다. 각 쿼리마다 단어들의 글자수가 맞는지 체크하지 말고, 단어의 길이마다 단어를 분류하면 쿼리마다 길이가 맞는 단어만 비교할 수 있다. 2. 접미사를 전부 접두사처럼 접미사도 접두사처럼 검증해서 로직을 단..

PS 2026.08.24

[프로그래머스]Lv.3 파괴되지 않은 건물 (Python)

문제https://school.programmers.co.kr/learn/courses/30/lessons/92344풀이2차원 배열을 순회하는 단순 구현으로도 쉽게 정답을 만들어낼 수 있다. 단, skill이 최악의 경우 250,000개가 전달되므로 이런 경우 단순한 시간복잡도 계산으로 시간초과가 발생할 수 있다는 것을 알 수 있다그렇기때문에 수학적 기믹이 필요하다. 누적합을 이용해보자.공격 또는 회복의 시작점과 끝점을 +n, -n으로 기록하게 되면 해당 범위에 모든 원소는 누적합 계산을 통해서 n만큼 적용시킬 수 있다.skill마다 공격과 회복 유형에 맞게끔 시작과 끝을 기록하고 나서 누적합을 기록한다면 1차원인 상태에서는 올바르게 적용시킬 수 있다. 그러나, 2차원 배열에서는 세로축도 존재하므로 고려..

PS 2026.08.11