[프로그래머스 / Level1] 크레인 인형뽑기 게임 (Java)

문제

2019 카카오 개발자 겨울 인턴십 / https://programmers.co.kr/learn/courses/30/lessons/64061

코딩테스트 연습 - 크레인 인형뽑기 게임

 

기존 코드 (실패)

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;                                             //터진 인형 개수
        int[] basket = new int[board[0].length * board.length];     //바구니
        int basketIdx = 0;

        for(int i = 0; i < moves.length; i++){
            boolean isEmpty = false;
            int move = moves[i]-1;

            //borad 배열의 뒤에서 부터 접근
            for(int j = board[move].length-1; j >= 0; j--){
                if(board[move][j] != 0) {
                    basket[basketIdx++] = board[move][j];         //바구니 추가
                    board[move][j] = 0;                         //인형 없애기

                    //바구니에 연속값 있나 체크
                    for(int k=0; k <= basketIdx; k++){
                        if(basket[k] != 0 && basket[k] == basket[k+1]) {
                            answer += 2;
                            basket[k] = 0;
                            basket[k+1] = 0;
                        }
                    }

                    break;                                  //다음 이동
                }
            }
        }

        return answer;
    }
}

 

실패 이유

• 자바 Collection Framework에 대한 학습이 미흡하여 '바구니'로 사용할 자료구조를 1차원 배열로 선택했다.
  => '바구니' : 순서가 있음, 중복 허용, 맨 위에 값을 추가/제거하기 때문에 스택(Stack)이 적절함
  
  
• 문제를 잘못 이해하여 2차원 배열 board의 구조를 착각했다.
  ex) 게임화면의 격자상태가 담긴 2차원 배열 board
  예시 값 : [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]
  
  [실제 게임화면]
  

  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

  
  [내가 생각한 게임화면]

  0	0	0	2	1
  0	0	0	4	3
  0	0	1	4	1
  0	3	5	2	5
  0	1	2	4	3

  - 그러니까 문제는 2차원배열의 요소인 각 1차원 배열이 한행을 나타내는데, 나는 이 1차원 배열들이 한 열을 나타낸다고 생각했다. 대체 왜 이렇게 생각한건지 의문이다... 잠시 뭐에 씌었나? '격자의 한열은 1차원 배열이다.'라는 고정관념에 사로잡혔던 건지. 예시가 5x5 구조 였던탓도 있고, 아래와 같은 격자라고 생각하고 해결 코드를 짰는데, [코드 수행] 결과는 성공이 떠서 기본 전제부터가 틀렸다는 생각을 못 한듯. (물론 코드 수행만 성공뜨고, 채점은 다 실패) 문제를 풀기에 앞서 제약조건과 문제 상황을 제대로 이해하는 것이 중요!!
  
  

학습 내용

컬렉션 프레임워크(Collection Framework)

데이터 그룹을 저장하는 클래스들을 표준화한 설계

인터페이스	특징
List	순서O, 데이터 중복 허용O
	구현 클래스 : ArrayList, LinkedList, Stack, Vector 등
Set	순서X, 데이터 중복 허용X
	구현 클래스 : HashSet, TreeSet 등
Map	키(key)-값(value)의 쌍(pair), 순서X, 키 중복 허용X, 값 중복 허용O
	구현 클래스 : HashMap, TreeMap, Hashtable, Properties 등

 

List 인터페이스 주요 메서드

메서드	설명
void add(int index, Object element) boolean addAll(int index, Collection c)	지정된 위치에 객체 또는 컬렉션에 포함된 객체들을 추가
Object get(int index)	지정된 위치에 있는 객체 반환
int indexOf(Object o)	지정된 객체의 위치 반환 (앞에서부터 탐색)
int lastIndexOf(Object o)	지정된 객체의 위치 반환 (뒤에서부터 탐색)
Object remove(int index)	지정된 위치에 있는 객체 삭제 후 반환
Object set(int index, Object element)	지정된 위치에 객체 저장
void sort(Comparator c)	지정된 비교자(Comparator)로 List를 정렬 *Comparator : 객체 배열에서 객체의 대소관계 파악을 위한 비교 클래스
List subList(int fromIndex, int toIndex)	지정된 범위에 있는 객체 반환

 

스택(Stack)

• List인터페이스를 구현하는 자료구조 클래스. 
• LIFO(Last In First Out) 구조

스택(Stack) 주요 메서드

메서드	설명
boolean empty()	Stack이 비어있는지 확인 결과 반환
Object peek()	Stack의 맨 위에 저장된 객체 반환.  *비어있을 경우 EmptyStackException 발생
Object pop()	Stack의 맨 위에 저장된 객체 꺼내기.  *비어있을 경우 EmptyStackException 발생
Object push(Object item)	Stack에 객체 저장
int search(Object o)	Stack에서 주어진 객체를 찾아서 그 위치를 반환. *위치는 1부터 시작 / 검색 실패 : -1

 

import java.util.Stack;

public class StackQueueEx {

	public static void main(String[] args) {
		Stack<Integer> st = new Stack<Integer>();
		
		st.push(0);
		st.push(1);
		st.push(2);
		
		while(!st.empty()) {
			System.out.println(st.pop());
		}
	}
}

//실행결과
2
1
0

 

개선 코드 (성공)

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        Stack<Integer> basket = new Stack<Integer>();
        
        for(int i = 0; i < moves.length; i++){
            int move = moves[i]-1;
            
            for(int j = 0; j < board.length; j++){
                int doll = board[j][move];
                if(doll != 0){
                    if(!basket.empty() && basket.peek() == doll){
                        basket.pop();
                        answer += 2;
                    }else{
                        basket.push(doll);
                    }
                    
                    board[j][move] = 0;
                    
                    break;
                }
            }
        }
        
        return answer;
    }
}

---

출처

• 프로그래머스 2019 카카오 개발자 겨울 인턴십 / https://programmers.co.kr/learn/courses/30/lessons/64061
•  자바의 정석 3rd / 남궁 성 / 도우출판