Problem

• 문제 링크

배열이 주어졌을 때 가장 많이 나오는 숫자를 찾아 리턴하는 문제입니다.

가장 많이 나오는 빈도는 문제에 명시된 대로 배열의 길이 / 2 입니다.

Solution

여러가지 풀이가 존재할 수 있습니다.

시간 복잡도만 고려해서 HashMap 을 사용해서 숫자들의 카운트를 기록했는데 Discuss 를 보니 Moore Voting Algorithm 라는 더 좋은 해답이 있었습니다.

Sort 는 그냥 길이가 짧고 신기해서 넣었습니다.

Java Code

// 1. Using HashMap - Time: O(n), Space: O(n)
class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);

            if (count > nums.length / 2) {
                return num;
            }
        }

        return 0;
    }
}

// 2. Using Sort - Time: O(n logn), Space: O(1)
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

// 3. Using Moore Voting Algorithm (From Discuss)
// Time: O(n), Space: O(1)
class Solution {
    public int majorityElement(int[] nums) {
        int curr = 0;
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                curr = num;
            } 

            count += (curr == num) ? 1 : -1;
        }

        return curr;
    }
}

Kotlin Code

class Solution {
    fun majorityElement(nums: IntArray): Int {
        return nums.groupBy { it }
                   .filterValues { it.size > (nums.size / 2) }
                   .keys
                   .first()
    }
}

Problem

• 문제 링크

Excel 의 행이 문자열로 주어지면 몇 번째 행인지 계산하는 문제입니다.

Solution

문자열 뒤에서부터 계산해도 되는데 저는 앞에서부터 했습니다.

ABZ 라는 문자열을 받았다고 가정합니다.

수식으로 변경하면 다음과 같습니다.

(A * 26 * 26) + (B * 26) + Z

*26 을 밖으로 빼서 정리해서 다시 수식을 표현할 수 있습니다.

(((A * 26) + B) * 26) + Z

위 수식을 바탕으로 for 문을 돌립니다.

1. 시작 값은 0 이다.
2. 26 을 곱한다.
3. 문자를 더한다.

Java Code

class Solution {
    public int titleToNumber(String s) {
        int ret = 0;

        for (char c : s.toCharArray()) {
            ret *= 26;
            ret += c - 64;
        }

        return ret;
    }
}

Kotlin Code

class Solution {
    fun titleToNumber(s: String): Int {
        return s.toCharArray().fold(0) { total, num -> total * 26 + num.toInt() - 64 }
    }
}

Problem

• 문제 링크

난이도는 Easy

오름차순으로 정렬되어 있는 int 배열이 주어지면 높이가 1 이상 차이나지 않는 BST 를 만드는 문제입니다.

Solution

이분탐색 하듯이 트리를 순회하면 됩니다.

배열이 오름차순으로 되어 있기 때문에 중앙에 있는 값이 무조건 root 가 되야 합니다.

부모 노드 nums[mid] 를 만들고 나면 왼쪽 서브트리는 0 ~ mid - 1 로 만든 트리고 오른쪽 서브트리는 mid + 1 ~ nums.length - 1 로 만든 트리입니다.

Java Code

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return traverse(nums, 0, nums.length - 1);
    }

    public TreeNode traverse(int[] nums, int low, int high) {
        if (low > high) return null;

        int mid = low + (high - low)/2;

        return new TreeNode(
            nums[mid],
            traverse(nums, low, mid - 1),
            traverse(nums, mid + 1, high)
        );
    }
}

Kotlin Code

class Solution {
    fun sortedArrayToBST(
        nums: IntArray, 
        low: Int = 0, 
        high: Int = nums.size - 1
    ): TreeNode? {
        if (low > high) return null

        val mid = low + (high - low) / 2;

        return TreeNode(nums[mid]).apply {
            left = sortedArrayToBST(nums, low, mid - 1)
            right = sortedArrayToBST(nums, mid + 1, high)
        }
    }
}

Problem

• 문제 링크

주어진 맵을 5 개의 구역으로 나눕니다.

각 구역의 인구의 합을 구한 뒤 가장 큰 값과 가장 작은 값의 차를 구합니다.

구역을 나눌 수 있는 모든 경우에서 최대값과 최소값의 차를 구한 뒤 이 중에서 가장 작은 수를 구하는 문제입니다.

Solution

대각선으로 나누어지기도 하고 좌표값이 복잡해보이긴 하지만 문제에서 주어진 대로 구현만 하면 쉽게 풀리는 문제입니다.

1. 4 중 for 문으로 (x, y, d1, d2) 경우의 수를 전부 구한다.
2. (x, y) 좌표에서 시작하여 d1, d2 를 기준으로 경계선만 체크한다.
3. 경계선을 기준으로 1, 2, 3, 4 구역의 인구수를 구한다.
4. 5 구역은 (전체 인구수 - 나머지 구역의 인구수) 로 계산한다.
5. 각 구역 인구수를 오름차순으로 정렬한 뒤에 최대값에서 최소값을 빼고 min 배열과 비교해서 최소값을 구한다.

각 구역의 인구수를 구하는 순서는 아래 그림처럼 위에서부터 아래로, 화살표 순서대로 값을 더했습니다.

미리 표시해둔 경계선을 만나면 다음 줄로 넘어가는 방식으로 구현하여 5 구역을 전부 알아낼 필요 없이 경계선만 체크했습니다.

Java Code

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

class Main {
    static int N;
    static int[][] arr;
    static int totalPeople = 0;
    static int min = Integer.MAX_VALUE;

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

        // input
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        
        arr = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                totalPeople += arr[i][j];
            }
        }

        // solution
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                for (int d1 = 1; d1 < N; d1++) {
                    for (int d2 = 1; d2 < N; d2++) {
                        if (x + d1 + d2 >= N) continue;
                        if (y - d1 < 0 || y + d2 >= N) continue;

                        solution(x, y, d1, d2);
                    }
                }
            }
        }

        System.out.println(min);
    }

    static void solution(int x, int y, int d1, int d2) {
        boolean[][] border = new boolean[N][N];

        // 경계선 세팅
        for (int i = 0; i <= d1; i++) {
            border[x + i][y - i] = true;
            border[x + d2 + i][y + d2 - i] = true;
        }

        for (int i = 0; i <= d2; i++) {
            border[x + i][y + i] = true;
            border[x + d1 + i][y - d1 + i] = true;
        }

        int[] peopleSum = new int[5];

        // 1 구역 인구수
        for (int i = 0; i < x + d1; i++) {
            for (int j = 0; j <= y; j++) {
                if (border[i][j]) break;
                peopleSum[0] += arr[i][j];
            }
        }

        // 2 구역 인구수
        for (int i = 0; i <= x + d2; i++) {
            for (int j = N - 1; j > y; j--) {
                if (border[i][j]) break;
                peopleSum[1] += arr[i][j];
            }
        }

        // 3 구역 인구수
        for (int i = x + d1; i < N; i++) {
            for (int j = 0; j < y - d1 + d2; j++) {
                if (border[i][j]) break;
                peopleSum[2] += arr[i][j];
            }
        }

        // 4 구역 인구수
        for (int i = x + d2 + 1; i < N; i++) {
            for (int j = N - 1; j >= y - d1 + d2; j--) {
                if (border[i][j]) break;
                peopleSum[3] += arr[i][j];
            }
        }

        // 5 구역 인구수
        peopleSum[4] = totalPeople;

        for (int i = 0; i < 4; i++) {
            peopleSum[4] -= peopleSum[i];
        }

        // 정렬
        Arrays.sort(peopleSum);

        // 최대 - 최소
        min = Math.min(min, peopleSum[4] - peopleSum[0]);
    }
}

Problem

• 문제 링크

연구소에는 벽과 비활성화된 바이러스가 있습니다.

10 개 이하의 비활성화 바이러스 중 M 개를 선택해서 활성화 시키려고 합니다.

활성화된 바이러스는 1 초에 인접한 상하좌우로 이동할 수 있으며 벽은 지나갈 수 없습니다.

M 개를 활성화시키는 모든 경우 중에서 바이러스가 연구소에 전부 퍼지는 최단시간을 구하는 문제입니다.

Solution

활성화된 바이러스를 택하는 모든 경우의 수는 백트래킹으로 구합니다.

Input 을 받을 때 바이러스들의 모든 리스트를 List<Virus> viruses 에 받아서 저장해둡니다.

재귀를 통해서 활성화 시킬 바이러스 리스트인 Virus[] active 를 구하고 나면 바이러스틀 퍼트립니다.

바이러스 퍼트리기는 BFS 로 진행하면 됩니다.

BFS 를 진행하면서 방문 체크가 필요한대, 기존 2차원 배열은 계속해서 사용해야되기 때문에 다른 배열을 복사하거나 생성해서 사용해야 합니다.

boolean[][] infected 배열을 통해 확산 여부를 체크하고 기존 배열로는 벽을 체크하면서 진행합니다.

처음 입력을 받을 때 미리 구해둔 emptySpace 를 사용해서 빈 공간의 갯수가 0 이 되는 순간의 시간초를 구하고 그 중 가장 작은 숫자를 구하면 됩니다.

주의할 점

1. 활성화된 바이러스가 퍼질 때 비활성화된 바이러스도 지나갈 수 있다.

2. 벽에 막혀서 바이러스가 존재하지 못하는 경우라고 반드시 -1 은 아니다. 다른 바이러스를 활성화 하면 성공할 수도 있다. 모든 바이러스의 경우를 만들었을때 전부 실패해야 -1 이다.

3. 바이러스를 퍼트릴 맵은 따로 복사해서 사용하는게 좋다.

4. 비활성화된 바이러스는 지나갈 수 있지만 도착하는 순간에 시간을 갱신하면 안된다. 비활성화된 바이러스들 때문에 바이러스가 전부 퍼졌는지 확인하는 건 빈 공간의 갯수로 파악하는 것이 훨씬 효과적이다.

Java Code

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

class Main {
    static class Virus {
        int x, y, time;

        Virus(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }

    static int N, M;
    static int[][] arr;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static List<Virus> viruses = new ArrayList<>();
    static Virus[] active;
    static int resultMinTime = Integer.MAX_VALUE;
    static int originEmptySpace = 0;

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

        // input
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        arr = new int[N][N];
        active = new Virus[M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());

                if (arr[i][j] == 0) {
                    originEmptySpace++;
                } else if (arr[i][j] == 2) {
                    viruses.add(new Virus(i, j, 0));
                }
            }
        }

        // solution
        if (originEmptySpace == 0) {
            System.out.println(0);
        } else {
            selectVirus(0, 0);
            System.out.println(resultMinTime == Integer.MAX_VALUE ? -1 : resultMinTime);
        }
    }

    // 백트래킹으로 M 개의 바이러스를 선택하는 Combination 구현
    static void selectVirus(int start, int selectCount) {
        if (selectCount == M) {
            spreadVirus(originEmptySpace);
            return;
        }

        for (int i = start; i < viruses.size(); i++) {
            active[selectCount] = viruses.get(i);
            selectVirus(i + 1, selectCount + 1);
        }
    }

    // BFS 로 바이러스를 퍼트린다
    static void spreadVirus(int emptySpace) {
        Queue<Virus> q = new LinkedList<>();
        boolean[][] infected = new boolean[N][N];

        for (int i = 0; i < M; i++) {
            Virus virus = active[i];
            infected[virus.x][virus.y] = true;
            q.add(virus);
        }

        while (!q.isEmpty()) {
            Virus virus = q.poll();

            for (int i = 0; i < 4; i++) {
                int nx = virus.x + dx[i];
                int ny = virus.y + dy[i];

                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if (infected[nx][ny] || arr[nx][ny] == 1) continue;

                if (arr[nx][ny] == 0) {
                    emptySpace--;
                }

                if (emptySpace == 0) {
                    resultMinTime = Math.min(resultMinTime, virus.time + 1);
                    return;
                }

                infected[nx][ny] = true;
                q.add(new Virus(nx, ny, virus.time + 1));
            }
        }
    }
}

Problem

• 문제 링크

문제에서 설명해주는 R 연산과 C 연산을 반복한 뒤 특정 좌표의 숫자가 k 와 일치하는 시간은 몇 초 뒤인지 구하는 문제입니다.

Solution

단순하게 구현하면 됩니다.

R 연산과 C 연산의 인덱스 빼고는 거의 동일한데 저는 헷갈릴까봐 그냥 각각 정의했습니다.

인덱스에 대한 처리만 주의하면 되는 문제입니다.

특정 행이나 열에 대한 연산은 다음 순서로 진행했습니다.

1. 숫자들의 갯수를 카운팅해서 Map<number, count> 에 저장합니다.
2. 우선순위를 적용한 Pair 클래스에 넣어서 우선순위 큐에 넣어줍니다.
3. 우선순위 큐에서 순서대로 값들을 꺼내 배열을 다시 갱신해주고 해당되지 않는 배열들은 전부 0 으로 초기화해줍니다.

주의할 점

1. R 연산, C 연산 인덱스 헷갈리지 않기

2. 100 초가 넘어가는 순간이기 때문에 100 초에 성공한 값도 인정

3. 연산할 때 0 의 갯수는 세지 않는 예외처리 필요

4. A 배열에 그대로 새 값을 덮어쓴다면 연산에 해당하지 않는 값은 0 으로 세팅 해줘야한다.

   • 연산을 한다고 길이가 무조건 길어지지는 않다.
   • [1, 1, 1, 1, 1] 을 연산하면 [1, 5] 가 되는데 만약 뒤의 값들을 0 으로 바꾸지 않으면 [1, 5, 1, 1, 1] 로 남는다.

Java Code

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

class Main {
    static class Pair implements Comparable<Pair> {
        int number;
        int count;

        Pair(int n, int c) {
            this.number = n;
            this.count = c;
        }

        // count 가 작은 게 앞으로, 같으면 number 가 작은게 앞으로
        public int compareTo(Pair o) {
            if (this.count > o.count) {
                return 1;
            } else if (this.count == o.count) {
                return this.number - o.number;
            } else {
                return -1;
            }
        }
    }

    static int r, c, k;
    static int[][] A = new int[101][101];
    static int xLength = 3, yLength = 3;

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

        // input
        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= 3; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1 ; j <= 3; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // solution
        System.out.println(solution());
    }

    static int solution() {
        for (int time = 0; time <= 100; time++) {
            if (A[r][c] == k) {
                return time;
            }
            operating();
        }

        return -1;
    }

    // R 연산 : 배열 A의 모든 행에 대해서 정렬을 수행한다
    // C 연산 : 배열 A의 모든 열에 대해서 정렬을 수행한다
    static void operating() {
        if (xLength >= yLength) {
            for (int i = 1; i <= xLength; i++) {
                R(i);
            }
        } else {
            for (int i = 1; i <= yLength; i++) {
                C(i);
            }
        }
    }

    // 각 숫자들의 개수를 구해서 HashMap 에 담았다가 우선순위 큐에 옮겨담아서 정렬
    static void R(int key) {
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        Map<Integer, Integer> map = new HashMap<>(); // <number, count>

        for (int i = 1; i <= yLength; i++) {
            if (A[key][i] == 0) continue;
            map.compute(A[key][i], (num, count) -> count == null ? 1 : count + 1);
        }

        map.forEach((k, v) -> pq.add(new Pair(k, v)));

        int i = 1;
        while (!pq.isEmpty()) {
            Pair p = pq.poll();
            A[key][i++] = p.number;
            A[key][i++] = p.count;
        }

        yLength = Math.max(yLength, i);

        while (i <= 99) {
            A[key][i++] = 0; 
            A[key][i++] = 0; 
        }
    }
    
    // 각 숫자들의 개수를 구해서 HashMap 에 담았다가 우선순위 큐에 옮겨담아서 정렬
    static void C(int key) {
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        Map<Integer, Integer> map = new HashMap<>(); // <number, count>

        for (int i = 1; i <= xLength; i++) {
            if (A[i][key] == 0) continue;
            map.compute(A[i][key], (num, count) -> count == null ? 1 : count + 1);
        }

        map.forEach((k, v) -> pq.add(new Pair(k, v)));

        int i = 1;
        while (!pq.isEmpty()) {
            Pair p = pq.poll();
            A[i++][key] = p.number;
            A[i++][key] = p.count;
        }

        xLength = Math.max(xLength, i);

        while (i <= 99) {
            A[i++][key] = 0; 
            A[i++][key] = 0; 
        }
    }
}

Problem

• 문제 링크

매 초마다 움직이는 물고기들과 물고기를 잡아먹으며 이동하는 상어가 존재할 때

상어가 잡아 먹을 수 있는 물고기 크기의 합을 구하는 문제입니다.

Solution

백트래킹을 이용해서 상어가 이동하는 모든 경우의 수를 구하면 됩니다.

상어는 한 방향밖에 가지 못하기 때문에 4 x 4 배열에서 이동하는 경우의 수는 최대 3 개입니다.

물고기가 먼저 이동해야 하기 때문에 DFS 시작하자마자 물고기를 전부 이동시키고 이동 가능한 경우의 수를 전부 확인하여 다시 DFS 를 들어갑니다.

원래 백트래킹을 할 때는 빠져 나오면서 값들을 원래 값으로 돌려놓아야 하는데

배열이나 물고기 리스트들이 너무 바뀌는게 많기 때문에 다음 DFS 로 넘기는 값들은 전부 복사한 새로운 값으로 했습니다.

그래서 DFS 를 빠져나온 후에도 기존 값들을 갖고 다음 경우의 수를 확인할 수 있습니다.

주의할 점

1. 물고기들은 번호 순서대로 이동해야 합니다. 물고기가 순서대로 주어지지 않기 때문에 정렬이 필요합니다.
2. 상어는 물고기가 있는 공간으로만 이동할 수 있습니다.
3. 물고기는 빈칸 또는 또다른 물고기가 있는 곳으로만 이동할 수 있습니다.
4. 상어나 물고기가 이동한 후에는 이동하기 전의 공간 뒷처리를 잘 해줘야합니다.

Java Code

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

class Main {
    static class Shark {
        int x, y, dir, eatSum;

        Shark() { }

        Shark(int x, int y, int dir, int eatSum) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.eatSum = eatSum;
        }
    }

    static class Fish {
        int x, y, id, dir;
        boolean isAlive = true;

        Fish() { }
        
        Fish(int x, int y, int id, int dir, boolean isAlive) {
            this.x = x;
            this.y = y;
            this.id = id;
            this.dir = dir;
            this.isAlive = isAlive;
        }
    }
    
    // 0 부터 7 까지 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};
    static int maxSum = 0;

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

        int[][] arr = new int[4][4];
        List<Fish> fishes = new ArrayList<>();

        // input
        for (int i = 0; i < 4; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < 4; j++) {
                Fish f = new Fish();
                f.id = Integer.parseInt(st.nextToken());
                f.dir = Integer.parseInt(st.nextToken()) - 1;
                f.x = i;
                f.y = j;
                
                fishes.add(f);
                arr[i][j] = f.id;
            }
        }

        // 물고기는 작은 순서부터 이동해야 하기 때문에 미리 정렬해둠
        Collections.sort(fishes, new Comparator<Fish>() {
            @Override
            public int compare(Fish o1, Fish o2) {
                return o1.id - o2.id;
            }
        });

        // 상어는 (0, 0) 물고기를 먹고 시작하며 위치는 -1 로 표현
        Fish f = fishes.get(arr[0][0] - 1);
        Shark shark = new Shark(0, 0, f.dir, f.id);
        f.isAlive = false;
        arr[0][0] = -1;
        
        // solution
        dfs(arr, shark, fishes);
        System.out.println(maxSum);
    }

    // 재귀로 상어가 이동할 수 없을 때까지 반복한다.
    static void dfs(int[][] arr, Shark shark, List<Fish> fishes) {
        // 잡아먹은 양의 최대값 구하기
        if (maxSum < shark.eatSum) {
            maxSum = shark.eatSum;
        }

        // 모든 물고기 순서대로 이동
        fishes.forEach(e -> moveFish(e, arr, fishes));
        
        for (int dist = 1; dist < 4; dist++) {
            int nx = shark.x + dx[shark.dir] * dist;
            int ny = shark.y + dy[shark.dir] * dist;
    
            if (0 <= nx && nx < 4 && 0 <= ny && ny < 4 && arr[nx][ny] > 0) {
                // 물고기 잡아먹고 dfs
                int[][] arrCopies = copyArr(arr);
                List<Fish> fishCopies = copyFishes(fishes);
                
                arrCopies[shark.x][shark.y] = 0;
                Fish f = fishCopies.get(arr[nx][ny] - 1);
                Shark newShark = new Shark(f.x, f.y, f.dir, shark.eatSum + f.id);
                f.isAlive = false;
                arrCopies[f.x][f.y] = -1;
                
                dfs(arrCopies, newShark, fishCopies);
            }
        }
    }
    
    // 이동가능한 칸은 빈칸, 다른 물고기가 있는 칸
    // 45도 반시계 방향으로 회전하면서 스캔
    static void moveFish(Fish fish, int[][] arr, List<Fish> fishes) {
        if (fish.isAlive == false) return;

        for (int i = 0; i < 8; i++) {
            int nextDir = (fish.dir + i) % 8;
            int nx = fish.x + dx[nextDir];
            int ny = fish.y + dy[nextDir];

            if (0 <= nx && nx < 4 && 0 <= ny && ny < 4 && arr[nx][ny] > -1) {
                arr[fish.x][fish.y] = 0;
                
                if (arr[nx][ny] == 0) {
                    fish.x = nx;
                    fish.y = ny;
                } else {
                    Fish temp = fishes.get(arr[nx][ny] - 1);
                    temp.x = fish.x;
                    temp.y = fish.y;
                    arr[fish.x][fish.y] = temp.id;

                    fish.x = nx;
                    fish.y = ny;
                }

                arr[nx][ny] = fish.id;
                fish.dir = nextDir;
                return;
            }
        }
    }

    static int[][] copyArr(int[][] arr) {
        int[][] temp = new int[4][4];

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                temp[i][j] = arr[i][j];
            }
        }

        return temp;
    }

    static List<Fish> copyFishes(List<Fish> fishes) {
        List<Fish> temp = new ArrayList<>();
        fishes.forEach(e -> temp.add(new Fish(e.x, e.y, e.id, e.dir, e.isAlive)));
        return temp;
    }
}

Problem

• 문제 링크

낚시왕이 왼쪽에서 오른쪽 끝으로 이동하는 동안 잡은 상어 크기의 합을 구하는 문제입니다.

상어는 속력과 방향, 크기를 갖고 있으며 매 초마다 바라보는 방향으로 속력만큼 칸을 이동합니다.

만약 상어가 범위 밖으로 벗어나려고 하면 방향을 바꿔서 이동합니다.

Solution

문제에서 주어진 대로 구현하면 됩니다.

Shark 클래스를 선언해서 상어의 크기, 속력, 방향을 정의했고 좌표에 맞춰서 2차원 배열인 sharks 에 저장했습니다.

이 문제는 상어를 움직이는게 핵심입니다.

처음에는 계산하기 귀찮아서 단순하게 반복했더니.. Java 8 에서는 통과하는데 Java 11 이나 OpenJDK 환경에서는 시간초과가 발생했습니다.

따라서 어느정도 이동거리에 대한 최적화가 필요합니다.

몇 개의 예시를 만들어서 테스트 해보면 알 수 있지만 상어가 어디 위치에 있던, 일정한 거리를 이동하면 다시 원래 위치와 방향으로 돌아옵니다.

공식은 상어가 위아래로 움직일 땐 (R - 1) * 2 이고 좌우로 움직일 땐 (C - 1) * 2 입니다.

예를 들어 상어의 속력이 9 이고 위아래로 움직이며 R == 4 인 맵에 있다고 가정합니다.

상어는 어느 좌표에 있어도 6 만큼 이동하면 다시 원래 자리와 방향(중요)으로 돌아옵니다.

그렇기 때문에 9 % 6 인 3 만큼만 이동하면 상어의 최종 도착지가 됩니다.

최종 연산까지 구하기엔 아무래도 상어의 방향까지 구하기가 귀찮아서.. 나머지 연산 이후에는 직접 반복문으로 이동했습니다.

주의할 점

1. 상어는 맨 끝에 있으면서 바깥 방향을 바라본 채로 시작할 수 있습니다.
2. 상어 경쟁을 실시간으로 처리하면 이동하기 전 상어와 경쟁할 수 있기 때문에 경쟁은 모든 이동이 끝난 후에 해야 합니다.

Java Code

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

class Main {

    static class Shark {
        int speed, direction, size;
    }

    static int R, C, M;
    static int answerSumOfSize = 0;
    static Shark[][] sharks;

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

        // 격자판의 크기 R, C, 상어의 수 M
        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        sharks = new Shark[R][C];

        // M 개의 줄에 상어의 정보
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            Shark shark = new Shark();
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            shark.speed = Integer.parseInt(st.nextToken());
            shark.direction = Integer.parseInt(st.nextToken());
            shark.size = Integer.parseInt(st.nextToken());
            sharks[r - 1][c - 1] = shark;
        }

        solution();
        System.out.println(answerSumOfSize);
    }

    // 낚시왕이 오른쪽으로 한칸 이동하는건 반복문의 index 로 표현
    // 현재 상어의 위치 중 제일 가까운 상어를 잡고 상어 이동 반복
    private static void solution() {
        for (int i = 0; i < C; i++) {
            fishing(i);
            moveAllSharks();
        }
    }

    // 현재 위치에서 가장 가까이에 있는 상어를 잡는다.
    private static void fishing(int col) {
        for (int i = 0; i < R; i++) {
            if (sharks[i][col] != null) {
                answerSumOfSize += sharks[i][col].size;
                sharks[i][col] = null;
                return;
            }
        }
    }

    private static void moveAllSharks() {
        Shark[][] nextSharks = new Shark[R][C];

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                moveShark(nextSharks, i, j);
            }
        }

        // 이동 완료한 배열로 덮어 씌우기
        for (int i = 0; i < R; i++) {
            sharks[i] = Arrays.copyOf(nextSharks[i], C);
        }
    }

    private static void moveShark(Shark[][] nextSharks, int i, int j) {
        Shark shark = sharks[i][j];

        if (shark == null) {
            return;
        }

        // direction 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽
        // 위아래는 R, 좌우는 C 가 X 라고 할 때 (X - 1) * 2 만큼 이동하면 동일한 위치, 방향으로 돌아온다.
        // 그러므로 상어의 속도에서 (X - 1) * 2 을 나눈 나머지만큼만 이동하면 된다.
        // 총 이동해야 할 거리 = shark.speed % ((X - 1) * 2)
        int X = shark.direction < 3 ? R : C;
        int moveDistance = shark.speed % ((X - 1) * 2);
        int row = i;
        int col = j;

        // 움직이는 거리를 구한 후에는 직접 이동시킴
        // (최종 위치를 구했을 때 방향까지 계산하기 귀찮아서.. 직접 이동)
        for (int k = 0; k < moveDistance; k++) {
            if (shark.direction == 1) {
                row--;
                if (row < 0) {
                    shark.direction = 2;
                    row = 1;
                }
            } else if (shark.direction == 2) {
                row++;
                if (row > R - 1) {
                    shark.direction = 1;
                    row = R - 2;
                }
            } else if (shark.direction == 3) {
                col++;
                if (col > C - 1) {
                    shark.direction = 4;
                    col = C - 2;
                }
            } else {
                col--;
                if (col < 0) {
                    shark.direction = 3;
                    col = 1;
                }
            }
        }

        // 만약 이미 상어가 있으면 크기를 비교해서 사이즈 큰 놈을 남긴다
        if (nextSharks[row][col] != null && nextSharks[row][col].size > shark.size) {
            return;
        }

        nextSharks[row][col] = shark;
    }
}