알고리즘 문제풀이 3-3

문제 1 / 격차

목표 : N명의 중 가장 큰 점수와 가장 작은 점수의 차이 구하기

해결방법 : max값과 min값을 찾아 구해줬다.

class Solution {
    public int solution(int N, int[] scores) {
        int answer = 0;
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        
        /*  
        	stream 연신으로 max 값과 min 값 구하는 방법
        	int max = Arrays.stream(scores).max().getAsInt();
        	int min = Arrays.stream(scores).min().getAsInt();
        */

        for(int score : scores) {
            max = Math.max(max, score);
            min = Math.min(min, score);
        }

        answer = max - min;
        return answer;
    }
}

문제 2 / 미용실

목표 : 예약 시간을 비교해 받을 수 있는 최대 예약의 수 구하기

해결방법 : 예약의 끝 시간이 다음 예약의 시작 시간이상일 때 예약의 수를 카운팅해준다고 생각하고 풀었다. 처음엔 시작 시간을 기준으로 정렬 후 끝 시간을 정렬해서 비교해주었다. 맞는 경우도 있지만 틀린 경우가 더 많았다.

그래서 끝 시간을 기준으로 정렬 후 시작 시간을 정렬하니 잘 작동되었다. 끝 시간이 짧은 걸 택해야 더 많은 예약을 받을 수 있기 때문이다.

예를 들어, {{1, 9}, {2, 3}, {3, 4}, {4, 7}, {9, 11}} 이 있다고 하면 시작 시간을 기준으로 구하면 {1, 9} {9, 11} 밖에 받지 못할 것이다. 하지만 끝 시간을 기준으로 받는다면 {2, 3} {3, 4} {4, 7} {9, 11} 을 받을 수 있다. 그렇기 때문에 끝 시간을 기준으로 잡아야 문제가 풀리는 것이었다.

List

import java.util.*;

class Solution {
    static class Reserve implements Comparable<Reserve> {
        int start, end;

        public Reserve(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Reserve o) {
            if(this.end==o.end) return this.start - o.start;
            return this.end - o.end;
        }
    }
    public int solution(int N, int[][] reserved) {
        int answer = 0;

        if(N==1) return 1;

        ArrayList<Reserve> list = new ArrayList<>();

        for(int[] reserve : reserved) {
            list.add(new Reserve(reserve[0], reserve[1]));
        }

        Collections.sort(list);

        int end=0;
        for(Reserve o : list) {
            if(o.start>=end) {
                answer++;
                end = o.end;
            }
        }
        return answer;
    }
}

우선순위 큐

import java.util.*;

class Solution {
    static class Reserve{
        int start, end;

        public Reserve(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    public int solution(int N, int[][] reserved) {
        int answer = 0;

        if(N==1) return 1;

        PriorityQueue<Reserve> pq = new PriorityQueue<>((o1, o2) -> {
            if(o1.end==o2.end) return o1.start - o2.start;
            return o1.end - o2.end;
        });

        for(int[] reserve : reserved) {
            pq.offer(new Reserve(reserve[0], reserve[1]));
        }

        int end=0;
        while(!pq.isEmpty()) {
            Reserve o = pq.poll();
            if(o.start>=end) {
                answer++;
                end = o.end;
            }
        }
        return answer;
    }
}

문제 3 / 벽 피하기

목표 : 벽 피하기
1초 동안 플레이어가 왼쪽, 가만히, 오른쪽으로 움직이고 벽이 한 칸식 내려온다.
이 때 플레이어가 벽에 부딪히면 종료된다. 플레이어의 생존 가능한 최대 시간을 구하기

해결방법 : 해결하지 못하였다(23.1/100)

계속 풀면서 생각을 전환하다 보니 생각보다 어렵지 않은 문제였다..

플레이어는 항상 바닥에 있기 때문에 N-1행에서 플레이어의 x값을 찾아줘 시작한다.
row는 1초마다 줄기 때문에 카운팅 될 때마다 줄어들게 했고 만약 왼쪽위 위 오른쪽위가 모두 벽이면 종료되어야 되기 때문에 최댓값을 가져와서 리턴해줬다.

dfs

import java.util.*;

class Solution {
    int maxCount;
    int N, M;
    int[][] board;
    int[] dx = {-1, 0, 1};
    
    public int solution(int N, int M, int[][] board) {
        this.N = N;
        this.M = M;
        this.board = board;
        maxCount = 0;
        
        int initPos = -1;
        for (int x = 0; x < M; x++) {
            if (board[N - 1][x] == 2) {
                initPos = x;
                break;
            }
        }
        
        dfs(initPos, 0);
        
        return maxCount;
    }

    private void dfs(int curPos, int count) {
        int row = N - count - 1; 
        
        for (int i = 0; i < 3; i++) {
            int nextPos = curPos + dx[i];
            boolean canMove = false;
            
            if (nextPos >= 0 && nextPos < M && board[row][nextPos] != 1) {
                if (row - 1 >= 0 && board[row - 1][nextPos] != 1) {
                    canMove = true;
                }
            }
            
            if (canMove) {
                dfs(nextPos, count + 1);
            } else {
                maxCount = Math.max(maxCount, count);
            }
        }
    }
}

bfs

import java.util.*;

class Solution {
    int maxCount;
    int N, M;
    int[][] board;
    int[] dx = {-1, 0, 1};
    class Position {
        int pos;
        int count;
        public Position(int pos, int count) {
            this.pos = pos;
            this.count = count;
        }
    }
    public int solution(int N, int M, int[][] board) {
        this.N = N;
        this.M = M;
        this.board = board;
        maxCount = 0;
        
        int initPos = -1;
        for (int x = 0; x < M; x++) {
            if (board[N - 1][x] == 2) {
                initPos = x;
                break;
            }
        }
        
        bfs(initPos);
        
        return maxCount;
    }
    
    private void bfs(int startPos) {
        Queue<Position> q = new LinkedList<>();
        q.offer(new Position(startPos, 0));
        
        while (!q.isEmpty()) {
            Position cur = q.poll();
            int curPos = cur.pos;
            int count = cur.count;
            int row = N - count - 1;
            
            for (int i = 0; i < 3; i++) {
                int nextPos = curPos + dx[i];
                boolean canMove = false;
                
                if (nextPos >= 0 && nextPos < M && board[row][nextPos] != 1) {
                    if (row - 1 >= 0 && board[row - 1][nextPos] != 1) {
                        canMove = true;
                    }
                }
                
                if (canMove) {
                    q.offer(new Position(nextPos, count + 1));
                } else {
                    maxCount = Math.max(maxCount, count);
                }
            }
        }
    }
}