www.acmicpc.net/problem/20056

 

20056번: 마법사 상어와 파이어볼

첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치

www.acmicpc.net

문제

어른 상어가 마법사가 되었고, 파이어볼을 배웠다.

마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다. 위치 (r, c)는 r행 c열을 의미한다.

격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.

파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다.

7 0 1
6   2
5 4 3

마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.

  1. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
    • 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.
  2. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
    1. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
    2. 파이어볼은 4개의 파이어볼로 나누어진다.
    3. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
      1. 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
      2. 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
      3. 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
    4. 질량이 0인 파이어볼은 소멸되어 없어진다.

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자.

입력

첫째 줄에 N, M, K가 주어진다.

둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다.

서로 다른 두 파이어볼의 위치가 같은 경우는 입력으로 주어지지 않는다.

출력

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 출력한다.

제한

  • 4 ≤ N ≤ 50
  • 0 ≤ M ≤ N2
  • 1 ≤ K ≤ 1,000
  • 1 ≤ ri, ci ≤ N
  • 1 ≤ mi ≤ 1,000
  • 1 ≤ si ≤ 1,000
  • 0 ≤ di ≤ 7

예제 입력 1

4 2 1

1 1 5 2 2

1 4 7 1 6

예제 출력 1

8

예제 입력 2

4 2 2

1 1 5 2 2

1 4 7 1 6

예제 출력 2

8

예제 입력 3

4 2 3

1 1 5 2 2

1 4 7 1 6

예제 출력 3

0

예제 입력 4

7 5 3

1 3 5 2 4

2 3 5 2 6

5 2 9 1 7

6 2 1 3 5

4 4 2 4 2

예제 출력 4

9

 

 

 

 

 

 

 

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Fireball {
    int r, c, m, s, d;
    boolean flag;
    Fireball(int r, int c, int m, int s, int d, boolean flag) {
        this.r = r;
        this.c = c;
        this.m = m;
        this.s = s;
        this.d = d;
        this.flag = flag;
    }
}

public class Main {
    static int n, m, k, ans;
    static boolean turnFlag;
    static ArrayList<Fireball>[][] map;
    static int[] rArr = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] cArr = {0, 1, 1, 1, 0, -1, -1, -1};

    public static void calculate() {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(map[i][j].isEmpty()) continue;
                for(Fireball f : map[i][j]) {
                    ans += f.m;
                }
            }
        }
    }

    public static void moveBall() {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(map[i][j].isEmpty()) continue;

                for(int idx = 0; idx < map[i][j].size(); idx++) {
                    Fireball f = map[i][j].get(idx);
                    if(f.flag == turnFlag) continue;  // 이번 턴에 이동해서 온 것은 또 이동시키면 안 딤

                    int nr = f.r + rArr[f.d] * (f.s % n);
                    int nc = f.c + cArr[f.d] * (f.s % n);
                    if(nr > 0) nr %= n;
                    if(nc > 0) nc %= n;
                    if(nr < 0) nr = n - Math.abs(nr);
                    if(nc < 0) nc = n - Math.abs(nc);
                    // (f.s % n)을 곱하기 때문에 n-Math.abs()는 반드시 양수 보장

                    f.r = nr;
                    f.c = nc;
                    f.flag = turnFlag;
                    map[nr][nc].add(f);
                    map[i][j].remove(idx--);
                }
            }
        }
    }

    public static void sumAndDivide() {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int size = map[i][j].size();
                if(size < 2) continue;

                // sum
                int mSum = 0, sSum = 0;
                int oddCnt = 0, evenCnt = 0;
                for(Fireball f : map[i][j]) {
                    mSum += f.m;
                    sSum += f.s;
                    if(f.d % 2 != 0) oddCnt += 1;
                    if(f.d % 2 == 0) evenCnt += 1;
                }
                map[i][j].clear();  // 합쳐진 파이어볼들은 삭제해준다

                // divide
                int nm = mSum/5, ns = sSum/size, d = 1;
                if(nm == 0) continue;  // 질량이 0인 파이어볼은 사라진다
                if(oddCnt == size || evenCnt == size)
                    d = 0;  // 모두 홀수 or 모두 짝수이면 0,2,4,6
                for(int nd = d; nd <= 7; nd+=2) {
                    Fireball f = new Fireball(i, j, nm, ns, nd, turnFlag);
                    map[i][j].add(f);
                }
            }
        }
    }

    public static void process() {
        while(k-- > 0) {
            moveBall();
            sumAndDivide();
            turnFlag = !turnFlag;
        }
        calculate();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        map = new ArrayList[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                map[i][j] = new ArrayList<>();
            }
        }

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            int m = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            Fireball f = new Fireball(r, c, m, s, d, true);
            map[r][c].add(f);
        }

        process();
        System.out.println(ans);
    }
}

 

이틀동안 해맸다.

 

s를 처음 입력받을 때부터 % n해서 입력받았는데 그게 문제였다. 처음부터 속도를 % 으로 받아버리면 파이어볼이 합쳐진 후에 나눠지는 과정에서 ns가 제대로 된 값을 얻지 못한다.

 

n == 4에서 s == 7, s == 1 일 경우 8/2 로 ns == 4가 되어야 하는데..

%으로 받으면 3, 1로 들어가기 때문에 ns == 2가 되는 문제였다.

 

 

근데 위 코드보다는 아래 방법이 더 나은 듯 하다.

 

1. Fireball을 담는 1차원 list 하나를 따로 둔다.

2. map[][]에는 int[]를 담고, 거기에는 "1."의 리스트의 인덱스를 담는다.

3. moveBall에서는 newMap[][]을 만들어 이동한 위치에 인덱스를 담은 후 map = newMap으로 덮어씌운다.

4. sumAndDivide에서는 newList를 만들어서 처리 후 덮어씌운다.

 

 

 

 

www.acmicpc.net/problem/19237

 

19237번: 어른 상어

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미

www.acmicpc.net

문제

청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.

N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.

각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.

모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.

<그림 1>

우선 순위상어 1상어 2상어 3상어 4↑↑↑↑↓↓↓↓←←←←→→→→

↓ ← ↑ → ↓ → ← ↑ → ← ↓ ↑ ← → ↑ ↓
→ ↑ ↓ ← ↓ ↑ ← → ↑ → ← ↓ ← ↓ → ↑
← → ↓ ↑ ← → ↑ ↓ ↑ ← ↓ → ↑ → ↓ ←
→ ← ↑ ↓ → ↑ ↓ ← ← ↓ ↑ → ↑ → ↓ ←

<표 1>

<그림 1>은 맨 처음에 모든 상어가 자신의 냄새를 뿌린 상태를 나타내며, <표 1>에는 각 상어 및 현재 방향에 따른 우선순위가 표시되어 있다. 이 예제에서는 k = 4이다. 왼쪽 하단에 적힌 정수는 냄새를 의미하고, 그 값은 사라지기까지 남은 시간이다. 좌측 상단에 적힌 정수는 상어의 번호 또는 냄새를 뿌린 상어의 번호를 의미한다.

<그림 2>

<그림 3>

<그림 2>는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태이고, <그림 3>은 <그림 2>의 상태에서 한 칸 더 이동한 것이다. (2, 4)에는 상어 2과 4가 같이 도달했기 때문에, 상어 4는 격자 밖으로 쫓겨났다.

<그림 4>

<그림 5>

<그림 4>은 격자에 남아있는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태, <그림 5>는 <그림 4>에서 한 칸 더 이동한 상태를 나타낸다. 상어 2는 인접한 칸 중에 아무 냄새도 없는 칸이 없으므로 자신의 냄새가 들어있는 (2, 4)으로 이동했다. 상어가 이동한 후에, 맨 처음에 각 상어가 뿌린 냄새는 사라졌다.

이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.

입력

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)

그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.

그 다음 줄에는 각 상어의 방향이 차례대로 주어진다. 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.

그 다음 줄부터 각 상어의 방향 우선순위가 상어 당 4줄씩 차례대로 주어진다. 각 줄은 4개의 수로 이루어져 있다. 하나의 상어를 나타내는 네 줄 중 첫 번째 줄은 해당 상어가 위를 향할 때의 방향 우선순위, 두 번째 줄은 아래를 향할 때의 우선순위, 세 번째 줄은 왼쪽을 향할 때의 우선순위, 네 번째 줄은 오른쪽을 향할 때의 우선순위이다. 각 우선순위에는 1부터 4까지의 자연수가 한 번씩 나타난다. 가장 먼저 나오는 방향이 최우선이다. 예를 들어, 우선순위가 1 3 2 4라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.

맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.

출력

1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.

예제 입력 1 복사

5 4 4

0 0 0 0 3

0 2 0 0 0

1 0 0 0 4

0 0 0 0 0

0 0 0 0 0

4 4 3 1

2 3 1 4

4 1 2 3

3 4 2 1

4 3 1 2

2 4 3 1

2 1 3 4

3 4 1 2

4 1 2 3

4 3 2 1

1 4 3 2

1 3 2 4

3 2 1 4

3 4 1 2

3 2 4 1

1 4 2 3

1 4 2 3

예제 출력 1

14

문제에 나온 그림과 같다.

예제 입력 2

4 2 6

1 0 0 0

0 0 0 0

0 0 0 0

0 0 0 2

4 3

1 2 3 4

2 3 4 1

3 4 1 2

4 1 2 3

1 2 3 4

2 3 4 1

3 4 1 2

4 1 2 3

예제 출력 2

26

예제 입력 3

5 4 1

0 0 0 0 3

0 2 0 0 0

1 0 0 0 4

0 0 0 0 0

0 0 0 0 0

4 4 3 1

2 3 1 4

4 1 2 3

3 4 2 1

4 3 1 2

2 4 3 1

2 1 3 4

3 4 1 2

4 1 2 3

4 3 2 1

1 4 3 2

1 3 2 4

3 2 1 4

3 4 1 2

3 2 4 1

1 4 2 3

1 4 2 3

예제 출력 3

-1

예제 입력 4

5 4 10

0 0 0 0 3

0 0 0 0 0

1 2 0 0 0

0 0 0 0 4

0 0 0 0 0

4 4 3 1

2 3 1 4

4 1 2 3

3 4 2 1

4 3 1 2

2 4 3 1

2 1 3 4

3 4 1 2

4 1 2 3

4 3 2 1

1 4 3 2

1 3 2 4

3 2 1 4

3 4 1 2

3 2 4 1

1 4 2 3

1 4 2 3

예제 출력 4

-1

 

 

 

 

 

 

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 *
 * 다른 상어의 냄새가 있는 곳으로는 가지 않는다.
 * 즉, 여러 상어가 한 칸에서 만나는 경우는 그 칸이 빈 칸으로 존재했을 경우에만 가능하다.
 *
 * 냄새의 카운트는 그 칸에 도착해서 냄새를 남긴 순간도 포함해서 센다.
 * 내 냄새가 있는 칸으로 이동한 경우에는 그냥 있던 냄새를 덮어버리고 다시 K부터  카운트 시작
 *
 * 결국 두 작업을 반복해서 하는 것.
 * 1. 냄새를 남긴다
 * 2. 이동한다
 *
 * 상어를 담는 배열과 냄새를 담는 배열 두 개를 따로 사용하는 게 좋을 듯
 *
 */

class Smell {
    int num, time;
    Smell(int num, int time) {
        this.num = num;
        this.time = time;
    }
}

class Shark {
    int r, c, num, dir;
    Shark(int r, int c, int num) {
        this.r = r;
        this.c = c;
        this.num = num;
    }
}

public class Main {
    static int n, m, k, sharkNum, ans;
    static Shark[] sharkArr;
    static Smell[][] smell;
    static int[][] map;
    static int[][][] prior;  // 각 상어의 방향에 대한 우선순위  [num][현재방향][우선순위] == 방향
    static int[] rArr = {0, -1, 1, 0, 0};  // 0상하좌우
    static int[] cArr = {0, 0, 0, -1, 1};

    public static void smelling() {
        for(Shark s : sharkArr) {
            if(s == null) continue;
            int r = s.r, c = s.c, num = s.num;
            if(smell[r][c] == null) {  // 빈 칸으로 들어옴
                smell[r][c] = new Smell(num, k);
            }else {  // 내 냄새가 있는 칸으로 들어옴
                smell[r][c].time = k;
            }
        }
    }

    public static void runOutOfSmellTime() {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(smell[i][j] != null) {
                    if(smell[i][j].time == 1) {
                        smell[i][j] = null;
                    }else {
                        smell[i][j].time -= 1;
                    }
                }
            }
        }
    }

    public static void moveShark() {
        // 같은 칸에 여러 상어 오면 제거하는 로직도 여기서 수행
        for(Shark s : sharkArr) {
            if(s == null) continue;

            boolean find = false;
            int r = s.r, c = s.c, num = s.num, dir = s.dir;

            // 빈 칸 체크
            for(int i = 1; i <= 4; i++) {
                int nd = prior[num][dir][i];  // 현 상태에서 i번째 우선운위를 갖는 방향
                int nr = r + rArr[nd];
                int nc = c + cArr[nd];

                if(-1 < nr && nr < n && -1 < nc && nc < n) {
                    if(smell[nr][nc] == null) {  // 남의 냄새가 없는 빈 칸
                        // 이미 빈 칸에 다른 상어가 있으면 대결을 해야 함
                        if(map[nr][nc] == 0) {  // 아무 상어도 없음
                            map[r][c] = 0; map[nr][nc] = num;
                            s.r = nr; s.c = nc; s.dir = nd;
                        }else {  // 다른 상어를 만남
                            if(map[nr][nc] < num) {   // 미리 와있던 상어가 더 쏌
                                sharkArr[num] = null;  // 나 죽음
                                sharkNum -= 1;
                                map[r][c] = 0;
                            }else {
                                sharkArr[map[nr][nc]] = null;  // 미리 와있던 상어 죽음
                                sharkNum -= 1;
                                map[r][c] = 0; map[nr][nc] = num;
                                s.r = nr; s.c = nc; s.dir = nd;
                            }
                        }
                        find = true;
                        break;
                    }
                }
            }
            if(find) continue;

            // 빈 칸이 없는 경우 자기 냄새 있는 칸 체크
            for(int i = 1; i <= 4; i++) {
                int nd = prior[num][dir][i];
                int nr = r + rArr[nd];
                int nc = c + cArr[nd];

                if(-1 < nr && nr < n && -1 < nc && nc < n) {
                    // 여기선 대결을 고려할 필요가 없다
                    // 다른 상어의 냄새가 있는 곳으로 가는 경우는 없기 때문
                    if(smell[nr][nc].num == num) {  // 내 냄새인 경우
                        map[r][c] = 0; map[nr][nc] = num;
                        s.r = nr; s.c = nc; s.dir = nd;
                        break;
                    }
                }
            }
        }
    }

    public static void process() {
        while(sharkNum != 1) {
            smelling();  // 냄새 남긴다
            moveShark();  // 다음 칸으로 이동한다
            runOutOfSmellTime();  // smell time을 줄인다
            ans += 1;
            if(ans > 1000) return;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        sharkNum = m;

        sharkArr = new Shark[m+1];
        map = new int[n][n];
        smell = new Smell[n][n];
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] != 0) {
                    sharkArr[map[i][j]] = new Shark(i, j, map[i][j]);  // idx == 상어의 번호
                }
            }
        }

        // 상어들의 처음 방향 일괄 입력
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= m; i++) {
            sharkArr[i].dir = Integer.parseInt(st.nextToken());
        }

        // 상어들의 방향 우선 순위
        prior = new int[m+1][5][5];  // 행 번호를 상어 번호와 맞춰주기 위해 m+1행
        for(int num = 1; num <= m; num++) {
            for(int i = 1; i <= 4; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j = 1; j <= 4; j++) {
                    prior[num][i][j] = Integer.parseInt(st.nextToken());
                }
            }
        }

        process();  // 1001초가 되면 강제 return 하여 -1 출력
        System.out.println(ans > 1000 ? -1 : ans);  // 1000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.
    }
}

 

빡빡빡구현 문제.

 

특별히 어려운 내용은 없지만 그냥 구현 자체가 어렵다.

 

조건도 많아서 까다로웠다.

 

 

 

 

www.acmicpc.net/problem/19236

 

19236번: 청소년 상어

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는

www.acmicpc.net

문제

아기 상어가 성장해 청소년 상어가 되었다.

4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.

오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.

물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.

물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

<그림 1>

<그림 1>은 청소년 상어가 공간에 들어가기 전 초기 상태이다. 상어가 공간에 들어가면 (0, 0)에 있는 7번 물고기를 먹고, 상어의 방향은 ↘이 된다. <그림 2>는 상어가 들어간 직후의 상태를 나타낸다.

<그림 2>

이제 물고기가 이동해야 한다. 1번 물고기의 방향은 ↗이다. ↗ 방향에는 칸이 있고, 15번 물고기가 들어있다. 물고기가 있는 칸으로 이동할 때는 그 칸에 있는 물고기와 위치를 서로 바꿔야 한다. 따라서, 1번 물고기가 이동을 마치면 <그림 3>과 같아진다.

<그림 3>

2번 물고기의 방향은 ←인데, 그 방향에는 상어가 있으니 이동할 수 없다. 방향을 45도 반시계 회전을 하면 ↙가 되고, 이 칸에는 3번 물고기가 있다. 물고기가 있는 칸이니 서로 위치를 바꾸고, <그림 4>와 같아지게 된다.

<그림 4>

3번 물고기의 방향은 ↑이고, 존재하지 않는 칸이다. 45도 반시계 회전을 한 방향 ↖도 존재하지 않으니, 다시 회전을 한다. ← 방향에는 상어가 있으니 또 회전을 해야 한다. ↙ 방향에는 2번 물고기가 있으니 서로의 위치를 교환하면 된다. 이런 식으로 모든 물고기가 이동하면 <그림 5>와 같아진다.

<그림 5>

물고기가 모두 이동했으니 이제 상어가 이동할 순서이다. 상어의 방향은 ↘이고, 이동할 수 있는 칸은 12번 물고기가 있는 칸, 15번 물고기가 있는 칸, 8번 물고기가 있는 칸 중에 하나이다. 만약, 8번 물고기가 있는 칸으로 이동하면, <그림 6>과 같아지게 된다.

<그림 6>

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.

입력

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

출력

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.

예제 입력 1

7 6 2 3 15 6 9 8

3 1 1 8 14 7 10 1

6 1 13 6 4 3 11 4

16 1 8 7 5 2 12 2

예제 출력 1

33

예제 입력 2

16 7 1 4 4 3 12 8

14 7 7 6 3 4 10 2

5 2 15 2 8 3 6 4

11 8 2 4 13 5 9 4

예제 출력 2

43

예제 입력 3

12 6 14 5 4 5 6 7

15 1 11 7 3 7 7 5

10 3 8 3 16 6 1 1

5 8 2 7 13 6 9 2

예제 출력 3

76

예제 입력 4

2 6 10 8 6 7 9 4

1 7 16 6 4 2 5 8

3 7 8 6 7 6 14 8

12 7 15 4 11 3 13 3

예제 출력 4

39

 

 

 

 

 

 

 

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Fish {
    int num, dir;
    Fish(int num, int dir) {
        this.num = num;
        this.dir = dir;
    }
}

public class Main {
    static int ans;
    static Fish[][] map;
    static boolean[] check;  // true == 잡아먹힌 샏선
    static int[] rArr = {-1, -1, 0, 1, 1, 1, 0, -1};  // 12시 방향부터 45도씩 반시계 회전
    static int[] cArr = {0, -1, -1, -1, 0, 1, 1, 1};

    public static void swap(int r, int c, int nr, int nc) {
        Fish temp = map[r][c];
        map[r][c] = map[nr][nc];
        map[nr][nc] = temp;
    }

    public static boolean isMovable(int nr, int nc) {
        if(-1 < nr && nr < 4 && -1 < nc && nc < 4) {
            if(map[nr][nc] == null || map[nr][nc].num != 0) {  // 빈칸이거나 상어가 아니거나
                return true;
            }
        }
        return false;
    }

    public static boolean isEatable(int r, int c, int dir) {
        for(int i = 1; i < 4; i++) {  // 최대 3칸 이동 가능
            int nr = r + rArr[dir] * i;
            int nc = c + cArr[dir] * i;
            if(-1 < nr && nr < 4 && -1 < nc && nc < 4) {
                if(map[nr][nc] != null) {  // 물고기가 있는 칸이 하나라도 있으면 eatable
                    return true;
                }
            }else {
                return false;
            }
        }
        return false;
    }

    public static void moveFish() {
        for(int fishNum = 1; fishNum <= 16; fishNum++) {
            if(!check[fishNum]) {  // 아직 먹히지 않은 생선만 이동 가능
                boolean find = false;
                Fish fish = null;

                // 일단 map에서 대상 fish 찾는다
                int r = 0, c = 0;
                for(int i = 0; i < 4; i++) {
                    for(int j = 0; j < 4; j++) {
                        if(map[i][j] != null && map[i][j].num == fishNum) {  // 찾았다
                            find = true;
                            fish = map[i][j];
                            r = i;
                            c = j;
                            break;
                        }
                    }
                    if(find) break;
                }

                // 이동 가능한 칸을 찾아 최대 7번 회전
                int dir = fish.dir;  // 최초 방향 기억
                for(int i = 0; i < 8; i++) {
                    fish.dir = (dir + i) % 8;  // 회전한 방향으로 이동이 불가해도 방향은 유지한다
                    int nr = r + rArr[fish.dir];
                    int nc = c + cArr[fish.dir];

                    if(isMovable(nr, nc)) {
                        swap(r, c, nr, nc);
                        break;
                    }
                }
            }
        }
    }

    public static Fish[][] deepCopyArr(Fish[][] arr) {
        Fish[][] temp = new Fish[4][4];
        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 4; j++) {
                if(arr[i][j] == null) {
                    temp[i][j] = null;
                }else {
                    temp[i][j] = new Fish(arr[i][j].num, arr[i][j].dir);
                }
            }
        }
        return temp;
    }

    public static void dfs(int r, int c, int dir, int sum) {
        moveFish();  // 생선 이동

        if(!isEatable(r, c, dir)) {  // 더 이상 먹을 수 없게 되면 최대값 갱신
            ans = Math.max(ans, sum);
            return;
        }

        Fish[][] tempArr = deepCopyArr(map);  // 현재 map 상태 기억
        for(int i = 1; i < 4; i++) {  // 최대 3칸 이동 가능
            int nr = r + rArr[dir] * i;
            int nc = c + cArr[dir] * i;

            if(-1 < nr && nr < 4 && -1 < nc && nc < 4) {
                if(map[nr][nc] != null) {  // 다음 칸에 물고기 있는지?
                    int num = map[nr][nc].num;
                    int nd = map[nr][nc].dir;
                    check[num] = true;
                    swap(r, c, nr, nc);  // 상어와 물고기의 swap으로 잡아먹기 표현
                    map[r][c] = null;  // 잡아먹힌 물고기 제거
                    map[nr][nc].dir = nd;  // 잡아먹은 물고기의 방향을 이어받는다

                    dfs(nr, nc, nd, sum + num);

                    check[num] = false;
                    map = deepCopyArr(tempArr);
                }
            }else {
                break;  // 범위 벗어났으면 더 검사할 필요 없음
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        map = new Fish[4][4];
        check = new boolean[17];
        for(int i = 0; i < 4; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 4; j++) {
                int num = Integer.parseInt(st.nextToken());
                int dir = Integer.parseInt(st.nextToken()) - 1;  // 방향은 1~8로 주어지므로 -1 해줘야 함
                map[i][j] = new Fish(num, dir);
            }
        }

        // [0][0] 물고기 잡아먹으면서 시작
        int num = map[0][0].num;
        int dir = map[0][0].dir;
        check[num] = true;
        map[0][0].num = 0;  // 상어가 들어감
        dfs(0, 0, dir, num);
        System.out.println(ans);
    }
}

 

삐끗할 요소가 너무 많은 구현 문제.

백트래킹 과정에서 deep copy한 배열을 덮어 씌워줘야 한다.

 

 

 

 

www.acmicpc.net/problem/16236

 

16236번: 아기 상어

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가

www.acmicpc.net

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

  • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
  • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
    • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
    • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

  • 0: 빈 칸
  • 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
  • 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

예제 입력 1

3

0 0 0

0 0 0

0 9 0

예제 출력 1

0

예제 입력 2

3

0 0 1

0 0 0

0 9 0

예제 출력 2

3

예제 입력 3

4

4 3 2 1

0 0 0 0

0 0 9 0

1 2 3 4

예제 출력 3

14

예제 입력 4

6

5 4 3 2 3 4

4 3 2 3 4 5

3 2 9 5 6 6

2 1 2 3 4 5

3 2 1 6 5 4

6 6 6 6 6 6

예제 출력 4

60

예제 입력 5

6

6 0 6 0 6 1

0 0 0 0 0 2

2 3 4 5 6 6

0 0 0 0 0 2

0 2 0 0 0 0

3 9 3 0 0 1

예제 출력 5

48

예제 입력 6

6

1 1 1 1 1 1

2 2 6 2 2 3

2 2 5 2 2 3

2 2 2 4 6 3

0 0 0 0 0 6

0 0 0 0 0 9

예제 출력 6

39

 

 

 

 

 

 

 

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * 접근 방식
 *   1. 현재 위치에서 먹을 수 있는 생선의 위치를 찾는 bfs
 *     1.1 먹을 수 있는 생선을 찾았다면? -> 그 거리를 넘어가는 탐색은 더 이상 하지 않음
 *       1.1.1 먹을 수 있는 생선들 중 조건에 맞는 생선의 위치로 이동
 *       1.1.2 상어 크기 키울 수 있다면 키움
 *       1.1.3 1번부터 다시 수행
 *
 *     1.2 먹을 수 있는 생선을 찾지 못하고 모든 map을 탐색했다면? -> 그대로 종료
 *
 */

class Pair implements Comparable<Pair> {
    int r, c, dist;
    Pair(int r, int c, int dist) {
        this.r = r;
        this.c = c;
        this.dist = dist;  // 상어로부터의 거리
    }

    // dist는 검사 기준으로 둘 필요 없다
    // 어차피 한 번의 bfs에서 같은 거리에 존재하는 생선들만 pq에 들어가기 때문
    @Override
    public int compareTo(Pair o) {
        if(this.r != o.r) {
            return (this.r < o.r) ? -1 : 1;
        }else {
            return (this.c < o.c) ? -1 : 1;
        }
    }
}

public class Main {
    static int n, ans, eatCnt, sharkSize = 2;
    static boolean find;  // 먹을 수 있는 생선 찾았는지
    static int[][] map;
    static boolean[][] check;
    static int[] rArr = {-1, 1, 0, 0};
    static int[] cArr = {0, 0, -1, 1};

    static Pair shark;
    static Queue<Pair> que;
    static PriorityQueue<Pair> fishes;  // eatable fish

    public static void bfs(int r, int c) {
        check = new boolean[n][n];
        que = new ArrayDeque<>();
        fishes = new PriorityQueue<>();
        check[r][c] = true;
        que.add(shark);

        int eatableDist = Integer.MAX_VALUE;
        while(!que.isEmpty()) {
            Pair p = que.poll();

            // p.dist + 1 거리에서 먹을 수 있다 하더라도 이미 최소 거리 초과
            // 즉, 더 이상 eatable fish를 찾을 필요 없음
            if(p.dist == eatableDist) break;

            for(int i = 0; i < 4; i++) {
                int nr = p.r + rArr[i];
                int nc = p.c + cArr[i];

                if(-1 < nr && nr < n && -1 < nc && nc < n && !check[nr][nc]) {
                    check[nr][nc] = true;

                    if(map[nr][nc] <= sharkSize) {  // 이동 가능
                        que.add(new Pair(nr, nc, p.dist + 1));
                        if(map[nr][nc] != 0 && map[nr][nc] < sharkSize) {  // 먹을 수 있음
                            if(!find) {  // eatableDist가 계속 갱신되는 것을 막기 위한 조건
                                find = true;
                                eatableDist = p.dist + 1;
                            }
                            fishes.add(new Pair(nr, nc, p.dist + 1));
                        }
                    }
                }
            }
        }
    }

    public static void process() {
        while(true) {
            find = false;
            bfs(shark.r, shark.c);

            if(!find) {  // 이동 가능한 모든 칸 이동해도 먹을 수 없음
                break;
            }else {  // 먹을 수 있는 물고기 존재
                Pair p = fishes.peek();
                map[shark.r][shark.c] = 0;
                map[p.r][p.c] = 9;  // 상어 위치 이동. 사실 굳이 계속 9값을 유지할 필요는 없음.
                ans += p.dist;  // 이동 시간 추가

                shark = new Pair(p.r, p.c, 0);
                if(sharkSize == ++eatCnt) {  // 횟수 채웠으면 상어 사이즈 업
                    eatCnt = 0;
                    sharkSize += 1;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        map = new int[n][n];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 9) {
                    shark = new Pair(i, j, 0);
                }
            }
        }

        process();
        System.out.println(ans);
    }
}

 

도저히 모르겠어서 코드는 안 보고 해법만 봤다.

 

근데 그걸 구현하는 것도 3시간이 걸렸다.

 

접근 방식

->

1. 현재 위치에서 먹을 수 있는 생선의 위치를 찾는 bfs

* 1.1 먹을 수 있는 생선을 찾았다면? -> 그 거리를 넘어가는 탐색은 더 이상 하지 않음
* 1.1.1 먹을 수 있는 생선들 중 조건에 맞는 생선의 위치로 이동
* 1.1.2 상어 크기 키울 수 있다면 키움
* 1.1.3 1번부터 다시 수행
*
* 1.2 먹을 수 있는 생선을 찾지 못하고 모든 map을 탐색했다면? -> 그대로 종료

 

 

물고기를 한 번 찾을 때마다 bfs를 한 번 씩, 더 이상 먹을 수 있는 생선이 없을 때까지 bfs를 계속 도는 것이 포인트.

(먹을 수 있는 물고기를 찾았다면 딱 그 거리만큼만 탐색을 진행하고 bfs를 종료한다.)

이를 위해 Queue, PriorityQueue, boolean[][] 모두 bfs를 돌 때마다 새로 초기화를 해줘야 한다.

 

bfs를 한 번 수행한 후에는 map을 올바르게 수정해줘야 하는 것도 놓치기 쉬운 포인트.

 

 

 

 

www.acmicpc.net/problem/7662

 

7662번: 이중 우선순위 큐

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적

www.acmicpc.net

문제

이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 

정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. 

Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.

입력

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적용할 연산의 개수를 나타내는 정수 k (k ≤ 1,000,000)가 주어진다. 이어지는 k 줄 각각엔 연산을 나타내는 문자(‘D’ 또는 ‘I’)와 정수 n이 주어진다. ‘I n’은 정수 n을 Q에 삽입하는 연산을 의미한다. 동일한 정수가 삽입될 수 있음을 참고하기 바란다. ‘D 1’는 Q에서 최댓값을 삭제하는 연산을 의미하며, ‘D -1’는 Q 에서 최솟값을 삭제하는 연산을 의미한다. 최댓값(최솟값)을 삭제하는 연산에서 최댓값(최솟값)이 둘 이상인 경우, 하나만 삭제됨을 유념하기 바란다.

만약 Q가 비어있는데 적용할 연산이 ‘D’라면 이 연산은 무시해도 좋다. Q에 저장될 모든 정수는 32-비트 정수이다. 

출력

출력은 표준출력을 사용한다. 각 테스트 데이터에 대해, 모든 연산을 처리한 후 Q에 남아 있는 값 중 최댓값과 최솟값을 출력하라. 두 값은 한 줄에 출력하되 하나의 공백으로 구분하라. 만약 Q가 비어있다면 ‘EMPTY’를 출력하라.

예제 입력 1

2

7

I 16

I -5643

D -1

D 1

D 1

I 123

D -1

9

I -45

I 653

D 1

I -642

I 45

I 97

D 1

D -1

I 333

예제 출력 1

EMPTY

333 -45

 

 

 

 

 

 

 

풀이 1. (틀린 코드 - 시간 초과)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

        int T = Integer.parseInt(br.readLine());
        while(T-- > 0) {
            PriorityQueue<Integer> maxQue = new PriorityQueue<>(Collections.reverseOrder());
            PriorityQueue<Integer> minQue = new PriorityQueue<>();

            int n = Integer.parseInt(br.readLine());
            while(n-- > 0) {
                st = new StringTokenizer(br.readLine());
                String str = st.nextToken();
                int num = 0;
                switch(str) {
                    case "D" :
                        if(maxQue.isEmpty()) break;

                        num = Integer.parseInt(st.nextToken());
                        if(num == 1) {
                            int max = maxQue.poll();
                            minQue.remove(max);
                        }else {
                            int min = minQue.poll();
                            maxQue.remove(min);
                        }
                        break;
                    case "I" :
                        num = Integer.parseInt(st.nextToken());
                        maxQue.add(num);
                        minQue.add(num);
                        break;
                }
            }

            if(maxQue.isEmpty()) {
                sb.append("EMPTY\n");
            }else {
                sb.append(maxQue.poll() + " " + minQue.poll() + "\n");
            }
        }
        System.out.println(sb.toString());
    }
}

 

로직은 맞지만 시간 초과다.

 

PriorityQueue는 Heap으로 이루어져 있다.

그리고 remove(Object o) 에 대해서 O(N)의 시간이 소요된다.

 

 

 

 

 

풀이 2. (정답 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;
        int T = Integer.parseInt(br.readLine());

        while(T-- > 0) {
            TreeMap<Integer, Integer> treeMap = new TreeMap<>();
            int n = Integer.parseInt(br.readLine());

            while(n-- > 0) {
                st = new StringTokenizer(br.readLine());
                String str = st.nextToken();
                int num = Integer.parseInt(st.nextToken());

                switch(str) {
                    case "I" :
                        treeMap.put(num, treeMap.getOrDefault(num, 0) + 1);
                        break;
                    case "D" :
                        if(treeMap.isEmpty()) break;
                        if(num == -1) {
                            int minKey = treeMap.firstKey();
                            if(treeMap.get(minKey) == 1) {
                                treeMap.remove(minKey);
                            }else {
                                treeMap.put(minKey, treeMap.get(minKey) - 1);
                            }
                        }else {
                            int maxKey = treeMap.lastKey();
                            if(treeMap.get(maxKey) == 1) {
                                treeMap.remove(maxKey);
                            }else {
                                treeMap.put(maxKey, treeMap.get(maxKey) - 1);
                            }
                        }
                        break;
                }
            }

            if(treeMap.isEmpty()) {
                sb.append("EMPTY\n");
            }else {
                sb.append(treeMap.lastKey() + " " + treeMap.firstKey() + "\n");
            }
        }
        System.out.println(sb.toString());
    }
}

 

TreeMap을 사용한 풀이.

TreeMap은 Red-Black Tree로 구현되어있다.

 

TreeMap은 Key값을 기준으로 정렬된 상태를 유지한다.

그렇기 때문에 원하는 순서의 원소에 접근할 수 있다.

firstKey(), lastKey()로 양 끝 값에 편리하게 접근할 수 있다.

 

또한, 원소의 추가, 삭제 이후에 정렬 상태를 유지하고 균형잡힌 트리 모양을 유지하는것까지 전부 합쳐서 O(logN)의 시간만을 소요한다.

 

 

 

 

 

 

www.acmicpc.net/problem/11723

 

11723번: 집합

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

www.acmicpc.net

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

  • add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
  • remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
  • check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
  • toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
  • all: S를 {1, 2, ..., 20} 으로 바꾼다.
  • empty: S를 공집합으로 바꾼다. 

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

예제 입력 1

26

add 1

add 2

check 1

check 2

check 3

remove 2

check 1

check 2

toggle 3

check 1

check 2

check 3

check 4

all

check 10

check 20

toggle 10

remove 20

check 10

check 20

empty

check 1

toggle 1

check 1

toggle 1

check 1

예제 출력 1

1

1

0

1

0

1

0

1

0

1

1

0

0

0

1

0

 

 

 

 

 

 

 

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

        int n = Integer.parseInt(br.readLine());
        int S = 0;
        while(n-- > 0) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            int num = 0;

            switch(str) {
                case "add" :
                    num = Integer.parseInt(st.nextToken()) - 1;
                    S = S | (1 << num);
                    break;
                case "remove" :
                    num = Integer.parseInt(st.nextToken()) - 1;
                    S = S & ~(1 << num);
                    break;
                case "check" :
                    num = Integer.parseInt(st.nextToken()) - 1;
                    int temp = S & (1 << num);
                    sb.append(((temp == 0) ? 0 : 1) + "\n");
                    break;
                case "toggle" :
                    num = Integer.parseInt(st.nextToken()) - 1 ;
                    S = S ^ (1 << num);
                    break;
                case "all" :
                    S = (1 << 21) - 1;
                    break;
                case "empty" :
                    S = 0;
                    break;
            }
        }
        System.out.println(sb.toString());
    }
}

 

기본적인 비트연산을 사용한 비트마스킹 문제.

 

예전에 비트마스킹을 공부할 기회가 있었으나 어려워보여서 외면하고 다른 쪽으로 넘어갔었다.

그렇게 다른 알고리즘만 공부하다가 비트마스킹의 효용성에 대해 알게 되어 지금이라도 익혀둬야겠다 싶었다.

 

하나의 정수를 이진수로 바꿨을 때, 특정 자리수의 비트가 1인지 0인지 판별하거나 특정 비트를 더하거나 빼거나 바꾸는 것을 비트연산을 통해 활 수 있다.

 

 

주의할 점,

20자리의 이진수가 있을 때, 각 비트의 자리수는 0~19이다.

문제에서는 1~20에 대한 입력으 받기 때문에 -1을 해주어 0~19로 맞춰줘야 한다.

 

 

 

 

programmers.co.kr/learn/courses/30/lessons/72411

 

코딩테스트 연습 - 메뉴 리뉴얼

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서

programmers.co.kr

문제 설명

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.
기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.
단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면,
(각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)

손님 번호주문한 단품메뉴 조합

1번 손님 A, B, C, F, G
2번 손님 A, C
3번 손님 C, D, E
4번 손님 A, C, D, E
5번 손님 B, C, F, G
6번 손님 A, C, D, E, H

가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.

코스 종류메뉴 구성설명

요리 2개 코스 A, C 1번, 2번, 4번, 6번 손님으로부터 총 4번 주문됐습니다.
요리 3개 코스 C, D, E 3번, 4번, 6번 손님으로부터 총 3번 주문됐습니다.
요리 4개 코스 B, C, F, G 1번, 5번 손님으로부터 총 2번 주문됐습니다.
요리 4개 코스 A, C, D, E 4번, 6번 손님으로부터 총 2번 주문됐습니다.

[문제]

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

[제한사항]

  • orders 배열의 크기는 2 이상 20 이하입니다.
  • orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
    • 각 문자열은 알파벳 대문자로만 이루어져 있습니다.
    • 각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
  • course 배열의 크기는 1 이상 10 이하입니다.
    • course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬되어 있습니다.
    • course 배열에는 같은 값이 중복해서 들어있지 않습니다.
  • 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return 해주세요.
    • 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.
    • 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
    • orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.

[입출력 예]

orderscourseresult

["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"] [2,3,4] ["AC", "ACDE", "BCFG", "CDE"]
["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"] [2,3,5] ["ACD", "AD", "ADE", "CD", "XYZ"]
["XYZ", "XWY", "WXA"] [2,3,4] ["WX", "XY"]

입출력 예에 대한 설명


입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
AD가 세 번, CD가 세 번, ACD가 두 번, ADE가 두 번, XYZ 가 두 번 주문됐습니다.
요리 5개를 주문한 손님이 1명 있지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 5개로 구성된 코스요리는 새로 추가하지 않습니다.

입출력 예 #3
WX가 두 번, XY가 두 번 주문됐습니다.
3명의 손님 모두 단품메뉴를 3개씩 주문했지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 3개로 구성된 코스요리는 새로 추가하지 않습니다.
또, 단품메뉴를 4개 이상 주문한 손님은 없으므로, 요리 4개로 구성된 코스요리 또한 새로 추가하지 않습니다.

 

 

 

 

 

 

 

풀이 1. 

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

class Solution {
    int max, mapIdx;
    StringBuilder sb;
    Map<String, Integer>[] mapArr;
    boolean[] check;

    public void push() {
        Map<String, Integer> temp = mapArr[mapIdx];
        if(temp.get(sb.toString()) == null) {
            temp.put(sb.toString(), 1);
            max =  Math.max(max, 1);
        }else {
            temp.put(sb.toString(), temp.get(sb.toString()) + 1);
            max = Math.max(max, temp.get(sb.toString()));
        }
    }

    public void dfs(int deptNow, int dept, int idx, String order) {
        if(deptNow == dept) {
            push();  // 해당 조합 추가
            return;
        }

        int len = order.length();
        for(int i = idx; i < len; i++) {
            if(!check[i] && deptNow + (len - idx) >= dept) {
                sb.append(order.charAt(i));
                check[i] = true;

                dfs(deptNow+1, dept, i+1, order);

                sb.deleteCharAt(sb.length() - 1);
                check[i] = false;
            }
        }
    }

    public ArrayList<String> solution(String[] orders, int[] course) {
        // 초기화
        ArrayList<String> answer = new ArrayList<>();
        sb = new StringBuilder();
        mapArr = new HashMap[course.length];
        for(int i = 0; i < course.length; i++) {  // course.length 만큼 Map 가져야 한다
            mapArr[i] =  new HashMap<>();
        }

        // 순서 맞춰주기 위해 정렬
        for(int i = 0; i < orders.length; i++) {
            char[] arr = orders[i].toCharArray();
            Arrays.sort(arr);
            orders[i] = new String(arr);
        }

        // course[i]를 목표 dept로 하는 조합 생성
        for(int i = 0; i < course.length; i++) {
            max = 0;  // max 초기화
            for(int j = 0; j < orders.length; j++) {
                check = new boolean[orders[j].length()];
                dfs(0, course[i], 0, orders[j]);
            }
            mapIdx += 1;

            if(max < 2) continue;  // 최소 두 명 이상에게 주문된 조합이어야 함
            Map<String, Integer> temp = mapArr[i];
            for(String str : temp.keySet()) {
                if(temp.get(str) == max) {
                    answer.add(str);
                }
            }
        }

        Collections.sort(answer);
        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        /**
         *
         * ["XYZ", "XWY", "WXA"]	[2,3,4]	["WX", "XY"]
         */
        Solution sol = new Solution();
        String[] orders = {"XYZ", "XWY", "WXA"};
        int[] course = {2, 3, 4};

        ArrayList<String> ans = sol.solution(orders, course);
        for(String str : ans) {
            System.out.println(str);
        }
    }
}

 

 

 

 

 

풀이 2.

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

class Solution {
    int max, mapIdx;
    StringBuilder sb;
    Map<String, Integer>[] mapArr;

    public void push() {
        Map<String, Integer> temp = mapArr[mapIdx];
        if(temp.get(sb.toString()) == null) {
            temp.put(sb.toString(), 1);
            max =  Math.max(max, 1);
        }else {
            temp.put(sb.toString(), temp.get(sb.toString()) + 1);
            max = Math.max(max, temp.get(sb.toString()));
        }
    }

    public void dfs(int deptNow, int dept, int idx, String order) {
        if(deptNow == dept) {
            push();  // 해당 조합 추가
            return;
        }

        int len = order.length();
        if(idx < len && deptNow + (len - idx) >= dept) {
            // idx번째 포함
            sb.append(order.charAt(idx));
            dfs(deptNow+1, dept, idx+1, order);
            sb.deleteCharAt(sb.length() - 1);
            
            // idx번째 미포함
            dfs(deptNow, dept, idx+1, order);
        }
    }

    public ArrayList<String> solution(String[] orders, int[] course) {
        // 초기화
        ArrayList<String> answer = new ArrayList<>();
        sb = new StringBuilder();
        mapArr = new HashMap[course.length];
        for(int i = 0; i < course.length; i++) {  // course.length 만큼 Map 가져야 한다
            mapArr[i] =  new HashMap<>();
        }

        // 순서 맞춰주기 위해 정렬
        for(int i = 0; i < orders.length; i++) {
            char[] arr = orders[i].toCharArray();
            Arrays.sort(arr);
            orders[i] = new String(arr);
        }

        // course[i]를 목표 dept로 하는 조합 생성
        for(int i = 0; i < course.length; i++) {
            max = 0;  // max 초기화
            for(int j = 0; j < orders.length; j++) {
                dfs(0, course[i], 0, orders[j]);
            }
            mapIdx += 1;

            if(max < 2) continue;  // 최소 두 명 이상에게 주문된 조합이어야 함
            Map<String, Integer> temp = mapArr[i];
            for(String str : temp.keySet()) {
                if(temp.get(str) == max) {
                    answer.add(str);
                }
            }
        }

        Collections.sort(answer);
        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        /**
         *
         * ["XYZ", "XWY", "WXA"]	[2,3,4]	["WX", "XY"]
         */
        Solution sol = new Solution();
        String[] orders = {"XYZ", "XWY", "WXA"};
        int[] course = {2, 3, 4};

        ArrayList<String> ans = sol.solution(orders, course);
        for(String str : ans) {
            System.out.println(str);
        }
    }
}

 

조건

1. 최소 2명 이상에게 주문된 적 있는 조합.

2. 목표 dept에서 최다 주문 조합이 여러 개 존재한다면 모두 정답 처리.

 

courser[i] 마다 Map<String, Integer>를 하나씩 갖는다.

max값을 갱신해가며 key, value쌍을 업데이트 하고 마지막에 max값과 같은 value를 가진 key들을 모두 정답처리한다.

 

주의할 점,

입력된 값들이 오름차순임이 보장되지 않는다.

따라서 시작하기 전에 orders의 모든 원소들을 오름차순 정렬 처리를 먼저 해줘야 한다.

 

 

 

 

'알고리즘 문제 > 프로그래머스' 카테고리의 다른 글

[PG] 풍선 터트리기 JAVA  (0) 2021.02.26
[PG] 괄호 변환 JAVA  (0) 2021.02.26
[PG] 카카오프렌즈 컬러링북 JAVA  (0) 2021.02.25
[PG] 2016년 JAVA  (0) 2021.02.19
[PG] 삼각 달팽이 JAVA  (0) 2021.02.19

www.acmicpc.net/problem/19583

 

19583번: 싸이버개강총회

첫번째 줄에는 개강총회를 시작한 시간 S, 개강총회를 끝낸 시간 E, 개강총회 스트리밍을 끝낸 시간 Q가 주어진다. (00:00 ≤ S < E < Q ≤ 23:59) 각 시간은 HH:MM의 형식으로 주어진다. 두번째 줄부터는

www.acmicpc.net

문제

보영이는 알고리즘 동아리 HI-ARC를 운영하고 있다.

보영이와 운영진 일동은 20년도에 입학하는 신입생들을 맞이하기 위해 열심히 준비를 해왔으나, 전염병의 유행이 악화된 나머지 정부에서는 “사회적 거리두기”를 선언했고 그에 따라 학교에서는 교내 모든 동아리에 오프라인 모임을 자제하라는 공지를 하기에 이르렀다. 오프라인에서 모임을 자제하라는 권고가 나온 어려운 상황에도 불구하고, 보영이는 기지를 발휘하여 개강총회를 미튜브 스트리밍으로 대체하는 결정을 하게 된다.

하지만, 미튜브 스트리밍으로 개강총회를 하게 될 경우, 아래와 같은 문제가 있었다.

  1. 누가 개강총회에 왔는지 알 수 없다.
  2. 누가 개강총회 자리에 끝까지 남아있었는지 알 수 없다.
  3. 어떤 사람이 개강총회 스트리밍을 단순히 틀어놓기만 했는지 알 수 없다.

이런 문제를 해결하기 위해서, 다음과 같이 출석부를 관리하기로 결심했다.

  1. 개강총회를 시작하기 전에, 학회원의 입장 확인 여부를 확인한다. 학회원의 입장 여부는 개강총회가 시작한 시간 이전에 대화를 한 적이 있는 학회원의 닉네임을 보고 체크한다. 개강총회를 시작하자마자 채팅 기록을 남긴 학회원도 제 시간에 입장이 확인된 것으로 간주한다.
  2. 개강총회를 끝내고 나서, 스트리밍을 끝낼 때까지 학회원의 퇴장 확인 여부를 확인한다. 학회원의 퇴장 여부는 개강총회가 끝나고 스트리밍이 끝날 때까지 대화를 한 적이 있는 학회원의 닉네임을 보고 체크한다. 개강총회가 끝나자마자 채팅 기록을 남겼거나, 개강총회 스트리밍이 끝나자마자 채팅 기록을 남긴 학회원도 제 시간에 퇴장이 확인된 것으로 간주한다.  

단, 00:00부터는 개강총회를 시작하기 전의 대기 시간이며, 개강총회 스트리밍 끝난 시간 이후로 남겨져 있는 채팅 기록은 다른 스트리밍 영상의 채팅 기록으로 간주한다.

이 때, 입장부터 퇴장까지 모두 확인된 학회원은 전부 몇 명인가?

입력

첫번째 줄에는 개강총회를 시작한 시간 S, 개강총회를 끝낸 시간 E, 개강총회 스트리밍을 끝낸 시간 Q가 주어진다. (00:00 ≤ S < E < Q ≤ 23:59)
각 시간은 HH:MM의 형식으로 주어진다.

두번째 줄부터는 HI-ARC에서 방송하는 스트리밍 영상의 채팅 기록들이 시간순으로 주어지는데, (시간) (학회원 닉네임)의 형태로 주어진다. 학회원의 닉네임은 알파벳 대소문자와 숫자, 그리고 특수 기호(., _, -)로만 구성된 문자열이며 최대 20글자이다.

모든 채팅 기록은 개강총회가 일어난 날에 발생한 채팅 기록이다. 즉 00:00~23:59의 시간만 주어진다. 채팅 기록은 10만 줄을 넘지 않는다.

출력

출석이 확인된 학회원의 인원 수를 출력한다.

예제 입력 1

22:00 23:00 23:30

21:30 malkoring

21:33 tolelom

21:34 minjae705

21:35 hhan14

21:36 dicohy27

21:40 906bc

23:00 906bc

23:01 tolelom

23:10 minjae705

23:11 hhan14

23:20 dicohy27

예제 출력 1

5

예제 입력 2

06:00 12:00 18:00

06:00 shinyo17

06:00 kimchist

06:00 swoon

06:00 kheee512

06:00 Green55

09:00 kimchist

11:59 shinyo17

12:00 kimchist

17:59 swoon

17:59 swoon

18:00 kheee512

18:01 swoon

18:01 Green55

18:01 kheee512

18:01 swoon

18:21 jinius36

18:40 jeongyun1206

예제 출력 2

3

 

 

 

 

 

 

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String S = st.nextToken();
        String E = st.nextToken();
        String Q = st.nextToken();

        Set<String> before = new HashSet<>();
        Set<String> after = new HashSet<>();
        Set<String> nameSet = new HashSet<>();
        String str = null;
        
        while((str = br.readLine()) != null) {
            String[] arr = str.split(" ");
            String time = arr[0];
            String name = arr[1];

            nameSet.add(name);
            if(S.compareTo(time) >= 0) {
                before.add(name);
            }else if(E.compareTo(time) <= 0 && Q.compareTo(time) >= 0) {
                after.add(name);
            }
        }

        int ans = 0;
        for(String name : nameSet) {
            if(before.contains(name) && after.contains(name)) {
                ans += 1;
            }
        }
        System.out.println(ans);
    }
}

 

Hash의 짧은 검색 시간을 사용하는 문제.

 

시간의 흐름을 나타내보면 아래와 같다.

00:00  -  S(=개총 시작)  -  E(=개총 끝)  -  Q(스트리밍 종료)  -  23:59

 

위와 같은 구조에서 00:00 ~ S, E ~ Q 두 구간에 모두 포함된  사람의 수를 세는 것.

모든 시간의 입력은 HH:MM형식으로 동일하기 때문에 compareTo를 사용한 시간의 비교가 가능하다.

 

입력받는 채팅 기록의 개수나 입력을 종료하는 문자를 따로 받는 것이 아니기 떄문에

while((str = br.readLine()) != null) 으로 탈출 조건을 잡는다.

StringTokenizer를 사용하는 방법도 있을 거 같긴 한데 어떻게 해야할지는 잘 모르겠다.

 

 

 

 

 

 

 

 

'알고리즘 문제 > 백준 온라인 저지' 카테고리의 다른 글

[BOJ] 7662 - 이중 우선순위 큐 JAVA  (1) 2021.03.25
[BOJ] 11723 - 집합 JAVA  (0) 2021.03.25
[BOJ] 11286 - 절댓값 힙 JAVA  (0) 2021.03.24
[BOJ] 15683 - 감시 JAVA  (0) 2021.03.24
[BOJ] 2776 - 암기왕 JAVA  (0) 2021.03.23

+ Recent posts