https://programmers.co.kr/learn/courses/30/lessons/81303
코딩테스트 연습 - 표 편집
8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO"
programmers.co.kr
풀이1
처음에 스택을 활용한 커서 구현 방법과 배열에 삭제 여부를 표시하는 방식을 사용해서 정확도는 통과할 수 있었지만, 효율성 테스트에서 문제가 있었다. 두 가지 방법 모두 삭제된 행을 복구할 때 O(N)이 소요됨에 따라 명령어 * 전체 행 = 약 2000억 번의 연산이 필요하기 때문이다. 커서를 움직이는 숫자의 합은 100만 이하라고 주어졌기 때문에, 복구하는데 걸리는 시간을 줄여야 효율성 테스트를 통과할 수 있다. 그리고 연결 리스트를 사용하면 O(1)으로 해결할 수 있다.
그림과 같이 연결리스트를 사용해서 삭제한 행을 스택에 저장하면, 삭제 과정이 연결리스트의 삽입과 같아진다.
그리고 항상 최근에 삭제된 행부터 복구하기 때문에, 삭제가 된 이후의 커서 이동이나 삭제는 신경쓰지 않고 이전 상태 그대로 복구할 수 있다. 단, 삭제하거나 복구할 때 양 끝의 행인지만 주의하면 된다!
풀이 2
삭제/복구 동작을 유심히 살펴보면 재밌는 사실을 발견할 수 있는데, 행을 삭제하더라도 cursor의 인덱스는 같다는 것이다.
ex)
0-1-2-3-4, cursor: 3, size: 5
----삭제----
0-1-2-4, cursor: 3(4를 가리킴), size: 4, stack: 3
즉, cursor의 인덱스와 행의 개수만으로 차트를 표현할 수 있다. 단, 마지막 행을 삭제했을 때는 cursor -= 1을 해주어야 하는데, 이것도 실제 삭제 동작과 같다.
ex)
0-1-2-3-4, cursor: 4, size: 5
----삭제----
0-1-2-3, cursor: 4 - 1 = 3, size: 5, stack: 4
복구할 때는 행의 개수를 다시 증가시키고, 만약 현재 cursor의 인덱스가 복구하려는 행의 인덱스보다 크거나 같으면 cursor += 1을 해준다. 왜냐면 아래로 밀어야 하기 때문이다.
ex)
0-1-2-4, cursor: 3 (4를 가리킴), size: 4, stack: 3
----복구----
0-1-2-3-4, cursor: 3 + 1 = 4, size: 5
이런 풀이도 있다 정도로 알면 좋을 것 같습니다.
코드2를 참고해주세요!
코드1 (연결 리스트 사용)
import java.util.*
// 행 넘버, 위에 행, 아래 행, 삭제 여부
data class Row(val number: Int, var prev: Row? = null, var next: Row? = null, var state: Char = 'O')
class Solution {
fun solution(n: Int, k: Int, cmd: Array<String>): String {
val rowArray = Array<Row>(n) { i -> Row(i) }
for (i in 0 until n-1) { // 앞으로 연결
rowArray[i].next = rowArray[i+1]
}
for (i in 1 until n){ // 뒤로 연결
rowArray[i].prev = rowArray[i-1]
}
var cursor = rowArray[k]
val removeStack = Stack<Row>()
cmd.forEach {
when (it[0]) {
'U' -> {
val prevStep = it.split(" ")[1].toInt()
repeat(prevStep) {
cursor = cursor.prev!!
}
}
'D' -> {
val nextStep = it.split(" ")[1].toInt()
repeat(nextStep) {
cursor = cursor.next!!
}
}
'C' -> {
val removeRow = cursor
val prevRow = cursor.prev
val nextRow = cursor.next
removeStack.push(removeRow)
removeRow.state = 'X' // 삭제 표시
if (nextRow == null) { // 삭제될 행이 마지막 행인 경우
cursor = prevRow!!
prevRow.next = null
}else{
cursor = nextRow
nextRow.prev = prevRow
// 첫번째 행을 삭제하는 경우를 고려하지 않으면 NullPointerexception 발생
if (prevRow != null) prevRow.next = nextRow
}
}
else -> {
val removedRow = removeStack.pop()
val prevRow = removedRow.prev
val nextRow = removedRow.next
removedRow.state = 'O'
if (nextRow == null){ // 마지막 행이었던 경우
prevRow!!.next = removedRow
}else{
nextRow.prev = removedRow
if (prevRow != null) prevRow.next = removedRow
}
}
}
}
// 배열에 저장하지 않고 head, tail을 사용해서
// 스택에 남아있는 행들을 다시 삽입한 후
// head부터 순서대로 출력할 수도 있습니다.
val answer = StringBuilder()
rowArray.forEach {
answer.append(it.state)
}
return answer.toString()
}
}
코드2 (cursor랑 size로 차트 표현)
import java.util.*
class Solution {
fun solution(n: Int, k: Int, cmd: Array<String>): String {
var cursor = k
var size = n
val removeStack = Stack<Int>()
cmd.forEach {
when (it[0]) {
'U' -> {
val step = it.split(" ")[1].toInt()
cursor -= step
}
'D' -> {
val step = it.split(" ")[1].toInt()
cursor += step
}
'C' -> {
removeStack.push(cursor)
size -= 1
if (cursor == size) cursor--
}
else -> {
val comebackRow = removeStack.pop()
size += 1
if (comebackRow <= cursor) cursor++
}
}
}
val answer = StringBuilder()
for (i in 0 until size) answer.append('O') // 살아있는 행 먼저 표시
while (removeStack.isNotEmpty()) {
val removedRow = removeStack.pop() // 연결리스트의 삽입과 같다
answer.insert(removedRow, 'X')
}
return answer.toString()
}
}'Problem Solving > 프로그래머스' 카테고리의 다른 글
| 프로그래머스: 프린터 (Kotlin) (0) | 2022.03.31 |
|---|---|
| (Java) 프로그래머스 - 아이템 줍기 (0) | 2022.03.12 |
| [프로그래머스] 순위 (Kotlin) - 플로이드 와샬 사용하지 않고 풀기 (0) | 2022.02.14 |
| (Kotlin) 프로그래머스 - 오픈채팅방 [2019 KAKAO BLIND RECRUITMENT] (0) | 2021.08.23 |
| (Kotlin) 프로그래머스 - 키패드 누르기 [2020 카카오 인턴십] (0) | 2021.08.22 |
