2024-03-27

https://hifumialice.tistory.com/17

어제 문제 하나가 안풀려서 풀고 돌아 오겠다고 했다...

문제를 풀었기에 과정을 적어보려고 한다.

코틀린으로 문제를 풀었다.

 

과정

문제 풀이 아이디어

1. 재료가 순서대로 1,2,3,1이 나온다면 데이터의 인덱스에 접근해서 저 값을 순서대로 지운다.

2. 맨 처음부터 다시 탐색한다.

3. 1,2 과정을 반복하면서 더 이상 완성이 불가능 하면 끝낸다.

 

맨 처음에는 intArray 자료형으로 데이터를 받았을 때 함수의 파라미터는 수정이 안되기에 MutableList<Int>형으로 자료를 변환 하고 문제를 풀었다. 그러나 시간초과가 떳다.

다음 StringBuilder 자료형으로 바꿔서 문제를 풀었다. 이 역시 시간 초과가 떳다.

풀이는 맞는 것 같은데 자꾸 시간 초과가 되기에 완성이 된 경우 처음부터 찾기가 아닌 1이 있는 처음 위치부터 찾기로 했다. 이 역시 계속 시간초과가 떳다..

 

이번에는 자료형을 바꾸는 것이 시간을 많이 먹는다고 생각해서 파라미터로 받은 데이터를 계속 써보자고 생각헀다.

1. 재료가 1,2,3,1이 연속으로 있다면 재료가 있는 인덱스를 새로운 배열에 저장한다.

2. 처음으로 돌아가서 다시 탐색을 진행하고 만약 새로운 배열에 인덱스가 있다면 건너 뛴다.

3. 재료의 인덱스가 1씩 차이가 나거나 새로운 배열의 길이를 더한 것 만큼 차이가 나면 완성이 가능하다.

4. 위 과정을 반복한다.

를 생각하고 짯으나 이 역시 시간 초과가 발생하고 문제가 제대로 안풀리는 경우도 있다.

그러던 중 풀이시간을 확인해본 결과 StringBilder로 푼 것이 인덱스를 저장해서 푸는 것보다 훨씬 더 빨랐다.

따라서 인덱스를 저장해서 푸는것 또한 제대로 완성한다 해도 어짜피 시간 초과가 발생한다.

이유를 생각해보니 인덱스를 저장한다고 해도 인덱스가 있는지 확인해봐야하고 또한 데이터가 원본 그대로 남아있기에 반복해야하는 회수는 동일하다.

따라서 오래 걸리는 것이다.

 

그럼 어떻게 문제를 풀어야 할까 고민을 계속 해봤다.

StringBuilder 자료형으로 바꿀 때 처음부터 재료가 완성이 되는지 확인을 해서 완성이 안되는 경우만 담으면 되지 않을까 생각했다. 그럼 데이터의 손을 봐야하는데 파라미터는 수정이 안되기에 안될거 같았다.

다시 한번 생각을 해보니 StringBuilder에 데이터를 하나씩 담아 갈 때 StringBulider 변수에 재료가 순서대로 있는 경우를 찾으면 된다고 생각하고 문제를 풀었다. 그러니 모든 문제가 시간초과도 없고 빠르게 풀렸다.

이때 들었던 생각이 너무 하나에 대해 생각하는 것 보다 다양한 방식으로 사고의 전환이 필요하다는 것이였다.

파라미터를 건들지 못한다고 단순히 끝낼 것이 아니라 데이터를 옮기면서 완성이 되는 경우를 찾는다 라는 생각을 했더라면 금방 풀었을 문제를 계속 한번에 옮기거나 파라미터만 건드릴 생각만 하니 반나절이나 문제를 푼거 같다.

 

풀이 코드를 적어 보겠다.

class Solution {
    fun solution(ingredient: IntArray): Int {
        var answer: Int = 0
        var sb = StringBuilder()
        var idx = 0
        for (i in ingredient)
        {
            sb.append(i)
            if(sb.length > 3 && i == 1)
            {
                idx = sb.lastIndexOf('1')
                if(sb[idx-1] == '3' && sb[idx-2] == '2' && sb[idx-3] == '1')
                {
                    // println(idx)
                    sb.delete(idx-3,idx+1)
                    answer += 1
                }
            }
        }
        return answer
    }
}