[programmers]クレーンを捕まえるゲーム

1.問題の説明

ゲーム開発者죠르디はクレーン型抜き機をモバイルゲームに変えようとした.
ゲームの面白さを高めるために、「Jordie」は画面レイアウトとルールをゲームロジックに反映し、以下のようにします.

ゲーム画面は「1 x 1」サイズのセルからなる「NxN」サイズの正斜角メッシュで、上部にクレーン、右側にバスケットがあります.(上の図は、サイズが「5 x 5」の例を示しています).各格子間には様々なぬいぐるみがあり、ぬいぐるみのない格子は空いています.すべての人形は「1 x 1」の大きさのメッシュを占め、メッシュの一番下から順番に積み上げられます.ゲームユーザーはクレーンを左右に動かし、停止した位置から一番上の人形を持ち上げることができる.拾った人形はかごの中に積み上げられ、かごの一番下の格子から人形は順番にかごの中に積み上げられます.下の図は[1番、5番、3番の位置で人形を順番にかごに入れる様子を示しています.

同じ形の2人の人形が連続してかごに積まれると、2人の人形が爆発してかごから消えてしまいます.上の状態で、次に[5番]の位置で人形をかごに積み上げると、同じ形の人形が2つ消えてしまいます.

クレーンが作動すると、人形が挟まないことはありませんが、人形がないところでクレーンを起動すれば、何も起こりません.また、バスケットが十分大きく、すべての人形を収容できると仮定します.(図中、スクリーン表示制限は5コマのみ表示)
ゲーム画面上の格子状態の2次元配列板と人形を挟むために、起動クレーンの位置を含む配列動作をパラメータとして指定した場合、solution関数を完了し、クレーンをすべて起動させ、爆発して消えた人形の個数を返します.

[制限]

マザーボードアレイは2 Dアレイで、サイズは「5 x 5」または「30 x 30」より大きい.

boardの各セルには、0または100以下の整数が含まれています.

0はスペースを表します.

1-100の各数字は異なる人形の形を表し、同じ数字は同じ人形の形を表す.

モバイルアレイのサイズは1000を超えません.

movies配列の各要素の値は1より大きく、自然数であり、スラブ配列の水平寸法より小さい.

I/O例

boardmovesresult[[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]][1,5,3,5,1,2,1,4]4

I/O例説明

I/O例#1
人形の初期状態は、与えられた問題の例と同じである.クレーンは[1,5,3,5,1,2,1,4]号の位置から順に人形を持ち上げ、かごに入れたが、状態は下図のようにかごの中で爆発して消えた人形が4個あった.

2.解説

2019年のKACA冬季実習期に出た問題ですが、問題説明が長く難しいように見えますが、スタックを知っていれば簡単に解決できる問題です.順番に丁寧に説明すると、

moviesから位置を取り出し、クレーンを底に置き、そこに人形があればcur_dollという変数に取り出して保存します.このプロセスが終了したら、元のぬいぐるみの位置に0を入れます.

スタックが空の場合は、ぬいぐるみを挿入します.そうしないと、スタックの一番上のぬいぐるみを現在のぬいぐるみと比較します.人形であれば、スタックから人形を取り出し、resultの価格に2を加算します.(2人の人形が集まると爆発するから).人形が違う場合は、スタックに直接挿入します.

moves配列がチェックされるまで、以上の手順を繰り返します.

3.コード

def solution(board, moves):
    answer = 0
    stack = []
    cur_doll = 0 #뽑은 인형을 저장할 변수
    
    for idx in moves:
        idx -= 1
        
        for crain in range(len(board)): #크레인을 밑으로 내린다
        	cur_doll = board[crain][idx]
            if cur_doll != 0: #인형이 있다면
                board[crain][idx] = 0 #인형을 뽑은 자리에 0을 넣어주고 종료
                break

        if not stack and cur_doll != 0: #인형을 뽑았는데 스택이 빈 경우
            stack.append(cur_doll)
        elif stack and cur_doll != 0:
            if stack[-1] == cur_doll: #스택의 가장 윗자리 인형과 뽑은 인형이 같으면
                stack.pop() #스택에서 인형을 꺼내준다
                answer += 2
            else:
                stack.append(cur_doll)
            
    return answer