[Java] 프로그래머스 - 크레인 인형뽑기 게임 (1단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	O
본인의 실력으로 풀었는가?	O

 

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

 

 

 

 

 

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        
        ArrayList<Queue<Integer>> map = new ArrayList<>();
        
        for (int i = 0; i < board.length; i++) {
            Queue<Integer> q = new LinkedList<>();
            
            for (int j = 0; j < board[i].length; j++) {
                if (board[j][i] == 0) continue;
                
                q.add(board[j][i]);                
            }
            
            map.add(q);
        }
        
        Stack<Integer> s = new Stack<>();
        
        for (int i = 0; i < moves.length; i++) {
            Queue<Integer> q = map.get(moves[i]-1);
            if (!q.isEmpty()) {
                int num = q.poll();
                int sNum = (!s.empty()) ? s.peek() : -1;
                
                if (sNum != -1 && num == sNum) {
                    s.pop();
                    answer += 2;
                } else {
                    s.push(num);
                }
            }
        }
        
        return answer;
    }
}

 

테스트 1 〉	통과 (0.27ms, 79.9MB)
테스트 2 〉	통과 (0.24ms, 74.4MB)
테스트 3 〉	통과 (0.27ms, 83.6MB)
테스트 4 〉	통과 (2.65ms, 72MB)
테스트 5 〉	통과 (0.24ms, 78.3MB)
테스트 6 〉	통과 (0.38ms, 75.8MB)
테스트 7 〉	통과 (0.36ms, 77MB)
테스트 8 〉	통과 (1.08ms, 83.7MB)
테스트 9 〉	통과 (0.68ms, 77.8MB)
테스트 10 〉	통과 (0.82ms, 72.3MB)
테스트 11 〉	통과 (1.02ms, 75.2MB)

 

 

 

 

 

board에 들어 있는 블록을 세로 한 줄씩 정리할건데, 위에서부터 정의되어 있어서 제일 먼저 들어간 것을 꺼내는 Queue를 이용하여 정리했음.

 

 

 

 

정리한 Queue들은 ArrayList로 묶어서 map을 만들었고, moves 배열에서 하나씩 꺼내오면서 제일 마지막에 넣는 것을 꺼내는 스택으로 블록을 하나씩 넣는데, 만약 제일 위에 있는 것이 넣을 것과 같으면 스택 맨 마지막에 넣은 값을 없애고 answer에 +2를 하는 것으로 코드를 짰다.

 

 

 

 

지난번에 작성한 코드

 

import java.util.*;

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

 

테스트 1 〉	통과 (0.18ms, 53MB)
테스트 2 〉	통과 (0.13ms, 77.2MB)
테스트 3 〉	통과 (0.19ms, 52.1MB)
테스트 4 〉	통과 (1.31ms, 52.2MB)
테스트 5 〉	통과 (0.18ms, 52.1MB)
테스트 6 〉	통과 (0.18ms, 53.3MB)
테스트 7 〉	통과 (0.30ms, 52.2MB)
테스트 8 〉	통과 (0.63ms, 52.2MB)
테스트 9 〉	통과 (0.51ms, 52.9MB)
테스트 10 〉	통과 (0.55ms, 52.9MB)
테스트 11 〉	통과 (0.84ms, 53.4MB)

 

 

이거는 그냥 그 board 자체에서 0이 아닌 값이 나올 때까지 for문을 돌리고, 만약에 0이 아닌 값이 나오면 스택에 넣고, 비교하는 걸로 코드를 짰었었음.

 

ArrayList에 넣고 꺼내고 그런 시간이 없다보니까 이번에 작성한 코드보다 시간 복잡도가 낮음.