백준 15961 - 회전초밥 - swift

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

15961번: 회전 초밥

 

 

 

 

우선 N이 최대 3백만이면서 시간제한이 1초이다. 

백준에서 Swift로 풀경우 종종 입력값이 백만개를 넘는경우가 종종있는데, 

더불어 시간제한이 1초라면 시간초과나기 십상이다. 

 

그러므로, 라이노님의 버퍼를 이용한 빠른 readLine을 활용해야한다. 

 

https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88 

ps할 때 입력을 한꺼번에 받기 위한 유틸리티 클래스. fread의 swift 버전.

 

 

그렇다고 빠르게 입력받는다고해서 만능은 아니라는점을 알아야한다.  ( 그래도 많은 문제가 풀리긴한다. ) 

 

그다음 접근법은 

투포인터를 응용한다. 

 

회전초밥이므로, 원을 그리는 형태가 되는데, 이를 표현하기위해서는

간단하게 하나의배열을 기존배열끝에 이어붙인 형태로 만들어줬다.

 

그럼이제 원을 고려할필요가없어졌고, 

새롭게 만들어진 배열을 토대로 하나씩 탐색해나가면된다. 즉 O(N)으로 풀 수 있게된다. 

배열을 탐색하는 원소를 right로 정의하고, 연속된 k개를 나타내기위해 , left변수를 따로 만들어둔다. 

 

그리고 각 초밥들을 확인하기위한 check배열을 만들어둔다. 

초밥들은 최대 3천개이므로, 간단하게 Int타입배열로 만들어두어도 충분히 가볍다. 

그럼이제, right-left+1 가 K보다 큰경우에는 연속된K개를 벗어난경우니, left를 증가시켜준다. 

그리고check배열들을 카운팅시킴으로써 최대초밥의 갯수를 구해낸다. 

 

import Foundation
// 라이노님 빠른 입력 FileIO 클래스
class  FileIO {
    private var buffer:[UInt8]
    private var index: Int

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
        index = 0
    }

    @inline(__always)  private func read() -> UInt8 {
        defer { index += 1 }

        return buffer.withUnsafeBufferPointer { $0[index] }
    }

    @inline(__always)  func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10 || now == 32 { // 공백과 줄바꿈 무시
            now = read()
        }
        
        if now == 45{ // 음수 처리
            isPositive.toggle()
            now = read()
        }
        
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always)  func readString() -> String {
        var str = ""
        var now = read()

        while now == 10
            || now == 32 { now = read() } // 공백과 줄바꿈 무시

        while now != 10
            && now != 32 && now != 0 {
                str += String(bytes: [now], encoding: .ascii)!
                now = read()
        }

        return str
    }
}

let file = FileIO()
let inp = [file.readInt(), file.readInt(), file.readInt(), file.readInt()]

let N = inp[0], D = inp[1], K = inp[2], C = inp[3]
var list = [Int]()
for _ in 0..<N {
    list.append(file.readInt())
}

list.append(contentsOf: list[0..<N-1])
var check = Array(repeating: 0, count: 3001)
var l = 0
var count = 0
var answer = 0
for r in 0..<2*N-K {
    check[list[r]] += 1
    if check[list[r]] == 1 {
        count += 1
    }
    if r-l+1>K {
        check[list[l]] -= 1
        if check[list[l]] == 0 {
            count -= 1
        }
        l += 1
    }
    if check[C] == 0 {
        answer = max(answer, count+1)
    } else {
        answer = max(answer, count)
    }
}

print(answer)