알고리즘 재활 7일차 - 백준 1541, 3190번

한달동안 알고리즘만 해보겠숩니다~!

 

 

잃어버린 괄호

 

아이고 세준아 누가 입력을

 

이렇게 넣으래 귀찮게시리

일단 그리디한 방식은 -뒤는 모두 더해주면 가장 최솟값으로 만들어줄 수 있다.

따라서 -를 기점으로 숫자를 모두 더해주고, 이후 + 연산을 처리해 주면 가장 작은 값이다.

 

숫자와 연산자를 나누는 건 split 처럼 StringTokenizer로 나눠줍시다.

StringTokenizer stSub = new StringTokenizer(br.readLine(), "-");

 

요로코롬  빼기 ('-') 를 기준으로 나눌 수 있다.

 

다만 맨 첫 번째는 무조건 양수다. 따로 처리해 주는 것에 유의

1. 맨 첫 번째는 더해준다.

2. '-' 빼기를 기점으로 숫자와 연산자를 먼저 나눈다.

3. 나눈 부분을 + 연산 처리를 통해 더한다.

4. 이후 나머지 부분 + 연산

 

예제 1의 경우

먼저 55를 answer에 넣어주고, - 으로 나누어 50+40을 로직에 던져 +처리를 한다

그럼 90의 값이 나오는데 이를 answer에 빼주면 최솟값인 -35이 나온다.

---

뱀

 

뱀이 사과를 좋아하나 보다...

 

조건들

 

1. 뱀은 왼쪽 최상단에서 시작하며 오른쪽을 보고 있는 상태이다.
2. 1초에 1칸 이동한다.
3. 일정 시간마다 뱀은 왼쪽이나 ('L') 오른쪽 ('D')으로 방향을 바꾼다.
4. 사과를 먹으면 뱀의 길이가 늘어난다.
5. 자신의 몸이나, 벽에 부딪히면( 밖으로 나가면 ) 종료

시간에 따라 방향을 바뀌는 건 Queue를 통해 관리해 주었다.

dr, dc 배열을 이용했고 % 연산으로 방향을 전환했다.

사과를 먹을 때 뱀의 길이가 변경되는 것은 머리와 꼬리를 Deque 덱 구조를 이용해

사과를 먹으면 데이터를 추가하고 사과를 먹지 않으면 맨 끝을 지워주어 뱀의 길이를 유지했다.

 

결국 뱀이 이동하기전 큐에 담긴 방향 전환과 비교하고,

다음으로 이동하는 곳이 맵 바깥인지, 뱀의 몸인지 체크하면서 이동한다.

이동 중 사과를 먹으면 몸길이가 증가된다.

 

import java.io.*;
import java.util.*;
 
public class Main { // G4 뱀
 
    public static int N, K, L;
    public static int[] dr = {-1, 0, 1, 0};
    public static int[] dc = {0, 1, 0, -1};
    public static int[][] map;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());// 사과
        map = new int[N][N];
 
        for (int j = 0; j < K; j++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            map[r][c] = 7;
        }
 
        L = Integer.parseInt(br.readLine());
        Queue<DirectionChange> que = new LinkedList<>();
        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());
            int time = Integer.parseInt(st.nextToken());
            String direction = st.nextToken(); // L -> 왼쪽 -1, D -> 오른쪽 +1
            que.add(new DirectionChange(time, direction));
        }
 
        Snake snake = new Snake(0, 0, 1);
        Deque<int[]> snakeBody = new LinkedList<>();
        snakeBody.add(new int[]{0, 0});
        map[0][0] = 1;
        int time = 0;
 
        while (true) {
//            System.out.println("현재 위치: " +snake.r+" "+snake.c);
            if (!que.isEmpty() && que.peek().time == time) {
                DirectionChange directionChange = que.poll();
                if (directionChange.time == time) {
                    if (directionChange.direction.equals("L")) {
                        snake.direction = (snake.direction + 3) % 4;
//                        System.out.println("좌회전: "+snake.direction);
                    } else if (directionChange.direction.equals("D")) {
                        snake.direction = (snake.direction + 1) % 4;
//                        System.out.println("우회전: "+snake.direction);
                    }
                }
            }
            time += 1;
            int nextR = snake.r + dr[snake.direction];
            int nextC = snake.c + dc[snake.direction];
 
//            for (int i = 0; i < N; i++) {
//                for (int j = 0; j < N; j++) {
//                    System.out.print(map[i][j] + " ");
//                }
//                System.out.println();
//            }
 
            if (rangeChk(nextR, nextC, map)) {
                System.out.println(time);
                break;
            }
 
            if (map[nextR][nextC] == 7) { // 사과가 있는 경우
                snakeBody.addFirst(new int[]{nextR, nextC});
            } else { // 사과가 없는 경우
                snakeBody.addFirst(new int[]{nextR, nextC});
                int[] tail = snakeBody.removeLast();
                map[tail[0]][tail[1]] = 0;
            }
 
            snake.r = nextR;
            snake.c = nextC;
            map[nextR][nextC] = 1;
        }
    }
 
    static class DirectionChange {
        int time;
        String direction;
 
        public DirectionChange(int time, String direction) {
            this.time = time;
            this.direction = direction;
        }
    }
 
    static class Snake {
        int r, c;
        int direction;
 
        public Snake(int r, int c, int direction) {
            this.r = r;
            this.c = c;
            this.direction = direction;
        }
    }
 
    public static boolean rangeChk(int r, int c, int[][] map) {
        return r < 0 || c < 0 || r >= N || c >= N || map[r][c] == 1;
    }
}