[알고리즘/Goorm] LV2. 블록 게임 (Java)

 

오늘의 학습 키워드

• 스택(Stack)
• 으로 풀었는데 원래 카테고리는 큐..(?)

오늘의 회고

1. 문제

• 문제 URL

구름LEVEL

2. 해결 방안

import java.io.*;
import java.util.*;

public class BlockGame {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String str = br.readLine();
        String strMove = br.readLine();
        String strNum[] = strMove.split(" ");

        Stack<Node> st = new Stack<>();

        // 초기화
        int x = 0;
        int y = 0;
        st.push(new Node(0,0,1));

        for(int i=0; i<n; i++) {
            char move = str.charAt(i);
            int num = Integer.parseInt(strNum[i]);

            if(move == 'R') {
                y += 1;
            }else if(move == 'L') {
                y -= 1;
            }else if(move == 'U') {
                x -= 1;
            }else { // 'D'
                x += 1;
            }

            // 놓여있는 블럭인지 확인
            checkVisited(x, y, st);
            st.push(new Node(x,y,num));
        }

        // 정답 계산
        int result = 0;
        while(!st.isEmpty()) {
            result += st.pop().num;
        }

        System.out.println(result);
    }

    public static void checkVisited(int x, int y, Stack<Node> st) {
        Stack<Node> st2 = new Stack<>();
        while(!st.isEmpty()) {
            Node n = st.pop();

            if(n.x == x && n.y == y) {
                // 방문한 적이 있는 곳이라면 현재까지 방문한것을 이미 다 제거했다
                return;
            }

            st2.add(n);
        }

        // 방문한 적이 없다면 원복 시킨다
        while(!st2.isEmpty()) {
            st.add(st2.pop());
        }
    }

    public static class Node{
        int x;
        int y;
        int num;

        public Node(int x, int y, int num) {
            this.x = x;
            this.y = y;
            this.num = num;
        }
    }

}

• 블럭(노드)이 초기에는 0,0,1(x,y,가중치) 값에서 시작하므로 초기값을 스택에 넣고, 현재 위치를 입력해 둘 x,y 변수를 0으로 초기화해둔다.
• 놓을 블럭 개수 만큼 for문을 돌면서 L,R,U,D 에 따라 x, y 좌표 값을 업데이트 시킨다.
• 놓여있는 블럭인지 확인하는 함수를 작성한다.
  • 스택에 있는 값을 하나씩 빼면서 스택2에 넣는다. 이미 놓여있는 블럭 위치라면 함수를 나간다. (함수 내 스택2는 다시 초기화됨)
  • 블럭이 놓여있지 않다면(=스택1이 다 비었다면) 스택2에 담아두었던 블럭을 다시 스택1로 옮긴다.
• 스택1에 신규 블럭을 추가한다.
• 위 과정이 끝나면 스택에 남은 값을 합산하여 출력한다.

3. 피드백

• 처음에 문제 이해가 제대로 안되서 시간이 오래 걸렸던 문제.. 문제 카테고리는 큐였는데 스택으로 풀었다. (되면 된거지 머..)
• 나는 checkedVisited() 함수를 따로 안만들고 내부에서 진행했더니 로직이 다소 지저분해졌는데 함수로 빼면 함수 내에 스택2를 사용하면 되어서 코드가 더 간결해진다. (남친이 짠 참고 코드 굿,, 짝짝,,)