
3745번: 오름세
입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다.
www.acmicpc.net
간단한 문제 요약
n일동안 매일 주가를 적어 놓고 가장 긴 오름세를 찾으시오
고려해야 할 사항
- 둘째 줄에서부터 주가가 첫 날부터 순서대로 주어집니다. 이때 주가는 한 개 이상의 공백으로 구분되어 있습니다.
문제 풀이
이 문제는 LIS문제입니다. 하지만 종료조건이 주어지지 않습니다. EOF처리 방법을 알아야 합니다.
EOF처리에 대해 처음으로 관심을 갖게 한 문제입니다.
while let input = readLine() {
...
}
기본적으로 Swift에서 EOF처리하는 방법은 위 코드와 같습니다.
고려해야 할 사항으로 두 번째 줄에 주가가 주어지는데, 주가가 한 개 이상의 공백으로 구분되어 있습니다. 또는 다른 위치에서도 자유롭게 나올 수 있습니다....
설마 이렇게??
input:
3
1 4
2
답 = 2...?
만약
3
1 4 2
주가가 이렇게 한 라인에서 공백 포함 나온다면
let lists = readLine()!.map{$0}.filter{$0 != " "}.map{Int(String($0))!}
readLine()을 활용할 수 있었을 텐데 맨 처음 예시처럼 \n 이후에도 주가가 나온다면... 음... 할 수는 있는데
while let input = readLine() {
let n = Int(input)!
var lists = [Int]()
while lists.count != n {
readLine()?
.compactMap{String($0)}
.filter{$0 != " " || $0 != "\n"}
.compactMap{Int($0)}
.map{lists.append($0)}
}
...
그래도 입력에서 틀렸습니다가 나와서..
이 글의 입력 함수를 통해 해결했습니다.
코드
var res = ""
var buffer: [UInt8] = Array(FileHandle.standardInput.readDataToEndOfFile()), byteIdx = 0; buffer.append(0)
@inline(__always) func readByte() -> UInt8 {
defer { byteIdx += 1 }
let bp = buffer.withUnsafeBufferPointer { $0[byteIdx] }
if bp == 0 { print(res); exit(0) } // 여기서 EOF 처리
return bp
}
@inline(__always) func readInt() -> Int {
var number = 0, byte = readByte(), isNegative = false
while byte == 10 || byte == 32 { byte = readByte() }
if byte == 45 { byte = readByte(); isNegative = true }
while 48...57 ~= byte { number = number * 10 + Int(byte - 48); byte = readByte() }
return number * (isNegative ? -1 : 1)
}
func binarySearch(_ seq: inout [Int], target: Int) {
var l = 0, r = seq.count-1, mid = 0
while l<r {
mid = (l+r)/2
if target>seq[mid] { l = mid+1 }
else { r=mid }
}
seq[r]=target
}
func solution() {
while true {
let n = readInt()
let lists = (0..<n).map{_ in readInt()}
var seq = [lists.first!]
(1..<lists.count).map{
if lists[$0] > seq.last! { seq.append(lists[$0]) }
else { binarySearch(&seq, target: lists[$0]) }
}
res += "\(seq.count)\n"
}
}
solution()
728x90
'백준 PS일지 > LongestIncreasingSubsequence' 카테고리의 다른 글
[백준/Swift] 2568: 전깃줄 - 2 문제 부수기!! + LIS 개념과 이분 탐색, 역 추적 개념 정리 | PS일지 (0) | 2023.02.19 |
---|---|
[백준/Swift] 14002: 가장 긴 증가하는 부분 수열4 파해치기 | PS일지. (0) | 2023.02.18 |
[백준/Swift] 2565 : 전깃줄 (0) | 2022.07.20 |