Jenikeju

풀이

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()

풀이

1. 입력받은 수를 Int 배열로 바꾼다

2. 배열을 내림차순으로 정렬한다 sort

3. 정렬된 배열을 String 배열로 바꾼뒤 String으로 변환한다 joined

import Foundation

func test() {
    guard let input = readLine() else { return }
    var nums = Array(input).map{ Int(String($0))!}
    nums.sort{ $0 > $1 }
    print(nums.map{ String($0)}.joined(separator: ""))
}

test()

풀이

1. 666이 가장 작은 종말의 수로 666부터 시작한다

2. 666이 연속되고, 연속된 666의 갯수가 1번인 경우만 배열에 넣는다 ( 6660666 x)

3. 입력받은 수 ( N번째로 작은 종말의 수) 만큼 배열에 찼다면, 배열의 마지막수를 출력한다

import Foundation

func test() {
    guard let index = Int(readLine()!) else { return }
    
    var num = 666
    var nums = [Int]()
    
    while nums.count < index {
        var number = num
        var sixCount = 0
        var tripleCount = 0
        
        while number > 0 {
            
            if number % 10 == 6 {
                sixCount += 1
            } else {
                sixCount = 0
            }
            
            if sixCount == 3 {
                tripleCount += 1
                
            }
            number = number / 10
        }
        
        if tripleCount == 1 {
            nums.append(num)
        }
        num += 1
        
    }
    print(nums.last!)

}

test()