프로그래머스 - 혼자 놀기의 달인

https://school.programmers.co.kr/learn/courses/30/lessons/131130

프로그래머스

 

문제를 읽었을때

- 임의로 카드를 선택해야하고 -> 다 확인을 해봐야한다.

- 열어야 하는 상자가 이미 열려있을때 까지 반복 -> visit 배열을 사용할 것

를 읽고 dfs 를 써보면 어떨까 싶었다.

 

그러나 일반적인 dfs 문제처럼 깊이나 도달해야하는 조건이 존재하지는 않고

방문을 할 수 없을때까지 그냥 반복시키면 됐다.

 

카드 배열 첫번째부터 다 확인을 시작한다.

그리고 문제 조건에 맞게 예제를 설명해보면

1. 0번째 카드는 8이다. 그럼 8번째 박스를 오픈하러 가야한다.

2. 방문을 했는지 visited 배열로 체크한다. 8번째는  visited 에서는 8-1 즉 7번 인덱스가 true 인지 체크한다.

3. 방문한적이 없다면 박스를 오픈할 수 있다.

4. 오픈할때마다 해당 숫자를 배열에 따로 저장한다.

5. 재귀를 돌면서 1~4번을 반복한다.

 

이렇게 박스그룹 하나를 만드는 사이클이 돌아가고

카드 배열을 다 돌아가면서 처음 여는 박스가 방문한적이 없다면

위 사이클을 또 돌린다.

그럼 다음 박스그룹이 또 나온다.

 

이렇게 만들어진 박스그룹들의 사이즈만 모아서 따로 배열에 저장하고

문제에서 원하고자하는 최고점수는 max 를 이용해서 구한다.

 

class Solution {
    var visited = booleanArrayOf()
    var resultList = mutableListOf<Int>()
    var result = mutableListOf<Int>()
    var max = 0
    fun solution(cards: IntArray): Int {
        var answer: Int = 0
        visited = BooleanArray(cards.size)
    
       for(i in 0 until cards.size){
           if(!visited[i]){
                recur(cards, i)
                resultList.add(result.size)
                result.clear()
           }
       }
       maxResult(resultList)
      
        return max
    }
    
    fun maxResult(list : MutableList<Int>){
        for(i in 0 until list.size){
            for(j in i+1 until list.size){
               max=maxOf(max,list[i] * list[j]) 
            }
        }
    }
    
    fun recur(cards : IntArray, v : Int){
        visited[v] =true
        result.add(cards[v])
        if(!visited[cards[v]-1]){
            dfs(cards, cards[v]-1)
        }
    }
}

 

 

알고리즘 문제를 풀다가 기분이 좋아지는 순간은 이렇게 혼자만의 힘으로 풀어냈을때다.

너무 오래걸리고 접근방법 조차 떠오르지 않는다면 다른 사람들의 풀이를 참고하는건 좋다고 생각한다.

하지만 그게 계속 반복되면 '내가 공부를 잘하고 있는게 맞나. 실력이 늘지 않는것 같은데 불안하다.'

이런 생각이 들게되는데 스스로 풀려고 노력하다가 풀렸을때 이런 걱정들이 조금씩 사라지는 기분이 든다.

 

말로만 해야겠다고 하고 미뤄뒀던 알고리즘 풀이를 매일매일 포기하지 않고

풀기 시작한지 이제 한달이 조금 넘은거 같다.

어려운 문제들은 여전히 어렵지만 내가 생각해도 처음에 비해서는 많이 발전했다.

포기하지말고 꾸준히 하자 파이팅!