Jenikeju

출력

첫째 줄부터 차례대로 M개의 줄에 각각의 문제에 대한 답을 말해줬으면 좋겠어!!!. 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 돼. 그럼 땡큐~

이게 오박사님이 나에게 새로 주시려고 하는 도감이야. 너무 가지고 싶다ㅠㅜ. 꼭 만점을 받아줬으면 좋겠어!! 파이팅!!!

풀이

1. Dictionary에 포켓몬번호와 이름 저장

2. Array에 포켓몬번호 index에 맞게 이름 저장

3. 포켓몬이름이 주어지면 Dictionary에서 value, 번호가 주어지면 Array에서 출력

Dictionary 단일로 저장하고 filter를 이용해 key값을 불러왔는데 시간초과가 떴다

더 줄이는 방법으로 아예 두가지 컬렉션으로 접근하는 방식을 이용했다

import Foundation

let inputs = readLine()!.split(separator:" ").map{ Int(String($0))!}
var pokemonsDict = [String: Int]()
var pokemonsArr = Array(repeating: "", count: inputs[0]+1)

for i in 1...inputs[0] {
    let pokemon = readLine()!
    pokemonsDict[pokemon] = i
    pokemonsArr[i] = pokemon
}

for j in 0..<inputs[1] {
    var quest = readLine()!

    if Int(quest) == nil {
        print(pokemonsDict[quest]!)
    } else {
        print(pokemonsArr[Int(quest)!])
    }
}

풀이

1. 문자열을 Set에 저장

2. 검사해야할 문자열을 for로 검사 

역시나 2중 for문으로 검사하면 시간 초과가 떴다

이전까지 복잡하게 생각했지만 단순하게 시간을 줄여서 접근해보았다

array.contains는 O(n) 이지만 set.contains 은 O(1)이여서 Set을 이용했다

문자열 비교와 정렬은 쉽게 시간초과가 많이 일어나서 고차함수와 Set, Dictionary를 알맞게 사용해야겠다

import Foundation

let inputs = readLine()!.split(separator: " ").map{ Int(String($0))!}
var strs = Set<String>()
var count = 0

for i in 0..<inputs[0] {
    let str = readLine()!
    strs.insert(str)
}

for j in 0..<inputs[1] {
    let str = readLine()!

    if strs.contains(str) {
        count += 1
    }
}

print(count)

let cardNum = Int(readLine()!)!
let cards = readLine()!.split(separator: " ").map{ Int(String($0))!}
let getCardCount = Int(readLine()!)!
var getCards = readLine()!.split(separator: " ").map{ Int(String($0))!}

var dict = [Int: Int]()

for i in cards {
    dict[i] = 1
}

print(getCards.map{ (num: Int) -> Int in
    if dict[num] == nil {
        return 0
    } else {
        return 1
    }
}.map{String($0)}.joined(separator: " "))

풀이

x1 좌표를 압축한다 -> 주어진 좌표중에서 x1좌표보다 작은 좌표의 개수로 변환됨

-> 입력받은 x좌표를 배열로 만들어 오름차순으로 정렬 했을 때 인덱스 값이 곧 압축값이다

배열로 입력받으면 중복값이 있으므로 아예 인덱스를 구할땐 Set으로 변환했다

그리고 바로 map 고차함수를 사용하기위해 dict에 넣어두었다.

이 문제는 시간이 매우촉박해서 최대한 시간을 줄였어야했다

let input = Int(readLine()!)!
var nums = readLine()!.split(separator: " ").map{ Int(String($0))! }
var sortedSet = Set(nums).sorted{ $0 < $1}.enumerated()
var dict = [ Int: Int]()

for (index, number) in sortedSet {
    dict[number] = index
}
print(nums.map{ String(dict[$0]!)}.joined(separator: " "))

풀이

1. 입력순서와 나이 이름을 배열에 넣는다

2. 2차원배열에 넣어서 나이순으로 정렬한다

3. 나이가 같으면 입력순으로 정렬한다

import Foundation

func test() {
    guard let input = Int(readLine()!) else {return}
    var list = [[String]]()
    
    for i in 1...input {
        guard let str = readLine()?.split(separator: " ") else {return}
        var arr = str.map{ String($0)}
        arr.insert(String(i), at: 0)
        
        list.append(arr)
    }
    list.sort{ if Int($0[1]) == Int($1[1]) {
        return Int($0[0])! < Int($1[0])!
    } else {
        return Int($0[1])! < Int($1[1])!
    }}
    

    for i in list {
        var arr = i
        arr.removeFirst()
        print(arr.joined(separator: " "))
    }
}
test()

풀이

1. 길이가 같으면 사전순, 다르면 길이수의 오름차순으로 정렬한다

2. 정렬된 대로 출력한다.

앞서 11650번 문제의 좌표정렬하기에서 2차원 배열을 sort로 정렬하여 출력했었다.

같은 방법으로 string을 받아 길이 비교 후 사전순으로 정렬을 했는데 시간 초과가 떴다

더이상 시간을 줄일 수 없어서 배열 보다 빠른 Set 을 사용했다

Set은 

1. 정렬되지 않은 컬렉션

2. 중복된 요소를 허용하지않는다

3. 해시를 통해 값을 저장

 -> 배열에 비해 검색 속도가 빠르다.

4. 저장되는 자료형은 Hashable 프로토콜 준수

이 문제를 풀땐 배열보다 빠르다는 장점만 보고 사용했다

아슬아슬 하게 시간초과는 면했다

import Foundation

func test() {
    guard let input = Int(readLine()!) else {return}
    var strSet = Set<String>()
    for i in 0..<input {
        guard let str = readLine() else {return}
        strSet.insert(str)
    }
    var sortedSet = strSet.sorted{ if $0.count == $1.count {
        return $0 < $1
    } else {
        return $0.count < $1.count
    }}
    for i in sortedSet {
        print(i)
    }
}
test()

풀이

1.  x좌표를 오름차순으로 정렬한다.

2. x좌표가 같을 경우 y좌표를 오름차순으로 정렬한다.

- 2중 for문으로 index 값을 확인해서 insert 로 넣은 결과 시간초과가 떴다. 시간복잡도 O(n^2)

func test() { 	// 시간초과 N^2
    guard let count = Int(readLine()!) else { return }
    var nums = [[Int]]()

    for i in 0..<count {
        guard let input = readLine()?.split(separator: " ") else { return }
        var arr = input.map{ Int(String($0))!}
        var index = 0

        if nums.isEmpty {
            nums.append(arr)
            continue
        }

        for j in 0..<nums.count {
            let x1 = nums[j][0]
            let y1 = nums[j][1]
            let x2 = arr[0]
            let y2 = arr[1]

            if x1 < x2 {
                if j == nums.count - 1 {
                    index = nums.count
                }
                continue
            } else if x1 == x2 {
                if y1 < y2 {
                    index = j+1
                } else {
                    index = j
                }
                break
            } else {
                index = j
                break
            }
        }
        nums.insert(arr, at: index)
    }

    for j in nums {
        print(j.map{ String($0)}.joined(separator: " "))
    }

}

test()

시간제한 1초 였던 문제라 시간 복잡도를 좀  줄였어야했다.

그래서 array 함수중 sort를 이용했다. sort의 시간복잡도는 O(nlogn)으로 2중 배열보다 빨랐다.

하지만 sort 함수를 사용해서 2차원배열 y좌표 접근하는 방법은 아직 미숙했다.

< 11650 >

func test() {
    guard let input = Int(readLine()!) else {return}
    var nums = [[Int]]()
    
    for i in 0..<input {
        guard let inputs = readLine()?.split(separator: " ") else {return}
        var arr = inputs.map{ Int(String($0))!}
        nums.append(arr)
    }
    nums = nums.sorted{ if $0[0] == $1[0] {
        return $0[1] < $1[1]
    } else {
        return $0[0] < $1[0]
    }}
    
    for j in nums {
        print(j.map{ String($0)}.joined(separator: " "))
    }
}
test()

마지막 출력할때 사용된 map함수의 시간복잡도는 O(n)이므로 결국 n + nlogn 이므로 n^2 보다 빠르니 시간초과가 뜨지않았다

11651 은 정렬기준만 다르기때문에 위 코드와 큰 차이는 없었다

< 11651 >

import Foundation

func test() {
    guard let input = Int(readLine()!) else {return}
    var nums = [[Int]]()
    
    for i in 0..<input {
        guard let inputs = readLine()?.split(separator: " ") else {return}
        var arr = inputs.map{ Int(String($0))!}
        nums.append(arr)
    }
    nums = nums.sorted{ if $0[1] == $1[1] {
        return $0[0] < $1[0]
    } else {
        return $0[1] < $1[1]
    }}
    
    for j in nums {
        print(j.map{ String($0)}.joined(separator: " "))
    }
}
test()