[2023-04-10] 5430 AC(Kotlin) +1 문제

 

어떻게 하면 시간복잡도를 줄일 수 있을까 많이 고민했던 문제였습니다.

 

효율적으로 코드를 짜는데 많이 도움 될 것 같아요.

 

 

문제 링크: https://www.acmicpc.net/problem/5430

5430번: AC

 

첫 번째 시도

 

val temp = LinkedList<Int>()
queue.forEach{i->
    temp.add(i)
}
queue.clear()
while(temp.isNotEmpty()){
    queue.add(temp.removeLast())
}

 

입력받은 문자열에 loop문을 돌려, 해당 문자가 R일 때마다

 

위와 같이 역순으로 정렬을 해주었습니다.

 

queue.reversed()

 

 

reversed() 매소드를 사용하여 역순으로 정렬하는 방법도 시도를 해봤습니다.

 

두 방법 모두 시간초과가 떴습니다.

 

 

 

두 번째 시도

 

 

배열의 최대 개수가 100,000개이므로,

 

함부로 reverse() 매소드를 사용하면 안되겠다고 생각을 했습니다.

 

고민하던 중, 굳이 정렬을 하지 않아도 됨을 깨달았습니다.

 

 

R의 개수가 짝수이면 가장 앞의 요소를 제거하고,

 

R의 개수가 홀수이면 가장 뒤의 요소를 제거하였습니다.

 

 

isError 라는 boolean 형 변수를 선언하여,

 

deque가 비었을 때 D 연산을 수행할 때나, 입력받은 n값이 0일 때 true로 설정해주었습니다.

 

 

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val t = br.readLine().toInt()
    var isError = false
    repeat(t){
        val queue = LinkedList<String>()
        val function = br.readLine()
        val n = br.readLine().toInt()
        
        if (n == 0){
            val list = br.readLine()
            isError = true
        }
        else{
            val list = br.readLine().split('[', ']')[1].split(',')
            list.forEach{
                queue.add(it)} // queue에 배열 요소 추가
        }
        
        var rCount = 0 // R의 개수
        
        function.forEach{
        
            if (it == 'R')
                rCount ++
            else{
                if (queue.isEmpty()){
                    isError = true
                }
                else{
                    if (rCount % 2 == 0){ // R개수가 짝수일 때
                        queue.removeFirst() // 앞의 요소 제거
                        rCount = 0
                    }
                    else // 홀수일 때 뒤의 요소 제거
                        queue.removeLast()
                }
            }
        }
        
        if (isError) // isError 가 true 이면 error 출력
            println("error")
            
        else {
        // 남은 R 개수가 짝수이면 그대로 출력
            if (rCount % 2 == 0){
                println(queue.joinToString(",","[","]"))
            }
            else{
            // 홀수이면 역순으로 출력
                queue.reverse()
                println(queue.joinToString(",","[","]"))
            }
        }
        // 변수 초기화
        isError = false
        rCount = 0
    }
}

 

시간초과가 뜨지 않았지만,

 

틀렸다는 결과가 나왔습니다.

 

계산 논리는 맞다고 생각을 했기 때문에, 많은 삽질을 했습니다.

 

 

 

고민을 해보다, 예외 상황을 찾을 수 있었습니다.

 

n이 0이고 함수가 R 일 경우 error가 뜨지 않아야 합니다.

 

 

if (n == 0){
    val list = br.readLine()
    isError = true
}

 

 

다음과 같이 n이 0일 때, 에러를 출력하게끔 작성해 놓은 것이 원인이였습니다.

 

 

 

성공 코드입니다.

 

package tenthDay
import java.io.*
import java.util.*

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val t = br.readLine().toInt()
    var isError = false
    repeat(t){
        val queue = LinkedList<String>()
        val function = br.readLine()
        val n = br.readLine().toInt()
        if (n == 0){
            val list = br.readLine()
        }
        else{
            val list = br.readLine().split('[', ']')[1].split(',')
            list.forEach{
                queue.add(it)}
        }
        var rCount = 0
        function.forEach{
            if (it == 'R')
                rCount ++
            
            else{
                if (queue.isEmpty()){
                    isError = true
                }
                
                else{
                    if (rCount % 2 == 0){
                        queue.removeFirst()
                        rCount = 0
                    }
                    else
                        queue.removeLast()
                }
            }
        }
        
        if (isError)
            println("error")
        
        else {
            if (rCount % 2 == 0){
                println(queue.joinToString(",","[","]"))
            }
            else{
                queue.reverse()
                println(queue.joinToString(",","[","]"))
            }
        }
        
        isError = false
        rCount = 0
    }
}

 

 

너무 많이 시도를 했네요