[백준/Swift] 17140번: 이차원 배열과 연산

 

https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

 

맨 처음에 101x101 사이즈로 2차원 배열을 생성해 줬다. (out of index를 방지하기 위해...)

100회까지 진행하고 넘어서면 -1를 출력하고 끝내야 하므로 while문에서,

- answer가 100을 넘어서면 종료

- array[r][c] == k면 종료

 

R 연산과 C 연산을 나눠서 진행하면 되는데, 사실 R 연산과 C 연산은 행과 열만 다르지 거의 같다.

 

1. 행/열에 나타나는 수의 개수를 세야 하는데, 이는 dictionary에 저장하면 편하다.

2. 그 후, dictionary를 정렬해주고 (개수가 적은 순으로 오름차순, 같다면 수가 적은 순으로 오름차순)

3. array에 dictionary의 key, value를 차례대로 넣어주면 된다. 여기서 들어갈 곳이 100을 넘어서면 빠져나온다. 

4. 가장 긴 행/열의 길이를 담고 있는 row/col의 값을 업데이트 해준다.

5. (중요) 이전 값이 남아있을 수 있으므로 넣어준 곳 다음은 0으로 바꿔준다. 

    3 | 3 | 3 -> 3 | 3으로 변하기 때문에 마지막 3의 인덱스는 0으로 바꿔줘야 한다.

 

 

import Foundation

/*
 3x3 배열 A. 인덱스는 1부터 시작. 1초 지날때마다 연산 적용
 - R 연산: 모든 행 정렬 (행개수 >= 열개수의 경우)
 - C 연산: 모든 열 정렬 (행개수 <  열개수의 경우)
 한 행 또는 열에 있는 수를 정렬하려면, 각 수가 몇 번 나왔는지 알아야 함. (0은 무시)
 수의 등장 횟수가 커지는 순으로, 수가 커지는 순으로 정렬
 배열 A에 정렬된 결과를 다시 넣기 (수와 등장 횟수 모두)
 */

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let r = input[0] - 1
let c = input[1] - 1
let k = input[2]
var array = [[Int]](repeating: [Int](repeating: 0, count: 101), count: 101)
for i in 0..<3 {
    let num = readLine()!.split(separator: " ").map{ Int(String($0))! }
    array[i][0] = num[0]
    array[i][1] = num[1]
    array[i][2] = num[2]
}

var col = 3
var row = 3
var answer = 0

while true {
    if array[r][c] == k {
        print(answer)
        break
    }
    if answer > 100 { //100번 넘어가면 종료
        print(-1)
        break
    }
    
    if col <= row { //R operation
        for i in 0..<row { //행마다
            var dictionary = [Int:Int]()
            for j in 0..<col {
                if array[i][j] == 0 { continue } //0이면 넘어감
                dictionary[array[i][j]] = (dictionary[array[i][j]] ?? 0) + 1
            }
            let sortedDictionary = dictionary.sorted { a, b in //정렬
                if a.value == b.value {
                    return a.key < b.key
                }
                return a.value < b.value
            }
            var index = 0
            for dictionary in sortedDictionary {
                if index >= 99 { break } //100 넘어가면 자름
                array[i][index] = dictionary.key
                index += 1
                array[i][index] = dictionary.value
                index += 1
            }
            col = max(col, index)
            //나머지 0으로 바꾸기
            for j in index..<100 {
                array[i][j] = 0
            }
        }
    } else { //C operation
        for i in 0..<col { //열마다
            var dictionary = [Int:Int]()
            for j in 0..<row {
                if array[j][i] == 0 { continue }
                dictionary[array[j][i]] = (dictionary[array[j][i]] ?? 0) + 1
            }
            let sortedDictionary = dictionary.sorted { a, b in
                if a.value == b.value {
                    return a.key < b.key
                }
                return a.value < b.value
            }
            var index = 0
            for dictionary in sortedDictionary {
                if index >= 99 { break } //100 넘어가면 자름
                array[index][i] = dictionary.key
                index += 1
                array[index][i] = dictionary.value
                index += 1
            }
            row = max(row, index)
            //나머지 0으로 바꾸기
            for j in index..<100 {
                array[j][i] = 0
            }
        }
    }
    answer += 1
}

 

 

생각보다 많이 헤맨 문제.. 

역시 문제를 많이 풀어보고 구현능력, 문제 풀이 능력을 키워야겠다..ㅠ