크게 2가지의 풀이 법이 있다. 그 중 좀 더 쉬운 방법이 분할 정복법인데, 그것도 아이디어를 떠올리기가 쉽지 않은 것 같다. 그래서 다른 분들의 풀이와 코드를 많이 참고했다.
먼저, 수가 최대 50만개라서 버블 소트를 쓰면 시간 초과가 난다.
각 숫자가 몇 번 swap 되는지를 그림으로 알아보면 다음과 같다.
각 숫자의 교점의 합이 총 swap의 합이 된다. 그리고 각 숫자의 교점의 개수는 자신보다 오른쪽에 있는 숫자들 중 더 작은 수의 개수가 된다. 예를 들어, 위의 6은 1, 3, 5 => 3번 swap 한다.
그러면 어떻게 O(n^2)보다 빠르게 각 숫자들의 오른쪽을 탐색할 수 있을까? Merge Sort를 하면 merge sort의 시간 복잡도인 O(n * log^n) 안에 가능하다.
merge sort
위의 그림은 merge sort를 하는 과정에서 가장 작은 0을 정렬한 다음 상황이다.
이제 왼쪽에서 가장 작은 2와 오른쪽에서 가장 작은 1 중 더 작은 값을 정렬해야 한다. 오른쪽 값이 더 작기 때문에 1을 정렬한다. 그리고 그 과정에서 1이 2,4,6,8과 교차되는 것을 알 수 있다. 즉, 1은 2, 4, 6, 8과 swap이 되고, swap += (왼쪽 배열 개수 - 왼쪽 인덱스)와 같은 방식으로 swap 횟수를 계산할 수 있다. 이러한 과정은 오른쪽 최소 값이 왼쪽 최소값보다 작을 때마다 적용된다.
참고로 swap 횟수는 최악의 경우 대략 50만 + ... + 1 => 50만 * 50만이 될 수 있기 때문에 Long형을 사용해야 한다!
코드
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
var count = 0L
lateinit var tempArray: IntArray
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val st = StringTokenizer(readLine())
val numbers = IntArray(n) { i ->
st.nextToken().toInt()
}
tempArray = IntArray(n)
mergeSort(numbers, 0, n-1)
print(count)
}
fun mergeSort(numbers: IntArray, start: Int, end: Int) {
if (start == end) {
return
}
val mid = (start + end) / 2
mergeSort(numbers, start, mid)
mergeSort(numbers, mid + 1, end)
merge(numbers, start, end) // 정렬된 양쪽 배열을 합치면서 다시 정렬한다
}
fun merge(numbers: IntArray, start: Int, end: Int) {
val mid = (start + end) / 2
var left = start
var right = mid + 1
var tempIndex = start
while(left <= mid && right <= end) {
// 꼭 등호는 왼쪽이 더 작거나 같은 조건으로 붙여야 한다.
// 그렇지 않으면 왼쪽과 오른쪽 값이 같을 때 1을 더 계산하게 된다.
if (numbers[left] <= numbers[right]){
// 왼쪽 값이 더 작거나 같다 -> 오른쪽 배열에 자신보다 큰 값이 없다
tempArray[tempIndex++] = numbers[left++]
}else{
tempArray[tempIndex++] = numbers[right++]
count += mid - left + 1
}
}
// 왼쪽이나 오른쪽 중 남아있는 배열의 숫자 정렬
while (left <= mid) {
tempArray[tempIndex++] = numbers[left++]
}
while (right <= end) {
tempArray[tempIndex++] = numbers[right++]
}
// 임시 배열에 정렬한 값을 원래 배열에 반영
for (i in start..end) {
numbers[i] = tempArray[i]
}
}
(3^k)꼴의 N과 3x3 패턴의 출력 형식이 주어졌을 때, 그 패턴에 맞춰 NxN 크기로 별을 출력하는 문제였다.
NxN은 (N/3) x (N/3) 크기의 영역 9개로 이루어져 있으며, 그 나누어진 영역은 다시 9개의 더 작은 영역으로 이루어져 있다. 그래서 문제에서 주어진 것처럼, 재귀적인 분할 정복 방식을 사용하여 문제를 해결할 수 있다.
9x9 = (3x3) 9개
위 그림은 N = 9일 때를 나타낸 것이다. 만약 N = 27이라면 이 그림이 9개로 이루어져 있을 것이다.
즉, NxN을 그리기 위해선 (N/3) x (N/3) 9개를 그려야 하고, N/3을 다시 나누다 보면 결국 3x3 영역부터 그리기 시작해서 전체를 그리게 된다.
참고로 영역은 배열을 사용하여,
가장 왼쪽 상단의 시작점(row, col)과 영역의 크기(size)를 통해 영역을 나타낼 수 있다.
배열, 시작점, 크기로 영역을 나타낼 수 있다
그러면 이제 NxN 패턴의 별을 그리는 재귀 함수를 선언하고, 그 안에서 크기가 3이 될 때까지 (N/3) x (N/3) 영역 9개 그리도록 재귀적으로 호출하면 문제를 해결할 수 있다.
위의 과정에서 영역을 인자로 받아서 3x3패턴의 별을 배열에 저장해주는 함수와 공백을 저장하는 함수가 추가적으로 필요하다.
시작점: (row, col), 크기: size인 별을 그리는 함수
풀이2
풀이1은 영역을 중심으로 분할해서 가장 작은 단위부터 해결하는 방식이었다. 다른 방법은 없을까 궁금해서 다른 분들의 풀이를 살펴보다가, 같은 분할 정복이지만 약간 다른 관점의 방법이 있어서 소개하려고 한다.
이 방법도 어느 영역에 속하는지가 중요하긴 하지만, 영역 자체가 아닌 각 점이 어느 영역에 속하는지 판단하여 해당 위치에 '*' 이나 ' '를 저장한다.
3x3의 빈칸
우선, 기본 단위인 3x3에서 빈칸은 각 정사각형의 1행 1열에 해당한다. 좌표는 (1,1), (1, 4), (1, 7), (1, 10), (1, 13)이며,
판별식은 (i % 3 == 1) && (j % 3 == 1)이다.
9x9에서도 1행 1열이 공백에 해당한다
9x9 패턴에서도 공백은 3x3 단위로 봤을 때 1행 1열 영역에 해당한다.
즉, N x N 패턴에서 1행 1열에 있는 (3/N) x (3/N) 영역 전부가 공백에 해당한다.
그리고 모든 크기로 확장한 판별식은 {(i / size) % 3} == 1 && {(j / size) % 3} == 1이 된다.
i / size 은 그 점이 3*size x 3*size 단위로 봤을 때, 몇 번째 행의 size x size 영역인지를 나타낸다.
예를 들어 N = 27, size = 9, i = 11, j = 0이라면,
27x27의 일부분
i / (size/3) = 3이므로 위에서 네 번째 3x3 영역에 속하며,
3 % 3 = 0이므로 9x9 영역에서 0행 0열에 있는 3x3에 속한다. 즉 1행 1열이 아니기 때문에 공백이 아닌걸 알 수 있다.
그리고 이것을 재귀적 코드로 나타내면 아래와 같다.
코드1
import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val stars = Array(n) { CharArray(n) }
setStars(stars, 0, 0, n) // NxN 패턴 별을 그린다
val answer = StringBuilder()
stars.forEach { charArray ->
charArray.forEach {
answer.append(it)
}
answer.appendLine()
}
print(answer)
}
// 왼쪽 위의 점인 stars[row][col]에서부터 size * size만큼 별 저장
fun setStars(stars: Array<CharArray>, row: Int, col: Int, size: Int) {
// 크기가 3일 때까지 나누어 들어가다가, 3이 되면 해당 영역에 3x3 패턴을 저장하고 종료한다.
if (size == 3) {
set3Pattern(stars, row, col, size)
return
}
val dividedSize = size / 3
// 0행
setStars(stars, row, col, dividedSize)
setStars(stars, row, col + dividedSize, dividedSize)
setStars(stars, row, col + 2*dividedSize, dividedSize)
// 1행
setStars(stars, row + dividedSize, col, dividedSize)
setSpace(stars, row + dividedSize, col + dividedSize, dividedSize) // 공백
setStars(stars, row + dividedSize, col + 2*dividedSize, dividedSize)
// 2행
setStars(stars, row + 2*dividedSize, col, dividedSize)
setStars(stars, row + 2*dividedSize, col + dividedSize, dividedSize)
setStars(stars, row + 2*dividedSize, col + 2*dividedSize, dividedSize)
}
// 3 * 3 패턴 별 저장
fun set3Pattern(stars: Array<CharArray>, startRow: Int, startCol: Int, size: Int) {
for (row in startRow until startRow + size){
for (col in startCol until startCol + size){
stars[row][col] = '*'
}
}
stars[startRow + 1][startCol + 1] = ' '
}
// 공백 저장
fun setSpace(stars: Array<CharArray>, startRow: Int, startCol: Int, size: Int) {
for (row in startRow until startRow + size){
for (col in startCol until startCol + size){
stars[row][col] = ' '
}
}
}
코드2
import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val answer = StringBuilder()
for (i in 0 until n) {
for (j in 0 until n) {
answer.append(getStar(i, j, n / 3)) // 위치에 해당하는 '*' or ' ' 반환
}
answer.appendLine()
}
print(answer)
}
fun getStar(row: Int, col: Int, size: Int): Char {
// 해당 위치가 (3*size) * (3*size)의 정사각형 영역 안에서,
// 가운데 영역인 (size * size) 정사각형 안에 포함될 경우
if ((row / size) % 3 == 1 && (col / size) % 3 == 1){
return ' '
}
return if (size == 1) '*'
else getStar(row, col, size / 3)
}
개인적으로 재귀 구현이 어렵게 느껴질 때가 종종 있었는데, 재귀를 공부하는 데 많은 도움이 된 것 같다.
코드 1
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.max
data class Edge(var node: Int, var distance: Int)
var answer = 0
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val tree = Array(n+1){ mutableListOf<Edge>() }
// 트리 입력
repeat(n){
val st = StringTokenizer(readLine())
val node = st.nextToken().toInt()
var adjacentNode = st.nextToken().toInt()
while(adjacentNode != -1){
val distance = st.nextToken().toInt()
tree[node].add(Edge(adjacentNode, distance))
tree[adjacentNode].add(Edge(node, distance))
adjacentNode = st.nextToken().toInt()
}
}
val visited = BooleanArray(n+1).apply{ this[1] = true }
getMaxLengthFrom(tree, 1, visited) // 지름을 찾는다
print(answer)
}
// 루트에서 리프 노드까지 중 최장 거리를 구한다
fun getMaxLengthFrom(tree: Array<MutableList<Edge>>, rooteNode: Int, visited: BooleanArray): Int {
val edgeList = tree[rooteNode]
var firstMax = 0 // 리프 노드까지 가는 가장 긴 거리
var secondMax = 0 // 2번째로 긴 거리
// 인접 노드 리스트
for (i in edgeList.indices){
val adjacentNode = edgeList[i].node
if (visited[adjacentNode]) {
continue
}
visited[adjacentNode] = true
// 인접 자식까지 거리 + 자식에서 손자까지 최장거리
val maxLength = getMaxLengthFrom(tree, adjacentNode, visited) + edgeList[i].distance
// 최대 값 갱신
if (firstMax < maxLength){
secondMax = firstMax
firstMax = maxLength
}else if (secondMax < maxLength){
secondMax = maxLength
}
}
// 각 노드를 루트로하는 (가장 긴 거리 + 2번째로 가장 긴 거리)가 지름의 후보가 된다
answer = max(answer, firstMax + secondMax) // answer 값 갱신
return firstMax
}
코드 2 (공식)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
data class Node(var node: Int, var distance: Int)
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val tree = Array(n+1) { mutableListOf<Node>() }
initTree(this, tree, n) // 트리 입력
val distance = IntArray(n+1){ -1 }.apply{ this[1] = 0} // 노드1과의 거리 + 중복 방문 체크 역할
findDiameter(distance, tree, 1) // 노드 1의 지름을 구한다
var tempDiameterNode = 0 // 노드1의 최장 노드
var tempMaxDistance = 0 // 노드1에서의 최장 거리
for (i in 1..n) {
if (tempMaxDistance < distance[i]){
tempMaxDistance = distance[i]
tempDiameterNode = i
}
}
// 거리 초기화
distance.apply {
for (i in 1..n) this[i] = -1
this[tempDiameterNode] = 0
}
findDiameter(distance, tree, tempDiameterNode) // 트리 지름 탐색
print(distance.maxOrNull())
}
fun initTree(br: BufferedReader, tree: Array<MutableList<Node>>, size: Int){
repeat(size) {
val st = StringTokenizer(br.readLine())
val node = st.nextToken().toInt()
var toNode = st.nextToken().toInt() // 인접 노드
while (toNode != -1) {
val distance = st.nextToken().toInt()
tree[node].add(Node(toNode, distance)) // 인접 리스트에 추가
toNode = st.nextToken().toInt() // 인접 노드 or -1
}
}
}
fun findDiameter(distance: IntArray, tree: Array<MutableList<Node>>, node: Int) {
val list = tree[node]
list.forEach { nextNode ->
if (distance[nextNode.node] == -1){
distance[nextNode.node] = distance[node] + nextNode.distance
findDiameter(distance, tree, nextNode.node)
}
}
}
