문제 풀이 (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 라인 수로 쉽게 풀 수 있었다. 알고리즘을 공부하는 이유를 오늘에서 좀 더 체감하고 간다. 앞으로도 더 성장하자.