프로.1.크레인

각 열에 해당하는 높이를 체크해서 보드의 행으로 사용했다.

인접한 애들 제거해야 하니까 인형을 담을 자료구조는 스택.

이중 포문 하나로 합치면 더 좋았을듯.

 

뭐가 문제인가 했더니, 터뜨린 인형의 갯수

터뜨린 횟수만 반환해서 문제였음. 

*2로 해결.

 

int solution(vector<vector<int>> board, vector<int> moves) {
    
    int n = board.size();
    int movSize = moves.size();

    //board 각 열의 높이
    vector<int> height(n, 0); //board row

    for (int col = 0; col < n; ++col)
    {
        for (int low = 0; low < n; ++low)
        {
            if (board[low][col] != 0)
            {
                height[col] = low;
                break;
            }
        }
    }

    // move - 1 -> board column idx 
    // pick = board[height[move[i-1]]][move[i-1]]
    // board[height[move[i-1]]][move[i-1]] = 0
    // stack.top() == pick -> pop()

    stack<int> stack;
    int pick = 0, answer = 0;

    for (int col : moves)
    {
        col -= 1;
        //인형이 없지 않다면,
        if (n > height[col])
        {
            pick = board[height[col]][col];
            board[height[col]++][col] = 0;

            if (stack.empty() || pick != stack.top()) {
                stack.push(pick); 
            }
            else 
            {
                stack.pop();
                ++answer;
            }
        }
    }

    return answer * 2;
}

 

 

 

제미나이

 

나의 방법은 n*n 보다 m이 확연히 클 경우 좋을 수 있겠으나, 

900, 1000은 큰 차이가 나지않으므로 직접 순회하는 것이 효울적이라는 이야기.

 

같은 열을 접근하는 빈도가 높다면, 순회 중에 행 인덱스를 체크하는 배열을 추가해도 좋겠지.

그리고 answer는 연산 할 때 한번에 2씩 증가시키는 게 맞다.

 

게다가 내껀 불필요한 연산이 많다.

int solution(vector<vector<int>> board, vector<int> moves) {
    stack<int> basket;
    int answer = 0;

    for (int move : moves) {
        int col = move - 1;

        for (int row = 0; row < board.size(); ++row) {
            if (board[row][col] != 0) {
                int doll = board[row][col];
                board[row][col] = 0; // 인형을 뽑았으므로 0으로 설정

                if (!basket.empty() && basket.top() == doll) {
                    basket.pop();
                    answer += 2; // 터진 인형 쌍은 2개
                } else {
                    basket.push(doll);
                }
                break; // 인형을 뽑았으면 다음 move로 이동
            }
        }
    }

    return answer;
}

 

 

제시된 조건 n = 5 ~ 30, m = 1 ~ 1000을 바탕으로 시간 복잡도를 분석하고 최적의 방법을 선택해 보겠습니다.

조건 분석:

• n의 범위: 5 ~ 30 (상대적으로 작은 값)
• m의 범위: 1 ~ 1000 (상대적으로 큰 값)

시간 복잡도 비교:

1. height 배열 사용 (O(N^2 + M))
   • N^2: 25 ~ 900
   • M: 1 ~ 1000
   • 이 경우, M의 값이 N^2의 값보다 커질 가능성이 높습니다.
2. 행 순회 (O(M * N))
   • M * N: 5 ~ 30000

결론:

• m의 최대값이 1000이고, n의 최대값이 30이므로, M * N의 최대값은 30000입니다.
• height 배열을 사용하는 경우, N^2의 최대값은 900이므로, M이 900보다 커지면 행 순회가 더 효율적입니다.
• 주어진 조건에서 m은 최대 1000이므로, 대부분의 경우 행 순회가 height 배열을 사용하는 것보다 효율적입니다.
• 따라서, 행을 순회하는 방식(개선된 코드)이 주어진 조건에서 더 효율적입니다.

추가 고려 사항:

• n이 매우 작고 m이 매우 큰 극단적인 경우를 제외하고는 개선된 코드가 효율적입니다.
• 코드의 가독성 측면에서도 행을 순회하는 방식이 더 좋습니다.

요약:

• 주어진 조건에서는 행을 순회하는 방식(개선된 코드)이 더 효율적입니다.
• n과 m의 크기를 비교하여 적절한 방법을 선택하는 것이 중요합니다.