Jenikeju

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42579

내가 푼 풀이

[장르: (인덱스: Int, 재생수: Int)]의 딕셔너리 한개와, [장르: 총재생수] 딕셔너리를 구현하여 만들었습니다.

주어진 jenres 문자열 배열을 위 딕셔너리 두개로 먼저 파싱한 뒤, 총 재생수가 많은 순으로 정렬하여 해당 장르를 접근하였습니다.

[장르: (인덱스: Int, 재생수: Int)]의 value에서 재생수가 많은 순으로 정렬한 다음, 장르 key값으로 (인덱스: Int, 재생수: Int) 튜플 value에 접근하여 가장 재생수가 높은 두개의 곡을 뽑아서 배열에 저장한 뒤 리턴하였습니다.

코드로 구현하면 다음과 같습니다.

import Foundation

func solution(_ genres:[String], _ plays:[Int]) -> [Int] {
    var played = [String: [(index: Int, plays: Int)]]()
    var totalPlayedGenres = [String: Int]() 
    var album = [Int]()
    
    for i in 0..<genres.count {
        let genre = genres[i]
        let playCount = plays[i]
        if played[genre] == nil {
            played[genre] = [(index: i, plays: playCount)]
            totalPlayedGenres[genre] = playCount
        } else {
            played[genre]!.append((index: i, plays: playCount))
            totalPlayedGenres[genre]! += playCount
        }
    }
    
    let sortedGenres = totalPlayedGenres.sorted { $0.value > $1.value }
    
    sortedGenres.forEach { element in
        let songs = played[element.key]!.sorted{ $0.plays > $1.plays}
        
        for i in 0..<songs.count {
            album.append(songs[i].index)
            if i == 1 { break }
        }
    }
    return album
}

문제

https://school.programmers.co.kr/learn/courses/30/lessons/388352

내가 푼 방법

비밀코드의 범위가 주어지면 해당 범위에서 만들 수 있는 모든 조합을 먼저 구한 뒤,

각 ans의 응답값을 비교해서 모두 일치하는 경우 하나의 비밀코드로 간주했다.

조합과 이중반복문으로 시간초과가 걸릴 것 같았지만, 가까스로 통과한 느낌이였다.

import Foundation

func solution(_ n:Int, _ q:[[Int]], _ ans:[Int]) -> Int {
    let targetArr = Array(1...n)
    var total = 0
    var results = [[Int]]()
    // 조합
    func combi(targetArr: [Int], targetNum: Int, index: Int, arr: [Int]) {
        if arr.count == targetNum {
            results.append(arr)
            return
        }
        for i in index..<targetArr.count {
            combi(targetArr: targetArr, targetNum: targetNum, index: i+1, arr: arr + [targetArr[i]])
        }
    }
    combi(targetArr: targetArr, targetNum: 5, index: 0, arr: [])
    
    // 각 응답값 비교
    results.forEach { element in
        for i in 0..<q.count {
            let arr = q[i]
            if !compare(lhs: arr, rhs: element, correct: ans[i]) {
                break
            }
            if i == q.count-1 {
                total += 1
            }
        }
    }
    return total
}

func compare(lhs: [Int], rhs: [Int], correct: Int) -> Bool {
    var count = 0
    for i in 0..<lhs.count {
        if rhs.contains(lhs[i]) { count += 1}
    }
    if count == correct { return true }
    return false
}

문제 설명 ▼

내가 푼 풀이

• 주어진 players배열과 크기가 같은 servers 배열을 만들었습니다.
• players배열을 반복문으로 순회하면서 각 시간마다 서버 증설이 필요한지 조건을 달았습니다.
• 증설이 필요하다면 그리디 기법으로 현재 시간의 인원을 수용할 만큼만의 서버를 증설하고 k시간까지 최대 이용자 수를 증가시켰습니다.
• 증설이 필요할 때 서버를 증설하고 증설된 수를 count 변수에 담아서 리턴했습니다.

import Foundation

func solution(_ players:[Int], _ m:Int, _ k:Int) -> Int {
    var servers = Array(repeating: 0, count: players.count)
    var count = 0
    
    for i in 0..<players.count {
        let allowPlayerCount = (servers[i] * m) + m
        if players[i] >= allowPlayerCount {
            let needServerCount = abs(servers[i] - (players[i] / m))
            count += needServerCount
            for j in i..<i+k {
                if j >= players.count { continue }
                servers[j] += needServerCount
            }
        }
    }
    
    return count
}

문제 설명▼

내가 푼 풀이

BFS를 사용해서 풀었습니다.

• 1번으로부터 가장 먼 노드의 갯수를 구하기 때문에, 인접한 그래프를 이동하는 움직임을 하나의 단위로 생각했습니다.
• 한번의 움직임을 담은 needToVisit 배열과, 움직임을 통해 도착한 노드의 인접그래프가 담긴 saveNextVisitList 배열을 선언해 주었습니다.
• 한번 이동을 통해 needToVisit의 배열이 비었다면, 도착 노드와 인접한 노드들이 담긴 saveNextVisitList를 needToVisit에 할당하고 saveNextVisitList를 빈배열로 초기화했습니다.
• 이미 방문한 노드들은 다시 갈 필요가 없으므로 노드 갯수만큼의 visited 배열 크기를 만들고 선언했습니다.
• saveNextVisitList에는 Set 형변환을 통해 중복 노드들을 제거하고 다시 Array배열로 형변환 후 visited 배열을 통해 방문하지 않은 노드들로 필터링을 했습니다.
• needToVisit은 인접한 그래프로의 한 움직임 단위 이므로 이를 lastNode 2차원 배열에 담았습니다. lastNode 배열은 needToVisit의 기록을 담고있습니다.
• 최종적으로 모든 노드를 도달했다면 needToVisit은 빈 배열이 되고 빈 배열이 lastNode배열에 담기게 되므로 결과로 lastNode의 마지막에서 두번째 원소의 갯수를 리턴하도록 설계하였습니다.

import Foundation

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    var graph: [Int: [Int]] = [:]
    // 그래프를 딕셔너리에 담기
    edge.forEach { (element) in
        if graph[element[0]] == nil {
            graph[element[0]] = [element[1]]
        } else {
            graph[element[0]]!.append(element[1])
        }
        if graph[element[1]] == nil {
            graph[element[1]] = [element[0]]
        } else {
            graph[element[1]]!.append(element[0])
        }
    }
    
    // 인접한 그래프로의 한번 이동을 담은 배열
    var needToVisit = [1]
    // 인접한 도착노드들의 인접노드들을 담은 배열
    var saveNextVisitList: [Int] = []
    // 방문기록
    var visited = Array(repeating: false, count: n+1)
    // needToVisit의 이전 기록들을 담는 배열
    var lastNode = [[Int]]()
    
    // BFS
    while !needToVisit.isEmpty {
        let node = needToVisit.removeFirst()
        visited[node] = true
        var nextNodes = graph[node]!
        saveNextVisitList += nextNodes
        
        if needToVisit.isEmpty {
            if saveNextVisitList.isEmpty {
                break 
            }
            let setVisitList = Array(Set(saveNextVisitList))
            for element in setVisitList {
                if !visited[element] {
                    needToVisit.append(element)
                    
                }
            }
            lastNode.append(needToVisit)
            saveNextVisitList = []
        }
    }
    return lastNode[lastNode.count-2].count
}

문제 설명

내가 푼 풀이

첫번째 방법 - DFS

한개의 물건이 주어졌을 때, 두가지 경우의 수가 있습니다.

1. A가 훔치기

2. B가 훔치기

또한 경찰에게 걸리지 않게 모든 물건을 훔쳤기에 물건을 훔치지 않는 옵션은 없습니다.

결국 A가 최소로 도둑질을 하면 흔적도 자연스럽게 최솟값을 가질 것이라 생각하고, B에게 먼저 조건을 걸어주었고, B가 최대한 훔치도록 구현하였습니다.

import Foundation

func solution(_ info:[[Int]], _ n:Int, _ m:Int) -> Int {
    var min = Int.max
    var informations = info
    
    func dfs(count: [Int], currentIndex: Int) {
        if currentIndex >= info.count {
            min >= count[0] ? min = count[0] : nil
            return
        }
        let theifACount = [count[0] + info[currentIndex][0], count[1]]
        let theifBCount = [count[0], count[1] + info[currentIndex][1]]
        if theifACount[0] < n && theifACount[0] < min {
            dfs(count: [count[0] + info[currentIndex][0], count[1]],
            currentIndex: currentIndex + 1)
        }
        if theifBCount[1] < m {
            dfs(count: [count[0], count[1] + info[currentIndex][1]],
            currentIndex: currentIndex + 1)
        }
    }
    dfs(count: [0, 0], currentIndex: 0)
    
    return min == Int.max ? -1 : min
}

결과는 시간초과가 발생하였습니다.

이유를 확인해보면, 만약 m,n이 매우 넉넉하다면, 큰 수라면 bfs의 실행은 $2^{40}$ 번 실행되어 시간초과가 발생하였습니다.

그러면 시간만 줄여서 될까 해서 테스트케이스를 몇 개 추가했더니, 해당 케이스도 실패하는걸 볼 수 있었습니다.

info = [[1, 2], [3, 1], [3, 2]]
n = 5
m = 3
// 결과는 4가 나와야 하지만 1이 나왔습니다.

이를 통해 매번 탐색할 때 최적해를 갱신해야 할 필요가 있구나 싶었습니다.

두번째 방법 - DP

이전까지의 최적해를 저장하여 그다음 최적해를 구하기 위해 DP를 사용했습니다.

info배열을 돌면서 한번으로 최적해가 구해질 수 있을까? 해서 작성해보았는데 위 테스트 케이스도 통과하지 못했습니다.

B도둑이 알뜰살뜰하게 m을 넘지 않으면서 m과 가까운 수만큼 흔적을 남기는 방법이 뭐가 있을까 하다가 배낭문제가 생각났습니다.

(도둑이 배낭에 보석을 담을 때 정해진 배낭무게, 보석무게와 가치에 맞춰서 가장 가치있는 보석만 골라담는 문제)

B도둑이 최대한 흔적을 많이 남길 수 있게 배낭문제처럼 m값을 갱신하고 A흔적의 최솟값을 구하려고 합니다.

이를 1번 입력을 예시로 2차원배열로 나타내보겠습니다.

행은 m, B가 남길 수 있는 흔적 입니다. 열은 index로 info의 물건을 접근하기위한 인덱스입니다.

조건을 다시 살펴보자면,

1. 모든 물건을 훔쳤다.(물건을 훔치지 않고 건너뛰는건 불가능)

2. A는 n, B는 m 보다 같거나 클 수 없다. 만약 같거나 크다면 훔칠 수 없다고 판단한다.

위 조건을 바탕으로 배낭문제 처럼 2차원 배열을 채워가며 A의 최솟값을 구하겠습니다.

dp[i][j] = 0 은 물건을 하나도 훔치지 않을 때 값입니다.

행은 무게를 뜻하고, 열은 물건의 순서를 뜻하고, 해당 위치의 원소는 A의 흔적입니다.

첫번째는 아무것도 훔치지 않았기때문에 dp[0][1...3] = 0 입니다.

이제 첫번째 물건을 훔치겠습니다. 물건의 정보는 [1, 2] 입니다.

이때, 두가지 경우의 수가 있습니다. (1. A가 훔치기 2. B가 훔치기)

해당 DP인덱스의 원소는 A의 흔적을 의미하기에 A가 훔친다면 이전 값에서 A의 흔적을 더한값이 될 것입니다.

B가 훔친다면, (현재열 + 2) 인덱스에 이전 값을 넣게 됩니다.

이렇게 이전의 저장된 값을 바탕으로 최적해를 구하기위해 갱신하면 다음과 같습니다.

그 다음 두번째 물건을 훔치겠습니다. 물건의 정보는 [2,3] 입니다.

두번째 물건도 두가지 경우가 있습니다.

dp[2][0]에는 3이 들어가고 이 의미는 두번째 물건까지 A가 훔치는 경우입니다.

두번째 물건을 B가 훔치는 경우는 (현재 열 + 3) 인덱스에 넣게 되는데, 이 때 첫번째 물건을 넣은 값과 비교를 해야합니다.

dp[2][j + 3] = min ( dp[2][j + 3], dp[1][j] )

j = 0일때, dp[2][3] = min(dp[2][3], dp[1][0]) 을 비교하게 됩니다. (INF  > 1)

이를 m = 3까지 갱신해줍니다.

dp[2][1], dp[2][2]는 첫번째는 B, 두번째는 A가 훔친경우입니다. 첫번째와 두번째 둘다 A가 훔친 경우(dp[2][0])보다 작은 수 이므로 갱신했습니다.

마지막으로 세번째 물건을 훔치겠습니다. 물건 정보는 [2,1]입니다.

세번째 물건까지 A가 훔치면 dp[3][0] = 5입니다.

세번째 물건을 B가 훔치는 경우라면 현재 인덱스 + 1의 자리를 갱신해줍니다.

dp[3][1] = min (dp[3][1], dp[2][1]) = 3

m = 3까지 갱신해주면 아래와 같습니다.

최종적으로 dp[3][3]에 구하는 값을 나타낼 수 있음을 알 수 있습니다.

여기까지 살펴본 결과 2차원 배열의 의미를 다음과 같이 나타낼 수 있습니다.

dp[i][j]

• i : 현재 물건의 인덱스
• j : 현재 B의 흔적
• dp[i][j]의 원소: i번째 물건까지 훔쳤고 현재 B의 흔적이 j일때 A의 흔적 값

점화식은 아래와 같습니다.

1. A가 훔쳤을 때 : dp[i][j] = min(dp[i][j], dp[i-1][j] + a) (a는 해당물건의 A흔적)
2. B가 훔쳤을 때 : dp[i][j+b] = min(dp[i][j+b], dp[i-1][j]) (b는 해당물건의 B흔적)

코드로 나타내면 다음과 같습니다.

import Foundation

func solution(_ info:[[Int]], _ n:Int, _ m:Int) -> Int {
    let INF = 100000000
    
    // DP
    var dp = Array(repeating: Array(repeating: INF, count: m),
                   count: info.count+1)
    for i in 0..<m {
        dp[0][i] = 0
    }
    
    for i in 1...info.count {
        // 현재 물건에 대한 A의 흔적과 B의 흔적
        let aThief = info[i-1][0]
        let bThief = info[i-1][1]
        
        for j in 0..<m {
        	// A가 훔친 경우 값 갱신
            dp[i][j] = min(dp[i][j], dp[i-1][j] + aThief)
            
            // B가 훔친 경우 값 갱신
            if j + bThief < m { 
                dp[i][j + bThief] = min(dp[i][j + bThief], dp[i-1][j])
            }
        }
    }
	// 마지막 물건과 B의 흔적이 m보다 크거나 같지 않게 훔쳤을 때의 최소값 리턴
    return dp[info.count][m-1] >= n ? -1 : dp[info.count][m-1]
}

기능 설명

중복되지 않는 3자리 숫자를 맞추는 게임입니다.

각 자리수는 서로 중복되지 않고, 앞자리에는 0이 올 수 없습니다.

입력

입력은 문자열을 포함하지 않은 숫자 3자리를 입력받습니다.

아래와 같이 올바르지 않는 입력 경우의 수는 다음과 같습니다.

- 빈 문자열

- 중복된 값이 존재하는 3자리 문자열

- 3자리가 아닌 문자열

- String값이 섞인 문자열

- 0으로 시작하는 문자열

// 올바르지 않는 입력값
input1 = ""
input2 = "122"
input3 = "12"
input4 = "12e"
input5 = "dfe"
input6 = "012"

이를 아래와 같이 필터링하는 메서드를 만들었습니다.

private func isCorrectInput(input: String) -> Bool {
	// 문자열의 앞 문자가 0인경우
    if input.prefix(1) == "0" { return false }
    // 빈문자열인 경우, Set타입으로 타입변환 시 중복된 원소가 제거되므로 변환해도 3자리 문자열인 경우
    if Int(input) == nil || Set(input.map{$0}).count != 3 {
        return false
    }
    
    return true
}

- Int(input): String값을 Int로 형변환 했을 때 숫자가 아닌 문자인 경우 nil로 변환되기에 여기서 문자열 안에 문자를 검사한다.

정답값 생성

중복없는 3자리 문자열 생성

private func initAnswer() {
    var answerArray = [Int]()
    
    func randomNumber(range: Range<Int>) -> Int {
        return Int.random(in: range)
    }
    
    while answerArray.count < 3 {
        let num = randomNumber(range: 1..<10)
        if !answerArray.contains(num) { answerArray.append(num)}
    }
    
    answer = answerArray
}

입력값과 정답 비교

각 자리마다 숫자를 비교하는데 결과는 3종류로 나타낼 수 있습니다.

- 자리도 같고 숫자도 같다면 Strike

- 자리는 다르지만 숫자가 존재한다면 Ball

- 자리도 없고 숫자도 존재하지 않으면 x

private func compareAnswer(with numArray: [Int]) -> (equalPoint: Int, containsPoint: Int) {
    var equalPoint = 0
    var containsPoint = 0
    
    for i in 0..<numArray.count {
        if answer[i] == numArray[i] {
            equalPoint += 1
        } else if answer.contains(numArray[i]) {
            containsPoint += 1
        }
    }
    return (equalPoint: equalPoint, containsPoint: containsPoint)
}

그에 따른 결과도 3가지로 나눌 수 있습니다.

- 정답

- N Strike N ball

- Nothing

이를 Strike와 Ball의 개수로 판단하도록 설계하였습니다.

private func playBaseball() {
    var currentTryCount = 0
    var isFindAnswer = false
    currentGameIndex += 1
    initAnswer()
    print("<게임을 시작합니다.>")
    while !isFindAnswer {
        print("숫자를 입력하세요")
        guard let input = readLine() else { continue }
        if !isCorrectInput(input: input) {
            print("올바르지 않은 입력값입니다.\n")
            continue
        }
        
        currentTryCount += 1
        let inputIntegerArray = input.map{Int(String($0))!}
        let result = compareAnswer(with: inputIntegerArray)
        
        if result.equalPoint == 3 {
            print("정답입니다!")
            isFindAnswer = true
            records.append((game: currentGameIndex, tryCount: currentTryCount))
        } else if result.equalPoint == 0 && result.containsPoint == 0 {
            print("Nothing")
        } else {
            print("\(result.equalPoint) Strike  \(result.containsPoint) Ball")
        }
    }
}

게임 모드

게임을 시작하면 [1. 게임진행], [2. 이전기록확인], [3.종료하기] 로 세가지 동작을 실행할 수 있습니다.

이를 열거형을 사용하여 didSet 관찰자를 사용해 입력받은 값에 따라 설정하여 didSet에 선언된 메서드가 실행되도록 구현하였습니다.

enum GameState: Int {
    case play = 1
    case record = 2
    case exit = 3
    case none
}

private var currentState: GameState = .none {
    didSet {
        switch currentState {
        case .play:
            playBaseball()
        case .record:
            openRecord()
        case .exit:
            exitGame()
        default:
            print("올바른 숫자를 입력해주세요!")
        }
    }
}

func play() {
    while currentState != .exit {
        selectMode()
    }
}

private func selectMode() {
    print("환영합니다! 원하시는 번호를 입력해주세요\n1. 게임 시작하기  2. 게임 기록 보기  3. 종료하기")
    guard let input = readLine(),
    let inputInteger = Int(input),
    let state = GameState(rawValue: inputInteger) else { return }
    currentState = state
}

종합해보면 아래와 같습니다.

class NumberBaseballGame {
    
    private var answer: [Int] = []
    private var records: [(game: Int, tryCount: Int)] = []
    private var currentGameIndex = 0
    private var currentState: GameState = .none {
        didSet {
            switch currentState {
            case .play:
                playBaseball()
            case .record:
                openRecord()
            case .exit:
                exitGame()
            default:
                print("올바른 숫자를 입력해주세요!")
            }
        }
    }
   
    enum GameState: Int {
        case play = 1
        case record = 2
        case exit = 3
        case none
    }
    
    init() { }
    
    func play() {
        while currentState != .exit {
            selectMode()
        }
    }
    
    private func selectMode() {
        print("환영합니다! 원하시는 번호를 입력해주세요\n1. 게임 시작하기  2. 게임 기록 보기  3. 종료하기")
        guard let input = readLine(),
        let inputInteger = Int(input),
        let state = GameState(rawValue: inputInteger) else { return }
        currentState = state
    }
    
    private func exitGame() {
        records.removeAll()
        currentGameIndex = 0
    }
    
    private func openRecord() {
        records.forEach { (game, count) in
            print("\(game)번째 게임 : 시도 횟수 - \(count)\n")
        }
    }
    
    private func playBaseball() {
        var currentTryCount = 0
        var isFindAnswer = false
        currentGameIndex += 1
        initAnswer()
        print("<게임을 시작합니다.>")
        while !isFindAnswer {
            print("숫자를 입력하세요")
            guard let input = readLine() else { continue }
            if !isCorrectInput(input: input) {
                print("올바르지 않은 입력값입니다.\n")
                continue
            }
            
            currentTryCount += 1
            let inputIntegerArray = input.map{Int(String($0))!}
            let result = compareAnswer(with: inputIntegerArray)
            
            if result.equalPoint == 3 {
                print("정답입니다!")
                isFindAnswer = true
                records.append((game: currentGameIndex, tryCount: currentTryCount))
            } else if result.equalPoint == 0 && result.containsPoint == 0 {
                print("Nothing")
            } else {
                print("\(result.equalPoint) Strike  \(result.containsPoint) Ball")
            }
        }
    }
    
    private func isCorrectInput(input: String) -> Bool {
        if input.prefix(1) == "0" { return false }
        if Int(input) == nil || Set(input.map{$0}).count != 3 {
            return false
        }
        
        return true
    }
    
    private func initAnswer() {
        var answerArray = [Int]()
        
        func randomNumber(range: Range<Int>) -> Int {
            return Int.random(in: range)
        }
        
        while answerArray.count < 3 {
            let num = randomNumber(range: 1..<10)
            if !answerArray.contains(num) { answerArray.append(num)}
        }
        
        answer = answerArray
    }
    
    private func compareAnswer(with numArray: [Int]) -> (equalPoint: Int, containsPoint: Int) {
        var equalPoint = 0
        var containsPoint = 0
        
        for i in 0..<numArray.count {
            if answer[i] == numArray[i] {
                equalPoint += 1
            } else if answer.contains(numArray[i]) {
                containsPoint += 1
            }
        }
        return (equalPoint: equalPoint, containsPoint: containsPoint)
    }
    
}

예로 수열 [10, 20, 10, 30, 15, 50]이 주어졌을 때, 이분탐색을 이용하여 구한다면

[10, 15, 30, 50]배열이 구해지고 이는 최장증가 부분수열이 아니다.

이유는 15는 50이전의 원소로 30보다 나중에 나오는 원소이므로 옳지 않다.

부분수열은 구할 수 없지만 길이는 알고있다.

이 점을 이용하여 이분탐색을 통해 부분수열을 구할 때, 해당 원소의 인덱스를 저장한다.

괄호안 숫자는 해당원소가 주어진 수열의위치를 의미한다.

첫번째 원소 10

첫번째 원소는 비교대상이 없으므로 첫번째에 넣는다.

result = [10(1)]

idx = [1]

두번째 원소 20

두번쨰 원소는 이분탐색을 이용하여 10뒤에 오는 숫자임을 알 수 있다.

result = [10(1), 20(2)]

idx = [1, 2]

세번째 원소 10

세번째 원소는 이분탐색 결과 첫번째 오는 숫자와 같음을 알 수 있다.

result = [10(3), 20(2)]

idx = [1, 2, 1]

네번째 원소 30

네번째 원소는 20뒤에오는 숫자임을 알 수 있다.

result = [10(3), 20(2), 30(4)]

idx = [1, 2, 1, 3]

다섯번째 원소 15

다섯번째 원소는 이분탐색 결과 10과 20사이에 오는 숫자임을 알 수 있다.

이분탐색 결과 부분수열은 아래와 같다.

result = [10(3), 15(5), 30(4)]

idx = [1, 2, 1, 3, 2]

-> 이분탐색으로 만들어진 부분수열은 이미 정답과는 다른 부분수열이 만들어졌다. 해당원소의 위치를 배열안에 저장한다.

여섯번째 원소 50

여섯번째 원소는 이분탐색결과 마지막에 오는 숫자임을 알 수 있다.

result = [10(3), 15(5), 30(4), 50(6)]

idx = [1, 2, 1, 3, 2, 4]

-> 결과

result = [10(3), 15(5), 30(4), 50(6)]

idx = [1, 2, 1, 3, 2, 4]

이전의 이분탐색을 이용하면 result 배열을 얻고 길이는 정답이지만 부분 수열은 옳지않은 수열이 된다.

이분탐색을 통해 부분수열의 값이 변경될때 해당 원소가 위치하는 인덱스값을 저장함으로써 길이를 차감하며 부분수열을 구할 수 있게된다.

길이가 4이므로 역순으로 4 3 2 1의 원소를 뽑으면 [50, 30, 20 ,10]이고 이배열의 역순은 정답이 된다.

이분탐색을 이용하는 방법은 알았지만, 부분수열을 뽑아내는 과정은 쉽게 떠올리지 못했다.

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let N = Int(readLine()!)!
var A = readLine()!.split(separator: " ").map{Int(String($0))!}
A.insert(0, at: 0)
let INF = 1000000001
// 이분탐색 결과배열과 인덱스 배열
var result = Array(repeating: INF, count: N+1)
var idxArr = [Int]()
result[1] = A[1]

// 이분탐색
func binarySearch(num: Int) {
    var left = 1
    var right = result.count-1
    
    while left <= right {
        let mid = (right + left) / 2
        
        if result[mid] < num {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    // 해당위치에 넣고, 인덱스배열에 저장
    result[left] = num
    idxArr.append(left)
}

for i in 1...N {
    binarySearch(num: A[i])
}

var answer = [Int]()
var count = 0

// 부분수열의 길이 구하기
for i in 1...N {
    if result[i] != INF {
        count += 1
    } else {
        break
    }
}
// 부분수열 구하기
for i in (0..<idxArr.count).reversed() {
    if idxArr[i] == count {
        count -= 1
        answer.append(A[i+1])
    }
}
// 출력
print(answer.count)
print(answer.map{String($0)}.reversed().joined(separator: " "))