알고리즘 연습(크레인 인형뽑기 게임)

# NOTE

스택(Stack) 이란?

사전적 의미로는 '쌓다', '더미'라는 뜻이 있습니다. 
스택을 흔히 후입선출(선출후입), LIFO 라고 부르는데 쉽게 설명하자면 
아래가 막힌 어떤 물체를 생각하시면 됩니다. 
쓰레기통, 마트용 음료수 진열대 등 이러한 것이 스택 구조 입니다. 
즉 한 쪽 끝에서만 자료(데이터)를 넣고 뺄 수 있는 형식의 자료 구조 입니다. 
스택을 실제 개발환경에서 사용 하는 경우는 인터넷 브라우저의 
'뒤로가기', '앞으로가기' 버튼을 생각 하시면 됩니다. 
따라서 Stack은 데이터를 쌓는 형식으로 저장하는데 
따라서 조회, 추가, 삭제 모두 가장 위에 있는 
즉 가장 최근의 값에서 이루어 진다. 
스택 구조에서 가장 상단에 있는 데이터를 Top이라고 한다.

<선언>
Stack<Element> stack = new Stack<>();

<함수>
push(); // 데이터 추가
pop(); // 최근에 추가된(Top) 데이터 삭제
peek(); // 최근에 추가된(Top) 데이터 조회
isEmpty(); // stack의 값이 비었는지 확인, 비었으면 true, 아니면 false
search(); // 인자값으로 받은 데이터의 위치 반환

https://velog.io/@lshjh4848/Java-%EC%8A%A4%ED%83%9DStack-%ED%81%B4%EB%9E%98%EC%8A%A4-%EC%A0%95%EB%A6%AC

---

# 크레인 인형뽑기 게임

//나의 풀이
class Solution {
	public static int solution(int[][] board, int[] moves) {
		int answer = 0;
		//스택 = 바구니
		Stack<Integer> stack = new Stack<>();
		
		for(int i = 0; i < moves.length; i++) {
			for(int k = 0; k < board.length; k++) {
				if(board[k][moves[i]-1] != 0) {
					//만약 스택이 비어있는 경우 그냥 넣으면 됨
					if(stack.isEmpty()) {
						stack.push(board[k][moves[i]-1]);
					}
					//만약 스택이 비어있지 않은 경우
					//새로 들어갈 인형이 기존 인형과 같은 것인지 확인 필요
					//같으면 제거 후 제거한 인형 수 +2
					//같지않으면 그대로
					else if(stack.isEmpty() == false) {
						if(stack.peek() == board[k][moves[i]-1]) {
							stack.pop();
							answer += 2;
						}
						else {
							stack.push(board[k][moves[i]-1]);
						}
					}
					//위 작업이 끝난 후엔 인형을 스택에 담은 상태이므로 0으로 초기화
					board[k][moves[i]-1] = 0;
					break;
				}
			}
		}
		
		return answer;
	}
}

//다른 사람 풀이
class Solution2 {
	public static int solution(int[][] board, int[] moves) {
		int answer = 0;
		Stack<Integer> s = new Stack<Integer>();
		for(int i=0; i<moves.length; i++) {
			for(int j=0; j<board.length; j++) {
				/* 
				 * 해당 칸에 인형이 존재하는경우
				 * ↓ 아래로 내려가므로 행의 값이 계속 바껴야함 (0,0), (1,0), (2,0) ...
				 * moves배열에 있는 요소를 board[][] 배열의 '열' 값에 넣어서 비교
				 * 배열의 인덱스는 0부터 시작하므로 -1
				 */ 
				if(board[j][moves[i]-1] != 0) {
					
					// 스택이 비어있는경우 -> 해당 인형 넣기
					if(s.isEmpty())
						s.push(board[j][moves[i]-1]);
					
					// 스택이 비어있지 않는경우 -> 인형이 동일한지 아닌지 비교
					else {
						// 인형이 동일하면 제거 후 사라진 인형개수 +2
						if(s.peek() == board[j][moves[i]-1]) {
							s.pop();
							answer += 2;
						}
						// 인형이 동일하지 않으면 스택에 인형 넣기
						else {
							s.push(board[j][moves[i]-1]);
						}
					}
					// 해당 작업 끝난 후에는 인형을 빼냈으므로 0으로 만든다.(인형이 없다는 표시)
					board[j][moves[i]-1] = 0;
					break;
				}
			}
		}
		return answer;
	}
}