본문 바로가기

백준 PS일지/LongestIncreasingSubsequence

[백준/Swift] 3745: 오름세. while문 무한 입력 EOF처리 방법 | PS일지

문제

 

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