Yong's Tech Story

문제 풀이 (JAVA)

import java.util.*;
public class part5_3 {

	public static void main(String[] args) {
		// 크레인 인형뽑기(카카오)
		Scanner input = new Scanner(System.in);
		int N = input.nextInt();
		
		int [][] a = new int[N][N];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				a[i][j]=input.nextInt();
			}
		}
		
		int K = input.nextInt();
		int [] b = new int[K];
		for(int i=0; i<K; i++) {
			b[i]=input.nextInt();
		}
		int answer = solution(a,N,b,K);
		
		System.out.print(answer);
	}
	private static int solution(int [][] a, int N, int [] b, int K) {
		int result = 0;
		Stack<Integer> stack = new Stack<>(); // 스택선언
		int idx=0; // 탐색할 배열 인덱스
		for(int i=0; i<K; i++) { // b의 K번째까지 반복 탐색
			idx=0; // 배열 인덱스 초기화
			// 2차원 행렬 b번째 행렬에 a의 0번째 행부터 인덱스로 순차적으로 탐색하여 0이 아닐때까지 탐색
			while(idx < N && a[idx][b[i]-1] == 0) {
				idx++;
			}
			if(idx == N) { // 인덱스가 N까지 증가되었다면 b번째 행렬은 모두 0이므로 다음 for문 처리
				continue;
			}
			// 스택에 값이 들어있다면
			if(stack.size() != 0) {
				if(a[idx][b[i]-1] == stack.peek()) { // 스택의 마지막 값과 현재 뽑은 a의 숫자가 같을 경우
					stack.pop(); // 스택에서 값을 제거
					result+=2; // 현재 뽑은 a를 추가하지 않고 결과값 +2
				}else { // 마지막 스택 값과 다르다면 값 추가
					stack.push(a[idx][b[i]-1]);	
				}
			}else { // 스택이 비어있다면 값 추가
				stack.push(a[idx][b[i]-1]);
			}
			a[idx][b[i]-1] = 0; // 뽑은 a의 행렬 값 0으로 초기화			
		}		
		
		return result;
	}
}

주요 핵심 포인트

1.  이차원행렬의 인덱스를 머리에 잘 그려놓고 입력받은 b의 인덱스 값을 이용하여 값이 존재하는지 유무를 잘 판별해야한다.

2.  값을 추가 시켜주는 일차원 배열을 스택으로 구현하여, 스택의 마지막 값과 현재 값이 같다면 현재 값은 스택에 넣지 않고, 스택의 마지막값은 제거시킴으로써 result 값은 +2를 해주었다.

3. 스택이 존재하지 않을때의 처리를 잘해주어야 하고, 인덱스가 N까지 왔다면 모든 숫자가 0임으로 continue 처리를 해주었다.

개선해야할 사항

1. 실은 이 문제를 프로그래머스에서 스택의 개념을 모를때 한번 푼적이 있다. 그때 당시에 시간이 훨씬 오래 걸려서 간신히 풀었는데, 스택을 사용함으로써 다시 문제를 푼 결과 코드가 개선이 되었다고 생각한다. 아래는 이전에 풀었던 프로그래머스 코드이다.

프로그래머스 -  이전 소스 코드

import java.util.*;
class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0; i<moves.length; i++){
            int w=0;
            int h=moves[i]-1;
            if(list.size()>1){
                // 리스트의 사이즈가 2개이상이고 마지막 값과 마지막 전 값이 같다면
                while(list.get(list.size()-2)==list.get(list.size()-1)){
                    list.remove(list.size()-1); //마지막 값 제거
                    list.remove(list.size()-1); //제거된 리스트의 마지막 값 제거
                    answer+=2; // 결과 +2
                    if(list.size()<2){ // 사이즈 오류 방지--크기가 2보다 작다면 멈춰라.
                        break;
                    }
                }
            }
            while(board[w][h] ==0){ // 값이 0이라면 찾을 행 증가
                w++;
                if(w==board.length-1){ // 마지막 행도 0이라면 반복 증가 멈춰라.
                    break;
                }
            }
            
            if(w==board.length-1 && board[w][h]==0){ // 마지막이 0이라면 스킵
                continue;
            }
            if(board[w][h] != -1){  // 0이 아니라면 값이 있으므로
                list.add(board[w][h]);
                System.out.println(list);
                board[w][h]=-1;  // 값 저장 후 -1로 변환 후 스킵
                continue;
            }
            if(board[w][h] == -1){  // -1은 사용된 값으로 -1이 나온다면
                while(board[w][h] == -1){  // -1이 아닐때까지 반복 증가
                    w++;
                    if(w==board.length){  // 다음 행이 마지막 행이라면 멈춰라.
                        break;
                    }
                    if(board[w][h] != -1){ // 마지막행이 아니라면 뽑아야 될 값
                        list.add(board[w][h]);
                        board[w][h]=-1; // 리스트 저장 후 스킵
                        break;
                    }
                }
            }
        }
        return answer;
    }
}

이때는 리스트의 개념만 알고 있어 힘들게 풀었다. 스택의 개념을 공부하고 풀어 보니, 이전에 풀었던 코드의 1/2 라인 수로 쉽게 풀 수 있었다. 알고리즘을 공부하는 이유를 오늘에서 좀 더 체감하고 간다. 앞으로도 더 성장하자.