개발해요

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

프로세스

1. 재귀(백트래킹)를 사용해서 9에서 오른쪽 or 0에서 왼쪽으로 감소/증가 하는 방향으로 감소하는 수를 모두 구한다.
2. 오름차순으로 정렬한다.
3. n > 1023이라면 -1을, 그렇지 않다면 n번째 수를 출력한다.

풀이

처음엔 앞에 있는 수로 다음 수를 구하는 것 같아서 DP를 떠올렸지만 경우의 수가 아닌 n번째 수를 구하는 방법을 생각해내지 못했다.

다음은 완전 탐색으로 풀 수 있는지 생각해본다. 수의 범위: 0 ~ 9876543210, 하지만 이 숫자를 전부 확인하면 시간 초과다. 

어떻게 해야할까

각 자릿수는 일정한 방향성을 갖는다. 왼쪽의 수가 7이라면 오른쪽에 올 수 있는 수는 6~0이다. 이 아이디어에 착안하면 재귀적으로 감소하는 수만 골라서 모두 구할 수 있다. 그리고 이것을 정렬하면 n번째 감소하는 수를 구할 수 있다.

재귀 함수의 구체적인 구현은 다음과 같다

 1. 이전 수의 마지막 자리 숫자보다 작은 수를 오른쪽에 추가해서 새로운 숫자를 구한다. -> 나머지 연산 사용

 2. 새로 구한 숫자로 재귀 함수를 호출한다

for (i in lastDigit - 1 downTo 0) {
	val newNumber = number * 10 + i  // 오른쪽에 감소하는 수 추가
	addDecreasingNumber(newNumber)
}

 3. 호출된 함수는 숫자를 감소하는 수에 추가한다

 4. 마지막 자리 수가 0이라면 재귀 함수를 종료한다.

재귀 함수 소스 코드

fun addDecreasingNumber(number: Long) {
    decreasingNumbers.add(number)

    val lastDigit = number % 10

    if (lastDigit <= 0) {
        return
    }

    for (i in lastDigit - 1 downTo 0) {
        val newNumber = number * 10 + i
        addDecreasingNumber(newNumber)
    }
}

위 방식은 왼쪽에서 오른쪽으로 숫자를 추가하면서 감소하는 방향으로 수를 구하고 있다. 반대로, 오른쪽에서 증가하는 방향으로 왼쪽에 숫자를 추가하는 방식도 가능하다.

감소하는 수를 구할 수 있을지 없을지는 어떻게 판단할까?

9 8 7 6 5 4 3 2 1 0에서 9531을 도출하는 방법을 경우의 수 관점에서 생각해볼 수 있다.

9, 5, 3, 1을 선택, 8, 7, 6, 4, 2, 0은 선택하지 않는 것이다. 각 자릿수를 선택/선택하지 않는 모든 경우의 수는 2^10개이고, 모두 선택하지 않는 경우는 없기 때문에 2^10 - 1 = 1023 개가 나온다. 따라서, n > 1022라면 감소하는 수를 구할 수 없다.

코드 (Kotlin)

1. 감소하는 방향으로 백트래킹

/**
 * 1. 백트래킹으로 0 ~ 9876543210까지 감소하는 수를 구한다
 * 2. 정렬한다
 * 3. n번째 값을 출력한다
 * 4. 정수 범위에 주의한다
 */

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.pow

val decreasingNumbers = mutableListOf<Long>()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val targetIndex = readLine().toInt()

    if (targetIndex <= 10) {
        println(targetIndex)
    } else if (targetIndex >= 1023){ // 감소하는 수의 개수는 1023개다
        println(-1)
    } else {
        for (i in 0..9) {
            addDecreasingNumber(i.toLong())
        }
        decreasingNumbers.sort()
        println(decreasingNumbers[targetIndex])
    }
}

fun addDecreasingNumber(number: Long) {
    decreasingNumbers.add(number)

    val lastDigit = number % 10

    if (lastDigit <= 0) {
        return
    }

    for (i in lastDigit - 1 downTo 0) {
        val newNumber = number * 10 + i
        addDecreasingNumber(newNumber)
    }
}

2. 증가하는 방향 

/**
 * 1. 백트래킹으로 0 ~ 9876543210까지 감소하는 수를 구한다
 * 2. 정렬한다
 * 3. n번째 값을 출력한다
 * 4. 정수 범위에 주의한다
 */

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.pow

val decreasingNumbers = mutableListOf<Long>()
    
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val targetIndex = readLine().toInt()

    if (targetIndex <= 10) {
        println(targetIndex)
    } else {
        addDecreasingNumber(0, 0, 0)
        decreasingNumbers.sort()

        if (targetIndex > decreasingNumbers.lastIndex) {
            println(-1)
        } else {
            println(decreasingNumbers[targetIndex])
        }
    }
}

fun addDecreasingNumber(startNumber: Int, beforeLength: Int, beforeNumber: Long) {
    if (beforeLength >= 10 || startNumber >= 10) {
        return
    }

    for (i in startNumber..9) {
        val newNumber = i * (10.0).pow(beforeLength).toLong() + beforeNumber
        decreasingNumbers.add(newNumber)
        addDecreasingNumber(i + 1, beforeLength + 1, newNumber)
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42587

프로세스

1. 단순 연결 리스트 사용: O(N^2)

1. 큐(연결 리스트)에서 문서를 꺼낸다. (total O(N))
2. 우선순위가 더 큰 문서가 있는지 연결 리스트의 모든 문서를 확인한다. (total O(N^2))
   1. 있다 -> 문서를 큐에 다시 넣는다.
   2. 없다 -> 문서를 출력(삭제)하고 removeCount++
3. 출력 문서 == location 문서 -> removeCount 반환

2. 우선순위 큐, 출력 확인용 배열 사용: O(NlogN)

1. 우선순위 큐(PQ)에 문서를 모두 넣는다. (total O(NlogN))
2. 큐에서 문서를 꺼낸다.
3. PQ에서 우선순위가 더 높은 문서가 있는지 확인한다. (total O(N))
   1. 우선순위 큐 제일 위에 있는 문서를 확인한다.
   2. 이미 출력한 문서라면(isPrinted 확인) PQ에서 제거하고 다시 확인한다.
   3. 더 높은 문서가 있다 -> 큐에 다시 넣는다
   4. 없다 -> 문서 출력, removeCount++, isPrinted에 체크
4. 출력한 문서 == location 문서 -> removeCount 반환

풀이

1. 연결 리스트 사용

가장 쉬운 방법은 큐에서 문서를 꺼낼 때마다 우선 순위가 더 높은 문서가 있는지 모두 확인하는 것이다. 끝에 어떤 문서서가 있을지 알 수 없어서 매번 연결 리스트를 끝까지 탐색(O(N))해야 하므로 총 O(N^2)이 걸린다. 하지만 문서가 최대 100개이므로 O(N^2)으로 해결할 수 있다. 

2. 우선순위 큐와 출력 확인용 배열 사용

우선순위 큐와 출력 확인용 배열을 사용하면 O(nlogn)으로 좀 더 빠르게 해결할 수 있다.

O(N^2)이 걸렸던 이유는 매번 다른 문서를 전부 확인해야 했기 때문이다. 따라서 다른 문서의 우선 순위를 더 빠르게 확인할 수 있다면 시간 복잡도를 줄일 수 있다. 

우선순위 큐

문서를 우선순위 큐(PQ)에 따로 넣어놓으면,  PQ의 맨 위에 있는 문서를 통해 순위가 더 높은 문서가 있는지 바로 확인이 가능하다.

val doc = queue.poll()
 // 우선 순위가 더 높은 문서가 있는지 확인
 if (doc.priority >= pq.peek().priority) {
 	removeCount++
    isPrinted[doc.id] = true
 }

하지만 문제는 문서를 출력할 때 PQ에서 해당 문서를 삭제하기가 번거롭다는 것이다. 왜냐면 맨 위에 있는 문서가 우선 순위가 같은 다른 문서일 수도 있기 때문이다. PQ에서 일일이 삭제를 할 수도 있는데, 그러면 총 O(nlogn)의 시간이 걸린다.

출력 확인 배열

좀 더 빠른 방법은 출력됐음을 확인하는 배열을 사용하는 것이다. 출력할 때 PQ에서 삭제하는 것이 아니라 배열에 체크를 하고, 다음 문서를 확인할 때 PQ의 맨 위에 있는 것이 이미 출력된 문서라면 제거하고 다음 문서를 가져온다. 이렇게 하면 PQ에서 문서를 제거하는 데 총 O(N)이 걸린다.

 // 출력된 문서 제거
while (isPrinted[pq.peek().id]) {
	pq.poll()
}

코드 (우선순위 큐)

import java.util.*

data class Document(val id: Int, val priority: Int)

class Solution {
    fun solution(priorities: IntArray, location: Int): Int {
        var removeCount = 0
        val queue: Queue<Document> = LinkedList()
        val pq = PriorityQueue(compareByDescending<Document>{it.priority})
        val documents = Array<Document>(priorities.size) { i ->
            Document(i, priorities[i])
        }
        val isPrinted = BooleanArray(documents.size)
        
        for (doc in documents) {
            queue.add(doc)
            pq.add(doc)
        }

        while(queue.isNotEmpty()) {
            
            // 출력된 문서 제거
            while (isPrinted[pq.peek().id]) {
                pq.poll()
            }

            val doc = queue.poll()

            // 우선 순위가 더 높은 문서가 있는지 확인
            if (doc.priority >= pq.peek().priority) {
                removeCount++
                isPrinted[doc.id] = true // 출력 체크

                if (doc.id == location) break
            } else {
                queue.add(doc)
            }
        }

        return removeCount
    }
}

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

프로세스

1. 완전 탐색을 떠올린다. 연산자 4개, 자리는 10개이므로 시간 복잡도(경우의 수)는 4^10 = 1,048,576이다.
2. 재귀 함수를 사용한다.
   1. calculate(왼쪽 피연산자(operand), 오른쪽 피연산자를 가리킬 인덱스)로 구성한다.
   2. 마지막 인덱스까지 계산할 때마다 최대 값, 최소 값을 갱신한다.
   3. 각 연산자마다 operand와 현재 피연산자를 계산해서 재귀함수를 호출한다.

풀이

어렵지 않았지만 재귀 함수를 연습하기 좋았다.

가장 먼저 완전 탐색을 떠올릴 수 있는데, 연산자 들어갈 자리가 최대 10자리이고 연산자가 4개 뿐이다. 따라서 모든 자리에 연산자를 한 번씩 넣어서 모든 경우의 수를 확인할 경우 4^10 = 1,048,576개 라서 충분히 완전 탐색으로 해결할 수 있다.

재귀 함수

재귀 함수 구성은 배열 1 2 3 4 5 6이 있다고 가정했을 때, (1 2) (연산자) (3 4 5 6)와 같이 나눌 수 있다. 즉, 지금까지 계산한 왼쪽 피연산자와 배열의 나머지에서 그 다음에 계산할 숫자의 현재 인덱스를 인자로 갖게 한다.

fun calculate(operand1: Int, idx: Int)

그리고 인덱스가 마지막 인덱스를 넘으면 전부 계산한 것이기 때문에 최대 값, 최소 값과 비교하여 정답을 갱신한다.

if (idx >= numbers.size) {
        maxValue = max(maxValue, operand1)
        minValue = min(minValue, operand1)
        return
    }

종료 조건이 아니라면, 각 연산자마다 계산해서 다음 자리에 해당하는 연산자를 넣어보기 위해 재귀 함수를 호출한다.

 for (i in operators.indices) {
        if (operators[i] <= 0) continue

        operators[i]--
        when(i) {
            0 -> calculate(operand1 + numbers[idx], idx + 1)
            1 -> calculate(operand1 - numbers[idx], idx + 1)
            2 -> calculate(operand1 * numbers[idx], idx + 1)
            else -> {
                if (operand1 < 0) {
                    calculate(-(-operand1 / numbers[idx]), idx + 1)
                } else {
                    calculate(operand1 / numbers[idx], idx + 1)
                }
            }
        }
        operators[i]++
    }

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.max
import kotlin.math.min

lateinit var numbers: IntArray
lateinit var operators: IntArray // +, -, *, /
var maxValue = Int.MIN_VALUE
var minValue = Int.MAX_VALUE

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val size = readLine().toInt()
    numbers = with(StringTokenizer(readLine())) {
        IntArray(size) { this.nextToken().toInt() }
    }
    operators = with(StringTokenizer(readLine())) {
        IntArray(4) { this.nextToken().toInt() }
    }

    calculate(numbers[0], 1)

    println(maxValue)
    println(minValue)
}

fun calculate(operand1: Int, idx: Int) {
    if (idx >= numbers.size) {
        maxValue = max(maxValue, operand1)
        minValue = min(minValue, operand1)
        return
    }

    for (i in operators.indices) {
        if (operators[i] <= 0) continue

        operators[i]--
        when(i) {
            0 -> calculate(operand1 + numbers[idx], idx + 1)
            1 -> calculate(operand1 - numbers[idx], idx + 1)
            2 -> calculate(operand1 * numbers[idx], idx + 1)
            else -> {
                if (operand1 < 0) {
                    calculate(-(-operand1 / numbers[idx]), idx + 1)
                } else {
                    calculate(operand1 / numbers[idx], idx + 1)
                }
            }
        }
        operators[i]++
    }
}

https://programmers.co.kr/learn/courses/30/lessons/87694

처음에 어떻게 풀어야 할지 감이 안 와서 고민해보다가 다른 분들의 힌트를 봤다. 생활 패턴 고친다고 밤을 새워서 그런지(핑계 맞음ㅎㅎ) 봐도 무슨 말인지 모르겠더라. 짐 싸서 집 가는 길에 백준에서 비슷한 문제를 풀었던 기억이 갑자기 떠올랐다ㅋㅋ. 신기하게도 샤워하거나 산책하면 아이디어가 잘 떠오르는데, 이유는 뭘까?

아무튼 DFS나 BFS로 풀 수 있다는 것까진 알았는데, 이번엔 어떻게 테두리만 표시할지 떠오르지 않았다. 결국 다른 분의 풀이를 봤는데, 대단한 사고력이 필요하진 않았고 오히려 방법이 단순했다. 최근에 코테 실력이 많이 는 것 같아서 "나 이제 코테 좀 치나?ㅋㅋ" 싶었는데, 반성했다.

결론적으론 나에게 어려운 문제였다.

요약

1. 좌표 및 사각형 영역을 2배로 늘린다
2. 그래프에 모든 사각형의 테두리를 표시한다. (1 vs 0 or true vs false)
3. 사각형의 테두리를 제외한 안쪽 영역(너비)을 빈공간으로 표시한다.
4. 테두리 전체 길이(S)와 시작점에서 도착점(src- dst)까지의 길이를 각각 구한다.
5. 정답: min(S - (src - dst), src - dst)

풀이

1. DFS/BFS로 해결할 수 있다

그래프를 점과 빈공간으로 표시할 때, 테두리만을 나타낼 수 있으면 시작점에서 도착점까지 얼마나 이동했는지를 DFS/BFS로 알 수 있다.

2. 좌표를 늘린다!

테두리를 따라가려면 인접한 1을 탐색하면 된다. 하지만 테두리간 거리가 1이면 위와 같은 상황에서 테두리를 잘못 따라갈 수 있다. 따라서, 좌표를 모두 2배로 늘려서 위와 같은 문제를 예방한다.

3. 어떻게 바깥의 테두리만 표시할 수 있을까?

1. 우선 모든 사각형의 테두리를 표시한다.

2. 테두리 안쪽 영역을 빈공간으로 표시한다. 그럼 사각형에 포함되어 있던 테두리가 제거된다.

코드

class Solution {
    static final int SIZE = 101;
    static boolean[][] board = new boolean[SIZE][SIZE]; // true: 점 

    int[] dR = new int[]{-1, 1, 0, 0};
    int[] dC = new int[]{0, 0, -1, 1};

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        // 좌표 2배로 늘리기
        int srcRow = characterY * 2;
        int srcCol = characterX * 2;
        int dstRow = itemY * 2;
        int dstCol = itemX * 2;

        markRect(rectangle); // 그래프에 사각형 테두리만 표시
        
        // + 1: 마지막 위치에서 시작점으로 돌아온 거리
        int totalDistance = findDistance(srcRow, srcCol, srcRow, srcCol, new boolean[SIZE][SIZE], 0) + 1; 
        int distance = findDistance(srcRow, srcCol, dstRow, dstCol, new boolean[SIZE][SIZE], 0);

        return Math.min(distance, totalDistance - distance) / 2;
    }

    private void markRect(int[][] rectangles) {
        for (int[] rect: rectangles) {
            int firstRow = 2* rect[1];
            int firstCol = 2* rect[0];
            int secondRow = 2* rect[3];
            int secondCol = 2* rect[2];

            markEdge(firstRow, firstCol, secondRow, secondCol);
        }

        for (int[] rect: rectangles) {
            int firstRow = 2* rect[1];
            int firstCol = 2* rect[0];
            int secondRow = 2* rect[3];
            int secondCol = 2* rect[2];

            markSpace(firstRow, firstCol, secondRow, secondCol);
        }
    }

    // 그래프에 테두리 모두 표시
    private void markEdge(int firstRow, int firstCol, int secondRow, int secondCol) {
        for(int row = firstRow; row <= secondRow; row++) {
            board[row][firstCol] = true;
        }
        for(int col = firstCol + 1; col <= secondCol; col++) {
            board[secondRow][col] = true;
        }
        for(int row = secondRow - 1; row >= firstRow; row--) {
            board[row][secondCol] = true;
        }
        for (int col = secondCol - 1; col > firstCol; col--) {
            board[firstRow][col] = true;
        }
    }

    // 테두리를 제외한 사각형 너비 영역을 모두 빈공간으로 표시한다
    private void markSpace(int firstRow, int firstCol, int secondRow, int secondCol) {
        for (int row = firstRow + 1; row < secondRow; row++) {
            for (int col = firstCol + 1; col < secondCol; col++) {
                board[row][col] = false;
            }
        }
    }

    // DFS
    private int findDistance(int row, int col, final int dstRow, final int dstCol, final boolean[][] visited, int count) {
        if (count > 0 && row == dstRow && col == dstCol) {
            return count;
        }

        visited[row][col] = true;

        for (int i = 0; i < 4; i++) {
            int newRow = row + dR[i];
            int newCol = col + dC[i];

            if (newRow >= 0 && newRow < SIZE && newCol >= 0 && newCol < SIZE && board[newRow][newCol] && !visited[newRow][newCol]) {
                return findDistance(newRow, newCol, dstRow, dstCol, visited, count+1);
            }
        }

        return count;
    }
}