스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.
입력
첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.
출력
입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.
예제 입력 1복사
8
4
3
6
8
7
5
2
1
예제 출력 1복사
+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-
예제 입력 2복사
5
1
2
5
3
4
예제 출력 2복사
NO
힌트
1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.
import Foundation
public struct Stack<T>{
private var elements = [T]()
public init() {}
public mutating func push(_ element: T){
self.elements.append(element)
}
public mutating func pop() -> T? {
let pop = self.elements.popLast()
self.elements.removeLast()
return pop
}
public mutating func poplast() {
self.elements.removeLast()
}
public func top() -> T? {
return self.elements.last
}
}
var myStack = Stack<Int>()
var ansArr : [String] = []
var cnt = 1
let input = Int(readLine()!)!
for _ in 0 ..< input {
let num = Int(readLine()!)!
while cnt <= num{
myStack.push(cnt)
ansArr.append("+")
cnt += 1
}
if myStack.top() == num{
myStack.poplast()
ansArr.append("-")
}else{
print("NO")
exit(0)
}
}
print(ansArr.joined(separator: "\n"))
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.
func sequencial(_ array: [Int], num: Int) -> Int {
var a = 0
for element in array {
if num == element {
a += 1
}
}
return a
}
var N = Int(readLine()!)!
var input_N = readLine()!.split(separator: " ").map{Int(String($0))!}
var M = Int(readLine()!)!
let input_M = readLine()!.split(separator: " ").map{Int(String($0))!}
input_N.sort()
var arr = [Int]()
for i in 0..<M{
arr.append(sequencial(input_N, num: input_M[i]))
}
print(arr.map{String($0)}.joined(separator: " "))
이진탐색으로 어떻게 해야할지 잘모르겠어서 완전탐색으로 하였다..
-> 당연히 시간초과 ㅋㅋㅌ ㅆ,,
실패코드 2트
func binarySearch(_ left: Int,_ right: Int , _ target: Int) -> Int{
let mid = Int((left + right) / 2)
var count = 0
if target == input_N[mid]{
var midLeft = mid - 1
count += 1
while midLeft >= 0 && target == input_N[midLeft]{
count += 1
midLeft -= 1
}
var midRight = mid + 1
while midRight < input_N.count && target == input_N[midRight]{
count += 1
midRight += 1
}
return count
}
if left > right || target < input_N[left] || target > input_N[right]{
return count
}
if target > input_N[mid]{
return binarySearch(mid + 1, right, target)
}else if target<input_N[mid]{
return binarySearch(left, mid - 1, target)
}
return count
}
var N = Int(readLine()!)!
var input_N = readLine()!.split(separator: " ").map{Int(String($0))!}
var M = Int(readLine()!)!
let input_M = readLine()!.split(separator: " ").map{Int(String($0))!}
input_N.sort()
var arr : [Int] = []
for i in input_M{
arr.append(binarySearch(0 , N-1 , i))
}
print(arr.map{String($0)}.joined(separator: " "))
나름 이분탐색 사용하였지만 다시나는 시간초과,,, 무엇이 문제일까..?
다음에 알아보도록 하자....
실패코드 3트
import Foundation
final class FileIO {
private let buffer:[UInt8]
private var index: Int = 0
init(fileHandle: FileHandle = FileHandle.standardInput) {
buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
}
@inline(__always) private func read() -> UInt8 {
defer { index += 1 }
return buffer[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 now = read()
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
let beginIndex = index-1
while now != 10,
now != 32,
now != 0 { now = read() }
return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
}
@inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
var now = read()
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
let beginIndex = index-1
while now != 10,
now != 32,
now != 0 { now = read() }
return Array(buffer[beginIndex..<(index-1)])
}
}
func binarySearch(_ left: Int,_ right: Int , _ target: Int) -> Int{
let mid = Int((left + right) / 2)
var count = 0
if target == input_N[mid]{
var midLeft = mid - 1
count += 1
while midLeft >= 0 && target == input_N[midLeft]{
count += 1
midLeft -= 1
}
var midRight = mid + 1
while midRight < input_N.count && target == input_N[midRight]{
count += 1
midRight += 1
}
return count
}
if left > right || target < input_N[left] || target > input_N[right]{
return count
}
if target > input_N[mid]{
return binarySearch(mid + 1, right, target)
}else if target<input_N[mid]{
return binarySearch(left, mid - 1, target)
}
return count
}
let fileIO = FileIO()
var input_N: [Int] = []
var input_M: [Int] = []
let N = fileIO.readInt()
for _ in 0..<N {
input_N.append(fileIO.readInt())
}
let M = fileIO.readInt()
for _ in 0..<M {
input_M.append(fileIO.readInt())
}
input_N.sort(by: <)
var result = ""
for i in input_M{
let count = binarySearch(0 , N-1 , i)
result += "\(count) "
}
print(result)
시간..초,,ㄱ..ㅘ....
딱알았다.. sort때문인거같으 이것만 다시해서 올려보겠습니다..ㅎ
4트ㅎㅎ
//import Foundation
//
//final class FileIO {
// private let buffer:[UInt8]
// private var index: Int = 0
//
// init(fileHandle: FileHandle = FileHandle.standardInput) {
//
// buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
// }
//
// @inline(__always) private func read() -> UInt8 {
// defer { index += 1 }
//
// return buffer[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 now = read()
//
// while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
// let beginIndex = index-1
//
// while now != 10,
// now != 32,
// now != 0 { now = read() }
//
// return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
// }
//
// @inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
// var now = read()
//
// while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
// let beginIndex = index-1
//
// while now != 10,
// now != 32,
// now != 0 { now = read() }
//
// return Array(buffer[beginIndex..<(index-1)])
// }
//}
func binarySearch(_ left: Int,_ right: Int , _ target: Int) -> Int{
let mid = Int((left + right) / 2)
var count = 0
if target == input_N[mid]{
var midLeft = mid - 1
count += 1
while midLeft >= 0 && target == input_N[midLeft]{
count += 1
midLeft -= 1
}
var midRight = mid + 1
while midRight < input_N.count && target == input_N[midRight]{
count += 1
midRight += 1
}
return count
}
if left > right || target < input_N[left] || target > input_N[right]{
return count
}
if target > input_N[mid]{
return binarySearch(mid + 1, right, target)
}else if target<input_N[mid]{
return binarySearch(left, mid - 1, target)
}
return count
}
func quickSort(numArr : [Int]) -> [Int]{
if numArr.count < 2{
return numArr
}
let pivot = numArr[0]
var left :[Int] = []
var right :[Int] = []
for i in 1..<numArr.count{
if pivot > numArr[i]{
left.append(numArr[i])
}else if pivot < numArr[i] {
right.append(numArr[i])
}else if pivot == numArr[i]{
left.insert(numArr[i], at: 0)
}
}
return quickSort(numArr: left) + [pivot] + quickSort(numArr: right)
}
//let fileIO = FileIO()
//var input_N: [Int] = []
//var input_M: [Int] = []
//let N = fileIO.readInt()
let N = Int(readLine()!)!
//for _ in 0..<N {
// input_N.append(fileIO.readInt())
//}
var input_N = readLine()!.split(separator: " ").map{Int(String($0))!}
//let M = fileIO.readInt()
let M = Int(readLine()!)!
//for _ in 0..<M {
// input_M.append(fileIO.readInt())
//}
var input_M = readLine()!.split(separator: " ").map{Int(String($0))!}
input_N = quickSort(numArr: input_N)
var result = ""
for i in input_M{
let count = binarySearch(0 , N-1 , i)
result += "\(count) "
}
print(result)
이렇게 해보니 1트와 2트는 그냥 틀린것 같네요? ㅎㅎ (말로만 1트 2트지 수많은 트라이들이...)
다른분들은 lower upper 나눠서 하길래 나는 다른길을 걷고자 악바리로 한번에 해보려했지만 안되는것같네요?ㅎㅎ
아직 의지는 꺾이지 않았습니다.
제출코드 5트..
import Foundation
final class FileIO {
private let buffer:[UInt8]
private var index: Int = 0
init(fileHandle: FileHandle = FileHandle.standardInput) {
buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
}
@inline(__always) private func read() -> UInt8 {
defer { index += 1 }
return buffer[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 now = read()
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
let beginIndex = index-1
while now != 10,
now != 32,
now != 0 { now = read() }
return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
}
@inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
var now = read()
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
let beginIndex = index-1
while now != 10,
now != 32,
now != 0 { now = read() }
return Array(buffer[beginIndex..<(index-1)])
}
}
func lowerBound(_ left: inout Int,_ right: inout Int , _ target: Int) -> Int{
while left < right{
let mid = Int((left + right) / 2)
if input_N[mid] < target {
left = mid + 1
}else if target <= input_N[mid] {
right = mid
}
}
return left
}
func upperBound(_ left: inout Int,_ right: inout Int , _ target: Int) -> Int{
while left < right{
let mid = Int((left + right) / 2)
if input_N[mid] <= target{
left = mid + 1
}else if target < input_N[mid]{
right = mid
}
}
return right
}
func binarySearch(_ left: Int,_ right: Int , _ target: Int) -> Int{
let mid = Int((left + right) / 2)
var count = 0
if target == input_N[mid]{
var midLeft = mid - 1
count += 1
while midLeft >= 0 && target == input_N[midLeft]{
count += 1
midLeft -= 1
}
var midRight = mid + 1
while midRight < input_N.count && target == input_N[midRight]{
count += 1
midRight += 1
}
return count
}
if left > right || target < input_N[left] || target > input_N[right]{
return count
}
if target > input_N[mid]{
return binarySearch(mid + 1, right, target)
}else if target<input_N[mid]{
return binarySearch(left, mid - 1, target)
}
return count
}
func quickSort(numArr : [Int]) -> [Int]{
if numArr.count < 2{
return numArr
}
let pivot = numArr[0]
var left :[Int] = []
var right :[Int] = []
for i in 1..<numArr.count{
if pivot > numArr[i]{
left.append(numArr[i])
}else if pivot < numArr[i] {
right.append(numArr[i])
}else if pivot == numArr[i]{
left.insert(numArr[i], at: 0)
}
}
return quickSort(numArr: left) + [pivot] + quickSort(numArr: right)
}
let fileIO = FileIO()
var input_N: [Int] = []
var input_M: [Int] = []
var N = fileIO.readInt()
//var N = Int(readLine()!)!
for _ in 0..<N {
input_N.append(fileIO.readInt())
}
//var input_N = readLine()!.split(separator: " ").map{Int(String($0))!}
var M = fileIO.readInt()
//var M = Int(readLine()!)!
for _ in 0..<M {
input_M.append(fileIO.readInt())
}
//var input_M = readLine()!.split(separator: " ").map{Int(String($0))!}
//input_N = quickSort(numArr: input_N)
input_N.sort()
var result = ""
var zero = 0
var N_real = N
for i in input_M{
//let count = binarySearch(0 , N-1 , i)
let up = upperBound(&zero, &N, i)
zero = 0
N = N_real
let lo = lowerBound(&zero, &N, i)
zero = 0
N = N_real
let count = up - lo
//print(String((upperBound(&zero, &N, i)) - (lowerBound(&zero, &N, i))), terminator: " ")
result += "\(count) "
}
print(result)
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
import Foundation
var N = Int(readLine()!)!
var arr = [(Int, Int)] ()
for _ in 0 ..< N{
let input = readLine()!.split(separator: " ").map{Int($0)}
arr.append((input[0]!, input[1]!))
}
arr.sort(by: {
$0.0 == $1.0 ? $0.1 < $1.1 : $0.0 < $1.0
})
for i in 0 ..< N{
print("\(arr[i].0) \(arr[i].1)")
}
func factorial(_ a : Int) -> Int {
var num = 1
for i in 2 ..< a+1{
num *= i
}
return num
}
let input = readLine()!.split(separator: " ").map{Int($0)!}
var N = input[0]
var K = input[1]
if K == 0 || N == K{
print(1)
}else{
let res = factorial(N) / (factorial(N-K)*factorial(K))
print(res)
}
정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여덟 가지이다.
push_front X: 정수 X를 덱의 앞에 넣는다.
push_back X: 정수 X를 덱의 뒤에 넣는다.
pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 덱에 들어있는 정수의 개수를 출력한다.
empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
예제 입력 1복사
15
push_back 1
push_front 2
front
back
size
empty
pop_front
pop_back
pop_front
size
empty
pop_back
push_front 3
empty
front
예제 출력 1복사
2
1
2
0
2
1
-1
0
1
-1
0
3
예제 입력 2복사
22
front
back
pop_front
pop_back
push_front 1
front
pop_back
push_back 2
back
pop_front
push_front 10
push_front 333
front
back
pop_back
pop_back
push_back 20
push_back 1234
front
back
pop_back
pop_back
import Foundation
public struct Dequeue<T>{
private var elements = [T]()
public init() {}
public mutating func push_front(_ element: T){
self.elements.insert(element, at: 0)
}
public mutating func push_back(_ element: T){
self.elements.append(element)
}
public mutating func pop_front() -> T? {
if self.elements.isEmpty{
return ( -1 as! T)
}else{
let pop = self.elements.first
self.elements.remove(at: 0)
return pop
}
}
public mutating func pop_back() -> T? {
if self.elements.isEmpty{
return ( -1 as! T)
}else{
let pop = self.elements.last
let size = (self.elements.count) - 1
self.elements.remove(at: size)
return pop
}
}
public func empty() -> Bool {
return self.elements.isEmpty
}
public var size: Int {
return self.elements.count
}
public mutating func front() -> T? {
if self.elements.isEmpty{
return (-1 as! T)
}else{
return self.elements.first //맨앞정수
}
}
public mutating func back() -> T? {
if self.elements.isEmpty{
return (-1 as! T)
}else{
return self.elements.last //맨뒤정수
}
}
}
var myDequeue = Dequeue<Int>()
let input = Int(readLine()!)!
for _ in 1...input {
let a = readLine()!.split(separator: " ")
switch String(a[0]) {
case "push_front":
myDequeue.push_front(Int(a[1])!)
case "push_back":
myDequeue.push_back(Int(a[1])!)
case "pop_front":
print(myDequeue.pop_front()!)
case "pop_back":
print(myDequeue.pop_back()!)
case "size":
print(myDequeue.size)
case "empty":
if myDequeue.empty() == false{
print(0)
}else{
print(1)
}
case "front":
print(myDequeue.front()!)
case "back":
print(myDequeue.back()!)
default:
break
}
}
import Foundation
public struct Queue<T>{
private var elements = [T]()
public init() {}
public mutating func push(_ element: T){
self.elements.append(element)
}
public mutating func pop() -> T? {
if self.elements.isEmpty{
return ( -1 as! T)
}else{
let pop = self.elements.first
self.elements.remove(at: 0)
return pop
}
}
public func empty() -> Bool {
return self.elements.isEmpty
}
public var size: Int {
return self.elements.count
}
public mutating func front() -> T? {
if self.elements.isEmpty{
return (-1 as! T)
}else{
return self.elements.first //맨앞정수
}
}
public mutating func back() -> T? {
if self.elements.isEmpty{
return (-1 as! T)
}else{
return self.elements.last //맨뒤정수
}
}
}
var myQueue = Queue<Int>()
let input = Int(readLine()!)!
for _ in 1...input {
let a = readLine()!.split(separator: " ")
switch String(a[0]) {
case "push":
myQueue.push(Int(a[1])!)
case "pop":
print(myQueue.pop()!)
case "size":
print(myQueue.size)
case "empty":
if myQueue.empty() == false{
print(0)
}else{
print(1)
}
case "front":
print(myQueue.front()!)
case "back":
print(myQueue.back()!)
default:
break
}
}
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231보다 크거나 같고 231보다 작다.
import Foundation
//N(1 ≤ N ≤ 100,000)
//M(1 ≤ M ≤ 100,000)
let N = Int(readLine()!)!
var arr_N = readLine()!.split(separator: " ").map{ Int($0)! }
let M = Int(readLine()!)!
var arr_M = readLine()!.split(separator: " ").map{ Int($0)! }
for i in 0..<N{
let num_m = arr_M[i]
if arr_N.contains(num_m){
print(1)
}else{
print(0)
}
}
너무 쉽다고 생각한후 이렇게 코드작성을 하니 당연히 시간 초과가 났다,,,
카테고리에 이진탐색을 발견후 코드를 바꿔줬다.
제출코드
import Foundation
//N(1 ≤ N ≤ 100,000)
//M(1 ≤ M ≤ 100,000)
func binarySearch(_ arr: [Int], _ target: Int) -> Int{
var start = 0
var end = arr.count - 1
while start <= end {
let mid = (start + end) / 2
if arr_N[mid] == target {
return 1
}else if arr_N[mid] > target {
end = mid - 1
}else if arr_N[mid] < target {
start = mid + 1
}
}
return 0
}
let N = Int(readLine()!)!
var arr_N = readLine()!.split(separator: " ").map{ Int($0)! }
let M = Int(readLine()!)!
var arr_M = readLine()!.split(separator: " ").map{ Int($0)! }
arr_N.sort()
for i in 0..<M{
print(binarySearch(arr_N, arr_M[i]))
}
import Foundation
let N = Int(readLine()!)!
var arr = [Int]()
for _ in 0..<N {
arr.append(Int(readLine()!)!)
}
var resArr = arr.sorted()
for i in 0..<N{
print(resArr[i])
}
import Foundation
let N = Int(readLine()!)!
var arr = [Int]()
for _ in 0..<N {
arr.append(Int(readLine()!)!)
}
var resArr = arr.sorted()
for i in 0..<N{
print(resArr[i])
}
당연히 sort를 사용하여 푸는 문제라고 접근하여서 풀었더니 시간초과만 주구장창 나왔다...
N의 범위가 N(1 ≤ N ≤ 10,000,000) 이니 입력을 받을때와 print를 할때 시간이 오래걸리는것을 알았지만~
import Foundation
final class FileIO {
private let buffer:[UInt8]
private var index: Int = 0
init(fileHandle: FileHandle = FileHandle.standardInput) {
buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
}
@inline(__always) private func read() -> UInt8 {
defer { index += 1 }
return buffer[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)
}
}
let file = FileIO()
let N = file.readInt()
var arr = Array(repeating:0,count:10001)
for _ in 0 ..< N {
let i = file.readInt()
arr[i] += 1
}
var res = ""
for i in 1...10000 {
res += String(repeating:"\(i)\n",count:arr[i])
}
print(res)