36일차)알고리즘 문제(모음사전, 안티세포**중요!!)

>알고리즘 문제

 

1. 모음사전

1)문제

문제 설명

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• word의 길이는 1 이상 5 이하입니다.
• word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

2)솔루션

class Solution {
    fun solution(word: String): Int {
        var answer = 1
        //AXXXX부터 시작
        //순서는 X A E I O U순
        var str=charArrayOf('A','X','X','X','X')
        try{
            while(true){
            
                if(word==str.joinToString().replace(", ", "").replace("X","")) return answer

                var idx=4
                while(true){
                    if(str[idx-1]=='X') idx--
                    else break
                }
                while(true){
                    str[idx]=when(str[idx]){
                        'X' -> 'A'
                        'A' -> 'E' 
                        'E' -> 'I'
                        'I' -> 'O'
                        'O' -> 'U'
                        else ->'X'
                    }
                    if(str[idx]=='X'){
                        idx--
                    }else{
                        break
                    }
                } 
                answer++
            }
        }catch(e:Exception){
            println("${str}")
        }
        
        return answer
    }
}

 

 

 

2. 안티세포

1)문제

당신에게 자연수로 이루어진 길이가 n인 배열 b가 주어집니다. 초기에는 모든 수들이 "안티 세포" 안에 들어있습니다. 일반적인 세포는 분열을 하지만, 이 안티 세포는 반대로 여러 안티 세포가 모여 합성을 합니다. 당신은 다음과 같은 과정을 통해 인접한 두 안티 세포를 합치거나 또는 그대로 두려고 합니다.

1. i=0로 설정하고, 빈 배열 c를 하나 만듭니다.
2. i가 n이라면 과정을 종료합니다.
3. b[i]를 포함하는 안티 세포를 X, 그리고 X 바로 왼쪽에 있는 안티 세포를 Y라고 정의합니다. 만약 Y가 존재하고 X의 모든 숫자의 합과 Y의 모든 숫자의 합이 같다면, 당신은 이 두 안티 세포를 합치거나 합치지 않는 행동 중에서 하나를 선택할 수 있습니다.
   1. 만약 X와 Y를 합친다면, 둘을 합치고, c의 맨 뒤에 i를 추가한 뒤 다시 3번 과정으로 돌아갑니다.
   2. 만약 X와 Y를 합치지 않는다면(또는 Y가 존재하지 않는다면), i를 1 증가시키고 2번 과정으로 돌아갑니다.

예를 들어, 다음은 b = [1,1,1,1]일 때 위와 같은 과정을 거치는 것을 나타낸 것입니다.

  i    안티세포      c       비고

0	(1)(1)(1)(1)	[]	초기 상태입니다.
1	(1)(1)(1)(1)	[]	i=0 일 때는 Y가 존재하지 않으므로 i를 1 증가시켰습니다.
1	(1,1)(1)(1)	[1]	b[1]을 포함하는 안티 세포(X)와 그 왼쪽의 안티 세포(Y)를 합쳤습니다. 따라서 c에 i=1이 추가됩니다.
2	(1,1)(1)(1)	[1]	b[1]을 포함하는 안티 세포(X) 왼쪽의 안티 세포 Y가 존재하지 않으므로 i를 1 증가시켰습니다.
3	(1,1)(1)(1)	[1]	X의 모든 수의 합은 1이고, Y의 모든 수의 합은 2이므로, 둘은 합칠 수 없습니다. 따라서 i을 1 증가시켰습니다.
3	(1,1)(1,1)	[1,3]	b[3]을 포함하는 안티 세포(X)와 그 왼쪽의 안티 세포(Y)를 합쳤습니다. 따라서 c에 i=3이 추가됩니다.
4	(1,1)(1,1)	[1,3]	b[3]을 포함하는 안티 세포(X)와 그 왼쪽의 안티 세포(Y)를 합칠 수 있었지만 그러지 않았습니다. 따라서 i를 1 증가시켰습니다.

이 경우 c = [1,3]이 됩니다. 물론 이는 c를 만들 수 있는 하나의 경우일 뿐이며, 당신의 선택에 따라 [], [1], [3], [1,3], [2], [1,3,3]으로 c배열을 다양하게 만들 수 있습니다. 당신이 어떤 선택을 하더라도 유한한 횟수 안에 c 배열을 만들 수 있음은 증명될 수 있습니다.

당신은 b가 주어졌을 때 만들 수 있는 서로 다른 배열 c의 개수가 몇 개인지 알고 싶습니다.

정수로 이루어진 배열 a와 s가 매개변수로 주어집니다. a는 여러 개의 b 배열을 순서대로 이어 붙인 배열이며, s는 각 b 배열의 길이가 순서대로 담긴 배열입니다. 각 b 배열에 대해 문제의 답을 109 + 7로 나눈 나머지를 구하여 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

예를 들어, a = [1,2,3,4,5,6,7,8,9], s = [2,3,4] 라면, 다음 3가지 b 배열에 대해서 답을 구해야 합니다.

• b = [1,2] (s[0] = 2 이므로, a의 첫 2개 원소가 b 배열을 이룹니다.)
• b = [3,4,5] (s[1] = 3 이므로, a의 그다음 3개 원소가 b 배열을 이룹니다.)
• b = [6,7,8,9] (s[2] = 4 이므로, a의 그다음 4개 원소가 b 배열을 이룹니다.)

제한사항

• 1 ≤ a의 길이 ≤ 200,000
  • 1 ≤ a의 모든 수 ≤ 109
• 1 ≤ s의 길이 ≤ a의 길이
  • 1 ≤ s의 모든 수 ≤ a의 길이
  • s의 모든 수의 합 = a의 길이

 

2)솔루션

class Solution {
    val mod=(1e9 + 7).toLong()
    lateinit var hier:Array<HashMap<Long,Int>>
    lateinit var case:LongArray
    fun solution(a: IntArray, s: IntArray): IntArray {
        var answer: IntArray = IntArray(s.size)
        var l=0
        var r=0
        for(t in s.indices){
            val i=s[t]
            r=l+i-1
            //index는 우측 idx, 키는 합친 세포크기, 값은 좌측 idx
            hier=Array(i){hashMapOf<Long,Int>()}
            case=LongArray(i+1){0L}
            case[0]=1
            

            for(j in 0..i-1){
                case[j+1]=merge(a[j+l].toLong(),j,j)
            }
            answer[t]=(case[i]%mod).toInt()
            l=r+1
        }
        return answer
    }
    fun merge(initkey:Long,idx:Int,lidx:Int):Long{//idx는 계층 lidx는 좌측 인덱스
        var total=case[lidx]
        val curhier=hier[idx]
        curhier.getOrPut(initkey){lidx}

        if(lidx>0){
            hier[lidx-1][initkey]?.let{
                total+=merge(2*initkey,idx,it as Int)
                total%=mod
            }
        }
        

        return total
    }
}

-세포를 합쳐가면서 재귀문으로 문제 풀이

-오른쪽 인덱스를 계층으로 두어 풀고 첫 계층부터 순차적으로 풀이

 

 

3)느낀점

배열에 원소를 추가하는 행위가 얼마나 시간 복잡도 부분에서 극악인지 알게된 문제였다. 

배열에 원소를 추가하게 되면 크기를 재할당해야 하므로 시간복잡도가 O(n)이기 때문에 배열의 크기를 미리 지정하고 값을 집어넣는것보다 훨씬 오래걸리게 된다. 

이번 경우는 프로그래머스에서 처음에 자동으로 

var answer=intArrayOf()

로 두기 때문에 아무생각없이 이것에 맞춰 풀었는데 자꾸 시간초과가 나는 것이었다. 

 

이부분을 

var answer: IntArray = IntArray(s.size)

이렇게 바뀌었더니 소모시간이 드라마틱하게 줄어들었다. 

 

전

후

보다시피 시간초과가 나던 테스트케이스가 50ms까지 줄어든 모습이다.

이제부터 이부분에 특히 신경써야겠다 느꼈다.