Jenikeju

문제

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

내가 푼 풀이

- 해당 위치의 스티커를 붙이게 된다면, 위치 기준 양옆 위아래 붙일 수 없다.

- 해당 열에서 스티커를 붙이고, 그 다음 열에 스티커를 붙인다면 0행이라면 1행의 스티커를, 1행이라면 0행의 스티커를 붙일 수 있다.

- 해당 열에서 스티커를 붙이지 않는 경우, 같은 행의 이전 열에서 최댓값(dp)을 가져온다.

- 두가지 경우중 최댓값을 dp에 저장한다.

- dp를 스티커의 열의 개수+1 만큼 선언한다.

- dp[i][j]: i행 j열 위치까지의 스티커 점수 최댓값

스티커 점수 배열 arr //  dp[i][j]: i행 j열 위치까지의 스티커 점수 최댓값

• dp[0][1] = arr[0][1], dp[1][1] = arr[1][1]
• 0행 n열의 스티커를 붙이는 경우: dp[1][n-1] + arr[0][n]
• 0행 n열의 스티커를 붙이지 않는 경우: dp[0][n-1]
• 위 두 가지 경우 중 최댓값을 dp에 저장한다.
• dp[0][n] = max(dp[1][n-1] + arr[0][n], dp[0][n-1])
• dp[1][n] = max(dp[0][n-1] + arr[1][n], dp[1][n-1])
• 마지막 값 중 최댓값을 출력

import Foundation

let count = Int(readLine()!)!

// 2행 n열 스티커의 점수 입력받기
// dp의 인덱스 접근 편의상 맨 앞에 [0] 추가
// 해당 인덱스의 스티커를 붙이는 경우와 붙이지 않는경우 중 최댓값을 dp에 저장한다
for i in 0..<count {
    let size = Int(readLine()!)!
    var dp = Array(repeating: Array(repeating: 0, count: size+1), count: 2)
    var arr: [[Int]] = [[0] + readLine()!.split(separator: " ").map{ Int($0)! }] + [[0] + readLine()!.split(separator: " ").map{ Int($0)! }]

    dp[0][1] = arr[0][1]
    dp[1][1] = arr[1][1]
    if size == 1 {
        print(max(dp[0][size], dp[1][size]))
    } else {
        for j in 2...size {
            dp[0][j] = max(dp[1][j-1] + arr[0][j], dp[0][j-1])
            dp[1][j] = max(dp[0][j-1] + arr[1][j], dp[1][j-1])
        }
        print(max( dp[0][size], dp[1][size]))
    }
    
    
}

내가 푼 풀이

- 5 와 6은 서로 5와 6으로 변경 가능하다.

- 더했을때 최댓값은 5는 무조건 6으로 바꾸고, 최솟값은 6을 무조건 5로 바꾸면 된다.

import Foundation

let inputs = readLine()!.split(separator: " ").map{ String($0) }

var minStr1 = Array(inputs[0]).map{ String($0) }
var maxStr1 = Array(inputs[0]).map{ String($0) }
var minStr2 = Array(inputs[1]).map{ String($0) }
var maxStr2 = Array(inputs[1]).map{ String($0) }

// 최소배열은 6은 5로, 최대배열은 5는 6으로 변경
for i in 0..<minStr1.count {
    if minStr1[i] == "5" {
        maxStr1[i] = "6"
    } else if minStr1[i] == "6" {
        minStr1[i] = "5"
    }
}

for i in 0..<minStr2.count {
    if minStr2[i] == "5" {
        maxStr2[i] = "6"
    } else if minStr2[i] == "6" {
        minStr2[i] = "5"
    }
}

print("\(Int(minStr1.joined(separator: ""))! + Int(minStr2.joined(separator: ""))!) \(Int(maxStr1.joined(separator: ""))! + Int(maxStr2.joined(separator: ""))!)")

- 주어진 수업들의 시간이 겹치지 않으면 같은 강의실을 사용한다.

- 수업들의 시작시간을 오름차순으로 정렬하고, 끝나는 시간을 배열에 넣어서 시작시간보다 같거나 작으면 같은 강의실을 이용하는 방법으로

코드를 짰는데, 80퍼에서 자꾸 시간초과가 떴다.

- 수업의 갯수가 최대 20만이고, 최악의 상황으로 모든 수업이 겹친다면, 강의실도 20만 개이므로 위 같은 코드는 O(n^2)으로 시간초과가 났다.

- 위 같은 조건으로 탐색하지만, 시간초과가 나서 더 빠른방법인 우선순위큐를 이용해서 풀었다.

- 우선순위큐의 가장 앞원소는 수업의 종료시간이 가장 빠른순으로 한다.

• 수업들을 입력받아 시작시간 기준으로 정렬한다.
• 첫번째 수업의 종료시간을 우선순위 큐에 넣는다. 우선순위큐에는 수업의 종료시간이 들어가고 가장 빨리 끝나는 순으로 정렬된다.
• 다음 수업과 우선순위큐의 첫 번째 원소랑 비교한다.
• 수업의 시작시간이 첫번째 원소랑 같거나 크다면, 같은 강의실을 이용할 수 있으므로, 다음 수업의 종료시간으로 갱신한다. ( pop -> push)
• 수업의 시작시간이 첫번째 원소보다 크다면, 다른 강의실을 이용해야 하므로 우선순위큐에 해당 수업의 종료시간을 넣는다. (push)
• 모든 수업을 위 조건과 비교한 후 큐의 크기를 출력한다.

알고리즘도 맞고 예제도 맞고 하는데 자꾸 틀렸다고 나왔는데,

Swift는 힙과 우선순위 큐를 직접 구현해야 하다 보니, 사소하게 순서를 잘못 적어서 제 기능을 제대로 못하는 경우였다.

우선순위큐는 힙을 바탕으로 구현하는데, 힙은 배열로 구현하고 힙의 특성 중 가장 중요한 게 배열의 sort 기능이다.

최소힙, 최대힙이 정해질때 배열의 sort기능을 사용하는데 (T, T) -> Bool에서 인자의 순서가 중요할 줄 몰랐는데,

아무래도 { $0 < $1 }인 클로저의 첫번째 두 번째 인자를 사용하면서 순서가 중요한 듯했다.

나중에 sort 관련해서 정리해 둬야겠다. 

import Foundation

// 힙 구현
struct Heap<T: Comparable> {
    private var elements: [T] = []
    private let sortFunction: (T, T) -> Bool
    
    var isEmpty: Bool {
        return self.elements.count == 1
    }
    
    var peek: T? {
        if self.isEmpty { return nil}
        return self.elements[1]
    }
    
    var count: Int {
        return self.elements.count - 1
    }
    
    init(elements: [T] = [], sortFuntion: @escaping (T,T) -> Bool) {
        if !elements.isEmpty {
            self.elements = [elements.first!] + elements
        } else {
            self.elements = elements
        }
        self.sortFunction = sortFuntion
        if elements.count > 1 {
            self.buildHeap()
        }
    }
    
    func leftChild(of index: Int) -> Int {
        return index * 2
    }
    func rightChild(of index: Int) -> Int {
        return index * 2 + 1
    }
    func parent(of index: Int) -> Int {
        return index / 2
    }
    
    mutating func swimUp(from index: Int) {
        var index = index
        while index != 1 && self.sortFunction(self.elements[index], self.elements[self.parent(of: index)]) {
            self.elements.swapAt(index, self.parent(of: index))
            index = self.parent(of: index)
        }
    }
    
    mutating func insert(node: T) {
        if self.elements.isEmpty {
            self.elements.append(node)
            return
        }
        self.elements.append(node)
        self.swimUp(from: self.elements.endIndex - 1)
    }
    
    mutating func diveDown(from index: Int) {
        var higherPriority = index
        let leftIndex = self.leftChild(of: index)
        let rightIndex = self.rightChild(of: index)
        
        if leftIndex < self.elements.endIndex && self.sortFunction(self.elements[leftIndex], self.elements[higherPriority]) {
            higherPriority = leftIndex
        }
        
        if rightIndex < self.elements.endIndex && self.sortFunction(self.elements[rightIndex], self.elements[higherPriority]) {
            higherPriority = rightIndex
        }
        
        if higherPriority != index {
            self.elements.swapAt(higherPriority, index)
            self.diveDown(from: higherPriority)
        }
        
    }
    
    mutating func buildHeap() {
        for index in (1...(self.elements.count / 2)).reversed() {
            self.diveDown(from: index)
        }
    }
    
    mutating func remove() -> T? {
        if self.elements.isEmpty { return nil }
        self.elements.swapAt(1, elements.endIndex - 1)
        let deleted = elements.removeLast()
        self.diveDown(from: 1)
        
        return deleted
    }
    
}

// 우선순위 큐 구현
struct PriorityQueue<T: Comparable> {
    var heap: Heap<T>
    
    init(_ elements: [T] = [], _ sort: @escaping (T,T) -> Bool) {
        heap = Heap(elements: elements, sortFuntion: sort)
    }
    
    var count: Int {
        return heap.count
    }
    
    var isEmpty: Bool {
        return heap.isEmpty
    }
    
    func top() -> T? {
        return heap.peek
    }
    
    mutating func clear() {
        while !heap.isEmpty {
            heap.remove()
        }
    }
    
    mutating func pop() -> T? {
        return heap.remove()
    }
    
    mutating func push(_ element: T) {
        heap.insert(node: element)
    }
}


let count = Int(readLine()!)!
var classArr = [[Int]]()

// 수업들 입력받기
for i in 0..<count {
    let inputs = readLine()!.split(separator: " ").map{ Int($0)! }
    classArr.append(inputs)
}

// 수업의 시작시간 기준으로 정렬
// 시작시간이 같다면 종료시간이 빠른순으로 정렬
var sortedArr = classArr.sorted{
    if $0[0] == $1[0] {
        return $0[1] < $1[1] } else {
        return $0[0] < $1[0]
    }}

// 우선순위큐에 첫번째 수업의 종료시간을 넣는다.
var pq = PriorityQueue([Int]() , { $0 < $1 })
pq.push(0)
pq.push(sortedArr[0][1])

// 오름차순으로 정렬된 수업배열을 우선순위큐의 첫번째 원소와 비교
// 우선순위의 첫번째 원소와 수업의 시작시간을 비교했을때,
// 원소값 <= 수업시작시간: 같은 강의실 사용한다. 원소값 pop 후 수업의 종료시간 push
// 원소값 > 수업시작시간: 수업시간이 겹치므로 다른 강의실 사용한다. 수업의 종료시간 push
for i in 1..<sortedArr.count {
    let s = sortedArr[i][0]
    let t = sortedArr[i][1]
    
    pq.push(t)
    if pq.top()! <= s {
        pq.pop()
    }

}

print(pq.count)

출력

- 길이가 N인 수열 안의 정수끼리 서로 묶어서 합의 최댓값을 구한다.

- 수열의 합이 무조건 최대가 돼야 하고, 위치에 상관없이 묶을 수 있고, 한 번만 묶을 수 있다는 조건이 있다.

- 수열의 구성은 최대 음수, 0 , 자연수 가된다.

- 수열의 합이 최댓값이 되도록 하려면, 음수는 무조건 결합해서 양수로 만들어 줘야 하고, 양수는 높은 수끼리 곱해줘서 큰 값으로 만들어 줘야 한다.

- 또한 결합할 때 절댓값이 큰 수끼리 결합해 줘야 더 높은 수가 될 수 있다.

- 이를 적용하기 위해 수열을 따로 정렬한다.

- 0을 지워주고 0이 존재하는지만 파악한 후, 배열을 { 음수(오름차순), 자연수(내림차순) }으로 정렬한다.

- 배열의 첫 번째부터 순회하면서 조건들을 파악한다.

배열의 원소 a: arr[idx],  b: arr[idx+1], 배열 = { 음수(오름차순), 자연수(내림차순) } 

• a < 0 , b < 0 : 서로 음수이므로 결합해서 곱한다. (idx = idx + 2)
• a < 0 , b > 0 : a는 음수의 마지막값이다. 수열에서 0이 존재한다면 곱해서 0으로 만들고, 없다면 더해준다. (idx = idx + 1)
• a > 0 , b > 0 : a, b 둘 다 자연수이다. a와 b 중에서 1이 존재하는 경우 결합을 하지 않는 게 더 높은 수가 된다.
• ex) a = 5, b = 1 인경우 결합한다면 a * b = 5, 결합하지 않는다면 a + b = 6
• ex) a = 1, b = 1 인경우 결합한다면 a * b = 1, 결합하지 않는다면 a + b = 2

위에 조건대로 코드를 구현했다.

import Foundation

let count = Int(readLine()!)!
var arr1 = [Int]()
var arr2 = [Int]()
var arr = [Int]()
var sum = 0
var idx = 0
var zero = false

// 수열 입력받기
// 0은 존재하는지 bool 값으로 입력
// 음수와 양수 정렬을 위해 따로 저장
for i in 0..<count {
    let num = Int(readLine()!)!
    if num > 0 {
        arr1.append(num)
    } else if num < 0 {
        arr2.append(num)
    } else {
        zero = true
    }
}

// 양수는 내림차순으로 정렬
// 음수는 오름차순으로 정렬
// 정렬한 배열들을 합친다.
arr1.sort{ $0 > $1}
arr2.sort{ $0 < $1}
arr = arr2 + arr1

// 배열의 원소와 그 다음인덱스의 원소와 함께 비교한다.
// 원소 두개가 모두 음수라면 무조건 결합해서 양수로 만든다.
// 원소가 음수, 양수라면 0이 있다면 음수와 결합해 0으로 만들고 없다면 음수만 더한다.
// 원소가 둘다 양수라면 1이 존재하는지 파악후 존재한다면 결합하지 않는다.
// 원소가 마지막인덱스라면 그냥 더해준다.
while idx < arr.count {
    if idx + 1 < arr.endIndex {
        var num1 = arr[idx]
        var num2 = arr[idx+1]
        var comb = 0
        
        if num1 < 0 && num2 < 0 {
            comb = num1 * num2
            idx += 2
        } else if num1 < 0 && num2 > 0 {
            if zero {
                comb = 0
            } else {
                comb = num1
            }
            idx += 1
        } else {
            if num1 == 1 || num2 == 1 {
                comb = num1
                idx += 1
            } else {
                comb = num1 * num2
                idx += 2
            }
        }
        sum += comb
    } else {
        sum += arr[idx]
        idx += 1
    }
}

print(sum)

내가 푼 풀이

- 한가지의 브랜드만 구매하는 것이 아니라 각 브랜드 중 가장 싸게 구매할 때 최솟값을 구하는 것이다.

- 패키지의 줄 개수는 6개이므로 6개를 기준으로 했을 때 가장 저렴하게 구매할 방법으로 끊어진 줄의 개수를 차감해 나간다.

- 끊어진 줄의 갯수에 딱 맞게 구매하는 것이 아니라 구매한 줄이 남아도 상관없으니 6개 미만일 때도 패키지가격과 낱개가격을 비교한다.

끊어진 줄의 갯수 n일 때,

• n >= 6 일 때, 패키지와 낱개를 6개 구매한 가격 중 최솟값을 결괏값에 더한다.
• n < 6 일 때, 패키지와 낱개를 n개 구매한 가격 중 최솟값을 결괏값에 더한다.
• n이 0이 되면 결괏값 출력

import Foundation

var inputs = readLine()!.split(separator: " ").map{ Int($0)! }
var n = inputs[0]
var setPrice = [Int]()
var singlePrice = [Int]()
var result = 0

// 기타 브랜드별 패키지 가격과 낱개 가격 입력
for i in 0..<inputs[1] {
    var prices = readLine()!.split(separator: " ").map{ Int($0)! }
    setPrice.append(prices[0])
    singlePrice.append(prices[1])
}

// 패키지 기준으로 끊어진 줄의 갯수를 구매할때 최솟값 구하기
// 끊어진 줄의 갯수가 6개 이상일때 패키지와 낱개를 6개 구매한 가격을 비교
// 줄이 남아도 상관없으니 6개이하일때도 패키지와 낱개를 남은 줄만큼 구매한 가격을 비교
while n > 0 {
    var arr : [Int] = []
    if n >= 6 {
        arr = setPrice + singlePrice.map{ $0 * 6}
        result += arr.min()!
        n -= 6
    } else {
        arr = setPrice + singlePrice.map{ $0 * n}
        result += arr.min()!
        n -= n
    }
}
print(result)

내가 푼 풀이

- 이번 문제는 많이 어려웠었다

- 보석과 가방의 개수가 최대 300,000으로 O(N^2)는 시간초과가 날 꺼라 생각했다.

- 가방에는 최대 한 개의 보석만 넣을 수 있다는 조건이 핵심이다.

- 가장 비싼 보석들만 골라서 해당 보석의 무게에 알맞은 가방 중 가장 최대무게가 적은 가방에 넣으면 된다.

- 오름차순으로 정렬된 가방에 넣는다면, 최대무게가 적은 가방순으로 가장 비싼 보석을 넣게 된다.

- 무게는 최대 10억이고, 가치는 최대 100만이므로 Uint64로 최댓값을 저장한다.

- Swift는 힙과 큐를 제공하지 않으므로 직접 구현해야 한다.

- 외워두도록 해야겠다.

- Heap, PriorityQueue는 구현을 위해 사용됐고, 아래에 주요 코드들이 있다.

• 가방의 최대무게가 m일 때, m보다 낮거나 같은 무게의 보석들을 우선순위큐에 저장 (보석의 가치 저장)
• 보석의 가치가 높은 순으로 저장된 우선순위 큐에서 가장 앞의 원소는 해당하는 가방에 넣을 수 있는 보석 중 가장 가치가 높은 보석을 말한다.
• 보석을 넣고, 우선순위큐에서 pop 후, 다음 가방을 쓴다.
• 최대무게보다 높은 보석들밖에 없다면 건너뛴다.

import Foundation

struct Heap<T: Comparable> {
    private var elements: [T] = []
    private let sortFunction: (T, T) -> Bool
    
    var isEmpty: Bool {
        return self.elements.count <= 1
    }
    
    var peek: T? {
        if self.isEmpty { return nil}
        return self.elements[1]
    }
    
    var count: Int {
        return self.elements.count - 1
    }
    
    init(elements: [T] = [], sortFunction: @escaping (T,T) -> Bool) {
        if !elements.isEmpty {
            self.elements = [elements.first!] + elements
        } else {
            self.elements = elements
        }
        self.sortFunction = sortFunction
        if elements.count > 1 {
            self.buildHeap()
        }
    }
    
    func leftChild(of index: Int) -> Int {
        return index * 2
    }
    func rightChild(of index: Int) -> Int {
        return index * 2 + 1
    }
    func parent(of index: Int) -> Int {
        return index / 2
    }
    
    mutating func swimUp(from index: Int) {
        var index = index
        while index != 1 && self.sortFunction(self.elements[index], self.elements[self.parent(of: index)]) {
            self.elements.swapAt(index, self.parent(of: index))
            index = self.parent(of: index)
        }
    }
    
    mutating func insert(node: T) {
        if self.elements.isEmpty {
            self.elements.append(node)
            return
        }
        self.elements.append(node)
        self.swimUp(from: self.elements.endIndex - 1)
    }
    
    mutating func diveDown(from index: Int) {
        var higherPriority = index
        let leftIndex = self.leftChild(of: index)
        let rightIndex = self.rightChild(of: index)
        
        if leftIndex < self.elements.endIndex && self.sortFunction(self.elements[leftIndex], self.elements[higherPriority]) {
            higherPriority = leftIndex
        }
        
        if rightIndex < self.elements.endIndex && self.sortFunction(self.elements[rightIndex], self.elements[higherPriority]) {
            higherPriority = rightIndex
        }
        
        if higherPriority != index {
            self.elements.swapAt(higherPriority, index)
            self.diveDown(from: higherPriority)
        }
    }
    
    mutating func buildHeap() {
        for index in (1...(self.elements.count / 2)).reversed() {
            self.diveDown(from: index)
        }
    }
    
    mutating func remove() -> T? {
        if self.elements.isEmpty { return nil}
        self.elements.swapAt(1, elements.endIndex - 1)
        let deleted = elements.removeLast()
        self.diveDown(from: 1)
        
        return deleted
    }
}

struct PriorityQueue<T: Comparable> {
    var heap: Heap<T>
    
    init(_ elements: [T] = [], _ sort: @escaping (T,T) -> Bool) {
        heap = Heap(elements: elements, sortFunction: sort)
    }
    
    var count: Int {
        return heap.count
    }
    
    var isEmpty: Bool {
        return heap.isEmpty
    }
    
    func top () -> T? {
        return heap.peek
    }
    
    mutating func clear() {
        while !heap.isEmpty {
            heap.remove()
        }
    }
    
    mutating func pop() -> T? {
        return heap.remove()
    }
    
    mutating func push(_ element: T) {
        heap.insert(node: element)
    }
}

var inputs = readLine()!.split(separator: " ").map{ Int($0)! }
var jewelys = [(m: Int, v: Int)]()
var bags = [Int]()
var result: UInt64 = 0

// 보석들을 튜플로 입력
for i in 0..<inputs[0] {
    var num = readLine()!.split(separator: " ").map{ Int($0)! }
    jewelys.append((num[0], num[1]))
}

// 가방 입력
for i in 0..<inputs[1] {
    bags.append(Int(readLine()!)!)
}

// 보석들의 무게를 오름차순으로 정렬
// 가방의 최대무게를 오름차순으로 정렬
jewelys.sort{ $0.0 < $1.0 }
bags.sort{ $0 < $1 }

// 우선순위큐 선언 (보석의 가치가 높은순)
// 같은 보석을 넣지 않도록 Idx를 따로 선언
// 우선순위큐의 구조상 isEmpty를 사용하기위해 따로 0을 push (필수가아님)
var idx = 0
var pq = PriorityQueue([Int](), { $0 > $1})
pq.push(0)

for i in 0..<bags.count {
    
    // 보석들중에 가방의 최대무게보다 작거나 같은 보석들을 큐에 저장
    while idx < jewelys.count {
        if jewelys[idx].m <= bags[i] {
            pq.push(jewelys[idx].v)     // 우선순위큐에 보석의 가치 push
        } else {
            break
        }
        idx += 1
    }
    // 해당 가방의 최대무게보다 작거나 같은 보석이 있을경우
    // 보석중의 가장 가치가높은(우선순위큐의 제일 첫번째 원소의값)을 결과값에 저장
    // 첫번쨰원소 pop
    if !pq.isEmpty {
        result += UInt64(pq.top()!)
        pq.pop()
        
    }
}

print(result)

내가 푼 풀이

- 주어진 알파벳 대문자의 합이 최댓값이 되도록 알파벳을 숫자로 변환한다.

- 알파벳이 변환해서 어떤 숫자로 되는지보다, 결과가 최댓값이 나오면 된다.

- 단어의 합이 최댓값이 되려면 주어진 알파벳을 큰 수로 만들면 된다.

- 처음에는 알파벳의 가장 앞자리수부터 차례로 높은 수를 대입해서 풀어봤지만, 예외 조건이 있었다.

예외) AB + BC

앞자리수 부터 차례로 높은 수를 대입한다면 A: 9, B: 8, C: 7  --> AB + BC = 98 + 87 = 185

하지만 B: 9, A: 8, C: 7로 대입한다면 --> AB + BC = 89 + 97 = 186으로 최댓값은 186이 된다.

알파벳에 대입된 수 보다, 결과가 무조건 최댓값이 나와야 하므로 위 예외조건에 따르면

A의 자릿수와, B의 자릿수, C의 자릿수를 모두 나타내면 A = 10, B = 11, C= 1 이 된다.

이를 오름차순으로 정렬 후 큰 수부터 대입하면 최댓값이 나온다.

import Foundation

let count = Int(readLine()!)!
var dict = [String: Int]()
var result = 0

for i in 0..<count {
    var str = String(readLine()!)
    var strArr = str.map{ String($0)}
    
    for j in 0..<strArr.count {
        var num = 1
        for k in 1..<strArr.count-j {
            num = num * 10
        }
        if dict[strArr[j]] == nil {
            dict[strArr[j]] = num
        } else {
            dict[strArr[j]]! += num
        }
    }
    
}
var sortedDict = dict.sorted{ $0.value > $1.value }
var num = 9
for (key,value) in sortedDict {
    result = result + (value * num)
    num -= 1
}
print(result)

내가 푼 풀이

- 문제의 분류는 그리디였지만 조금 편한방법으로 풀었다.

- 연속된 하나 이상의 숫자를 뒤집을 수 있다.

- 주어진 문자열 S에서 0사이에 있는 1들의 갯수와 1사이에 있는 0들의 갯수를 구해서 둘중 최소값이 행동의 최소횟수가 된다.

• 0001100 -> ["000", "00"] , ["11"]  : 0을 1로 뒤집으면 2번 , 1을 0으로 뒤집으면 1번 뒤집게되므로 최소횟수: 1
• 11001100110011000001 -> ["00", "00", "00", "00000"] , ["11", "11", "11", "11", "1"] :
• 0을 1로 뒤집을때 4번, 1을 0으로 뒤집을때 5번이므로, 최소횟수: 4번

import Foundation

var input = readLine()!
var zero = input.split(separator: "0").count
var one = input.split(separator: "1").count
print(min(zero, one))