개발해요

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

풀이

자료구조에 관한 문제이다. 문자열을 어딘가에 저장해야 하는데, 커서의 개념이 존재하고 그걸 움직일 수도 있다. 커서에 방향이 있으므로 데이터에 순서가 있고, 추가/삭제가 쉬운 자료구조를 사용해야 한다. 따라서, 배열은 사용할 수 없고, 추가/삭제가 빠르고 데이터에 순서가 있는 연결 리스트를 생각해볼 수 있다. 

커서는 어떻게 구현할 수 있을까?

방법1) 연결 리스트

연결리스트를 응용하면 커서의 개념을 구현할 수 있다. 연결 리스트를 2개를 사용해서 커서의 왼쪽 리스트와 오른쪽 리스트의 개념으로 사용하면, 왼쪽 리스트의 끝과 오른쪽 리스트의 시작 지점 사이에 자연스럽게 커서가 생긴다. 그러면 왼쪽 리스트의 끝에 데이터를 추가/삭제할 수 있다.

ex) (왼쪽 리스트: a-b-c-d-x) - 커서 - (오른쪽 리스트: y) 

방법2) 스택

연결 리스트와 마찬가지로 왼쪽 스택과 오른쪽을 스택을 사용해서 구현할 수 있다. 양 스택의 꼭대기에 있는 데이터를 움직여서 커서를 움직이고, 왼쪽 스택의 pop/push로 커서 왼쪽에 데이터를 추가/삭제할 수 있다.

연결리스트와 차이점은 실제 문자열의 순서가 스택에 저장된 순서와 조금 다르다는 것이다. 문자열을 왼쪽에서 오른쪽으로 읽을 때, 왼쪽 스택의 바닥에서 꼭대기, 오른쪽 스택의 꼭대기에서 바닥 순서로 읽어야 한다.

방법3) listIterator

다른 사람들의 코드를 읽어보다가 문제에서 요구한 것과 완벽하게 동일한 자료구조가 자바에 존재한다는 걸 알게됐다. listIterator라는 녀석이다. Iterator 인터페이스를 상속한 것으로 Collection의 List에 사용할 수 있는데, 컬렉션의 요소에 접근, 추가, 삭제 등을 지원한다. Iterator는 정방향으로만 순회가 가능하지만 listIterator는 역방향으로도 순회가 가능하고 커서도 존재한다ㅋㅋ. 주의할 점은, 원래의 컬렉션 객체를 참조하기 때문에 Iterator에서 데이터를 추가/삭제하면 원래 객체에도 그대로 반영된다.

참고) http://www.tcpschool.com/java/java_collectionFramework_iterator 여기에 자세하게 설명되어 있다.

코드1 (연결 리스트)

import java.io.*
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    // 커서 왼쪽에 문자들 추가
    val leftList = LinkedList<String>().apply{ addAll(readLine().map{ it.toString() }) }
    val rightList = LinkedList <String>()
    val n = readLine().toInt()

    repeat(n){
        val cmd = readLine()

        when(cmd){
            "L" -> {
                if (leftList.isNotEmpty()){ // 커서 왼쪽에 문자가 있을 때
                    rightList.addFirst(leftList.pollLast())
                }
            }
            "D" -> {
                if (rightList.isNotEmpty()){ // 커서 오른쪽에 문자가 있을 때
                    leftList.addLast(rightList.pollFirst())
                }
            }
            "B" -> {
                if (leftList.isNotEmpty()){
                    leftList.removeLast() // 커서 왼쪽에 있는 문자 삭제
                }
            }
            else -> {
                leftList.add(cmd[2].toString()) // 커서 왼쪽에 문자 추가
            }
        }
    }

    val answer = StringBuilder()
    leftList.forEach { answer.append(it) } // 연결리스트는 순서대로 문자를 읽을 수 있다.
    rightList.forEach{ answer.append(it) }
    print(answer)
}

코드2 (스택: 리스트 사용)

import java.io.*
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val leftStack = readLine().map{ it.toString() }.toMutableList()
    val rightStack = mutableListOf<String>() // 리스트로 스택 구현
    val n = readLine().toInt()

    repeat(n){
        val cmd = readLine()

        when(cmd){
            "L" -> {
                if (leftStack.isNotEmpty()){
                    rightStack.add(leftStack.removeAt(leftStack.lastIndex))
                }
            }
            "D" -> {
                if (rightStack.isNotEmpty()){
                    leftStack.add(rightStack.removeAt(rightStack.lastIndex))
                }
            }
            "B" -> {
                if (leftStack.isNotEmpty()){
                    leftStack.removeAt(leftStack.lastIndex)
                }
            }
            else -> {
                leftStack.add(cmd[2].toString())
            }
        }
    }

    val answer = StringBuilder()
    leftStack.forEach { answer.append(it) }
    for (i in rightStack.lastIndex downTo 0){ // 오른쪽 스택은 top부터 문자를 읽어야 한다
        answer.append(rightStack[i])
    }
    print(answer)
}

코드3 (listIterator)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val str = readLine()
    val list = LinkedList<String>()
    str.forEach { 
        list.add(it.toString())
    }
    val iter = list.listIterator(list.size)

    val n = readLine().toInt()
    repeat(n){
        val cmd = readLine()

        when(cmd){
            "L" -> {
                if (iter.hasPrevious()){ // 커서 왼쪽에 데이터가 있으면
                    iter.previous()      // 그걸 리턴하고 커서를 반환할 데이터의 왼쪽으로 움직인다.
                }
            }
            "D" -> {
                if (iter.hasNext()){ // 커서 오른쪽에 데이터가 있으면
                    iter.next()      // 그걸 리턴하고 커서를 반환할 데이터의 오른쪽으로 움직인다.
                }
            }
            "B" -> {
                if (iter.hasPrevious()){
                    iter.previous()
                    iter.remove()   // 가장 최근에 리턴한 데이터를 삭제한다 -> 실제 리스트에도 반영된다
                }
            }
            else -> {
                iter.add(cmd[2].toString()) // 커서 위치에 데이터 추가 -> 리스트에 반영
            }
        }
    }

    val answer = StringBuilder()
    list.forEach {
        answer.append(it)
    }
    print(answer)
}

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

풀이

간단한 규칙이 있는 이차원 배열 수들 중 n번째로 큰 수를 찾는 문제였다.

공간 복잡도: 1500 *1500 * 4 byte = 9MB

시간 복잡도: 2,250,000 * log(2,250,000) = 2,250,000 * 21. ~ = 약 47,250,000

처음엔 복잡도가 충분해보였고 혹시 공간 복잡도에 문제가 있을까 싶었지만, 우선 일차원 배열을 정렬해서 답을 구해봤다. 그리고 예상외로 시간초과 판정을 받았다.

왜 시간초과가 발생했는지 찾아봤는데, 자바의 Array와 Collections의 정렬 방식이 다르기 때문이었다.
정렬의 실제 시간 복잡도는 C * 시간복잡도 + a로 알고리즘에 따라 C값이 달라지는데, Array는 퀵정렬을, Collections은 Tim 정렬이라는 걸 사용한다고 한다. 그 이유는, Array는 데이터들이 메모리에 연속적으로 존재하는 반면, list는 산발적인 연결리스트 방식으로도 존재해서 참조 지역성에 차이가 있기 때문이다. 그래서 리스트를 사용했을 때 시간 초과가 났고, IntArray로 풀어봤더니 정말로 됐다ㅋㅋ 

(자세한 내용은 https://sabarada.tistory.com/138 여기를 참고했습니다ㅋ.ㅋ)

다시 문제로 돌아와서, 고민하다가 풀이를 찾아보니 heap 또는 우선순위 큐를 사용하는 문제였다. 문제에서 주어진 배열의 크기 조건에 관계 없이 heap의 특징을 사용해서 쉽게 푸는 방법과 문제 조건을 함께 사용하는 방법이 있었고, 후자의 방법이 조금 더 빨랐다. 

참고) https://jihogrammer.tistory.com/25

방법1)

아이디어는 간단하다. 연산을 끝마쳤을 때 heap에 가장 큰 수 n개가 들어있게 만든다면, 그 중 최소 값이 n번째로 큰 수가 된다. 그러기 위해서, 최소heap에 수를 하나씩 넣는다. 그리고 크기를 n으로 유지하기 위해 최소 값을 삭제하고 새로운 숫자를 삽입하면, 연산할 때마다 최소 값이 하나씩 사라지므로 연산이 끝났을 때의 n개의 숫자들이 가장 큰 수의 집합이 된다. 

방법2)

두 번째 방법은 방법1에서 heap의 연산(logn) 횟수를 절약하는 것이다. 방법1에서는 연산을 할 때마다 heap에서 값을 빼고 넣는데, 사실 heap의 목적은 최소 값을 버림으로써 지금까지의 숫자들 중 최대 값 n개를 유지하는 것이다. 따라서, heap의 최소 값보다 작은 수는 연산할 필요가 없으므로 생략한다.

방법3)

세 번째는 heap과 더불어 문제의 조건도 함께 사용하는 방법이다. 다시 한번 말하지만, 핵심은 연산할 때마다가 아닌, 연산이 모두 끝났을 때 가장 큰 숫자 n개를 갖고 있는 것이다!

아이디어) 최대 heap을 사용한다. 처음에 heap이 전체의 최대 값을 갖고 있고, n-1번의 연산 동안 최대 값을 그 다음의 최대 값으로 교체할 수 있다면, 그때 최대heap의 값이 답이 된다.

이해하면 간단할 수도 있는데, 다이나믹 프로그래밍적인 느낌도 들고 처음부터 떠올리기엔 쉽지 않은 것 같다ㅋㅋ

구현 방법)

1. 이차원 배열에 숫자를 입력 받는다.

2. 마지막 행의 수들을 최대heap에 넣는다.

3. 그러면 heap은 처음에 가장 큰 수를 포함해서 각 열의 최대 값을 갖게 된다.

4. heap의 최대 값을 삭제한다.

5. 삭제한 값을 numbers[row][col]라고 할 때, heap에 numbers[row-1][col]을 삽입한다. 그럼 항상 모든 열의 최대 값을 heap이 갖게 되는데, 전체 수의 최대 값은 항상 모든 열의 최대 값 중 하나이다.

6. 따라서 이 연산을 n-1번 반복했을 때, 힙의 최대 값이 n번째로 큰 수가 된다.

구현을 위해선 이차원 배열에 값을 저장해놓고, 힙에 배열의 좌표를 함께 저장해야 한다. 

코드1

import java.util.*

fun main() {
    val n = readLine()!!.toInt()
    val pq = PriorityQueue<Int>() // 최소힙

    // 힙의 사이즈를 n으로 유지한다
    pq.addAll(readLine()!!.trim().split(" ").map{it.toInt()}) // 힙에 첫번째 줄 삽입
    repeat(n-1){
        val list = readLine()!!.trim().split(" ").map{ it.toInt() }
        list.forEach { number ->
            pq.offer(number)
            pq.poll()
        }
    }

    // 가장 큰 n개의 수만 남아있다
    println(pq.poll())
}

코드2

import java.util.*

fun main() {
    val n = readLine()!!.toInt()
    val pq = PriorityQueue<Int>(n) // 최소힙

    pq.addAll(readLine()!!.trim().split(" ").map{it.toInt()}) // 첫번째 줄 삽입
    
    repeat(n-1){
        val list = readLine()!!.trim().split(" ").map{ it.toInt() }
        list.forEach { number ->
            // 최대 값 n개를 유지한다 -> 힙의 최소 값보다 작은 수는 넣을 필요가 없다
            // 힙 연산 횟수를 줄이기 위해 힙의 최소 값보다 작은 수는 생략
            if (pq.peek() < number){	  
                pq.poll()
                pq.offer(number)
            }
        }
    }

    // 가장 큰 n개의 수만 남아있다
    println(pq.poll())
}

코드3

// 시간을 더 단축해보고 싶어서 StringTokenizer 사용했습니다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

data class Number(val row: Int, val column: Int, val number: Int)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val numbers = Array(n){ mutableListOf<Number>() }

    // 이차원 배열에 좌표와 함께 저장
    repeat(n){ i ->
        val st = StringTokenizer(readLine())
        for(j in 0 until n){
            val number = st.nextToken().toInt()
            numbers[i].add(Number(i, j, number))
        }
    }

    // 최대heap
    val pq = PriorityQueue<Number>(compareByDescending{it.number}).apply{
        addAll(numbers[n-1])    // 가장 큰 수가 들어있는 마지막 라인 추가
    }
    
    // 가장 큰 수를 차례대로 n-1번 꺼낸다
    repeat(n-1){
        val maxNumber = pq.poll()
        pq.add(numbers[maxNumber.row-1][maxNumber.column]) // 그 다음으로 가장 큰 수 n개 유지
    }

    println(pq.peek().number)
}

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

풀이

가장 먼저 시작되는 회의에 회의실을 배정한다. 그리고 현재 진행중인 회의들 중 가장 먼저 끝나는 회의와 다음에 시작할 회의의 시작 시간을 비교해서, 진행중인 회의의 끝나는 시간이 더 빠르다면 그 강의실에 새로 시작할 회의를 그대로 넣어준다. 반대로 새로 시작하는 시간이 더 빠르다면 새 회의실을 사용한다. 이렇게 하나씩 비교를 끝마치면, 남아있는 회의의 개수가 지금껏 사용한 회의실의 개수가 된다. 기존의 회의실만 삭제하는 경우는 없으며, 1:1로 교체하거나 추가로 생성만 하기 때문이다.

자료구조)

비교를 할 때 남아있는 회의들은 시작 시간순으로 접근하므로, 시작시간의 오름차순으로 정렬을 하고,

진행중인 회의들 중에서는 가장 빨리 끝나는 회의 하나만 꺼내서 비교하므로 끝나는 시간을 기준으로 우선순위 큐(최소힙)를 사용하면 편하게 구현할 수 있다.

우선순위 큐가 회의실이고, 회의=회의실로 생각해서 교체, 추가한다는 발상이 정말 인상적이었다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

data class Meeting(val start: Int, val end: Int)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val meetings = mutableListOf<Meeting>()
    val pq = PriorityQueue<Meeting>(compareBy{ it.end }) // 현재 진행중인 회의 저장(사용중인 회의실)

    repeat(n){
        val st = StringTokenizer(readLine())
        val meeting = Meeting(st.nextToken().toInt(), st.nextToken().toInt())
        meetings.add(meeting)
    }
    meetings.sortWith(compareBy{ it.start }) // 일찍 시작하는 순서대로 정렬

    pq.add(meetings[0])
    for (i in 1 until n){
        val prevMeeting = pq.peek()   // 진행중인 회의 중 가장 먼저 끝나는 회의
        val nextMeeting = meetings[i] // 다가올 회의 중 가장 먼저 시작하는 회의
        // 기존 회의가 먼저 끝나면 그 회의실에서 다음 회의를 진행할 수 있으므로, 기존 회의를 삭제한다
        if (prevMeeting.end <= nextMeeting.start){
            pq.poll()
        }

        pq.offer(nextMeeting)
    }

    // 회의를 1:1로 교체하거나 회의실이 부족하면 추가 회의실을 사용했기 때문에
    // 남아있는 회의의 개수 = 지금껏 사용한 회의실 개수
    println(pq.size)
}