[파이썬, 스위프트][백준 13422][💛 골드 4] (투포인터, 슬라이딩 윈도우)

🧞‍♂️ 난이도

💛 골드 4

🧞‍♂️ 문제

포도주 시식

https://www.acmicpc.net/problem/13422

🧞‍♂️ 유형

투포인터, 슬라이딩 윈도우

🧞‍♂️ 내 풀이

이 문제는 슬라이딩 윈도우로 풀면 되는 문제이다. left, right 으로 슬라이딩윈도우를 한칸씩 이동시키면서

왼쪽으로 윈도우에서 빠지는 숫자는 sum 에서 빼주고 오른쪽으로 새로 들어오는 숫자는 더해주면서 K 보다 작을때는 정답에 1을 추가해주면 된다.

이렇게 해서 한바퀴만 돌리면 되기 때문에 O(N) 으로 가능하다.

원형으로 연결되어있으니까 % 연산자 이용해서 right를 계산해주면 되고,

이 문제 아무 생각없이 풀다가 채점 마지막 쯤에 실패를 하는데 꼭 챙겨야되는 예외케이스가 있다

4 4 5
1 1 1 1

이런 테스트케이스에서는 정답이 1인데 그냥 풀어버리면 4가 나오게될거다.

즉, N이랑 M 이 같을때에 대한 예외처리를 해줘야한다.

---

🧞‍♂️ 파이썬 풀이

import sys
input = sys.stdin.readline

def solution(houses, N, M, K):
    currentSum = sum(houses[0:M])
    left = 1
    right = M
    answer = 1 if currentSum < K else 0
    # 예외처리
    if N == M:
        return answer

    while left < N:
        currentSum -= houses[left - 1]
        currentSum += houses[right % N]
        if currentSum < K:
            answer += 1
        left += 1
        right += 1
    return answer

T = int(input())
for _ in range(T):
    N, M, K = map(int, input().split())
    houses = list(map(int, input().split()))
    print(solution(houses, N, M, K))

🧞‍♂️ 스위프트 풀이

import Foundation

func solution(houses: [Int], N: Int, M: Int, K: Int) -> Int {
    var currentSum = houses[0..<M].reduce(0, +)
    var answer = currentSum < K ? 1 : 0
    // 예외처리
    if N == M {
        return answer
    }
    var left = 1
    var right = M
    
    while left < N {
        currentSum -= houses[left - 1]
        currentSum += houses[right % N]
        if currentSum < K {
            answer += 1
        }
        left += 1
        right += 1
    }
    
    return answer
}

let T = Int(readLine()!)!

for _ in 0..<T {
    let NMK = readLine()!.split(separator: " ").compactMap { Int($0) }
    let N = NMK[0]
    let M = NMK[1]
    let K = NMK[2]
    let houses = readLine()!.split(separator: " ").compactMap { Int($0) }
    
    print(solution(houses: houses, N: N, M: M, K: K))
}

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기