뒤집어진 사과집

접근

전형적인 BFS 문제였다. 가로 세로의 길이가 50 이하로, 모든 경우를 탐색한다 해도 2500번만 보면 된다. 모든 칸을 탐색하며 육지일 경우 bfs로 가장 긴 거리를 리턴하고, 그 중 가장 큰 수를 출력하면 된다.

개인적으로 하나로 연결된 육지를 계속해서 확인해봐야 한다는 점이 비효율적으로 느껴져 개선 방안을 찾아보고자 했지만.. 다른 사람들의 풀이를 참고해봐도 실행 시간이 비슷한 것으로 보아 특별한 해결책은 찾지 못했다. 

코드

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

class Main {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static char[][] map;

    public static class Pos{
        int x;
        int y;
        int dist = 0;

        Pos(int x, int y, int d){
            this.x = x;
            this.y = y;
            this.dist = d;
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 입력값 저장
        int h = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());
        map = new char[h][w];

        for(int i = 0; i < h;i++)
            map[i] = br.readLine().toCharArray();

        // 최단거리 계산
        int answer = solve(w, h);
        System.out.println(answer);
    }

    public static int solve(int w, int h){
        int res = 0;

        for(int i = 0;i < h;i++){
            for(int j = 0;j < w;j++){
                if(map[i][j] =='W') continue;
                int curMax = bfs(i, j, w, h);
                res = Math.max(res, curMax);
            }
        }
        
        return res;
    }

    public static int bfs(int x, int y, int w, int h){
        int maxDist = 0;
        
        boolean[][] visit = new boolean[h][w];
        for(int i = 0;i < h;i++)
            Arrays.fill(visit[i], false);

        Queue<Pos> q = new LinkedList();
        q.add(new Pos(x, y, 0));
        visit[x][y] = true;
        
        while(!q.isEmpty()){
            Pos cur = q.poll();
            maxDist = Math.max(maxDist, cur.dist);

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

                // 범위를 벗어남
                if(!inBound(nx, ny, w, h)) continue;
                // 바다이거나 이미 방문함
                if(map[nx][ny] == 'W' || visit[nx][ny]) continue;

                q.add(new Pos(nx, ny, cur.dist+1));
                visit[nx][ny] = true;
            }
        }

        return maxDist;
    }

    public static boolean inBound(int x, int y, int w, int h){
        return !(x < 0 || x >= h || y < 0 || y >= w);
    }
}

접근

어렵진 않은데, 생각보다 푸는 데 되게 오래 걸렸던 문제다. 구현 문제는 알고리즘에 조금 소홀해지면 바로 표가 나는 것 같다. 

1. 우선 처음에는 'R' 명령어가 나올 때마다 배열을 reverse하는 단순한 방식으로 작성했고, 시간초과가 났다.

2. 그래서 R이 나올 때마다 flag값을 반전시켜 앞/뒤쪽 중 어디에서 아이템을 삭제할지 정하는 방식으로 수정했다. 

3. 이번엔 시간 초과는 안났는데, 틀렸다. 질문 게시판의 반례를 모두 입력해보아도 틀린 경우가 없었는데.. 

4. 이유가 다소 어이없었다ㅠ 내가 작성한 코드의 ArrayList.toString() 함수는 "[1, 2, 3]"과 같이 각 값 사이에 공백이 추가되어 나오는데, 문제의 테스트 케이스는 "[1,2,3]"과 같이 공백이 없는 값을 요구하고 있었다.. 그래서 replaceAll로 공백을 모두 없애주니 통과했다. 

다른 사람들의 코드와 비교해봤을 때 실행 시간이 다소 느린 것 같아서 그 이유를 고민해봤다. 로직은 동일한데, 자료구조의 문제였던 것 같다. 내가 사용한 ArrayList는, 만약 첫 번째 아이템을 remove한다면 뒤쪽의 아이템들을 모두 앞당기는 과정이 필요하다고 한다.(by gpt) 그런데 676ms가 나온 해당 코드를 보면 Deque를 사용하고 있다. 디큐도 잘 알고 있는 자료구조였지만, 알고리즘 문제를 풀며 자주 접하게 되지는 않다보니 이를 사용할 생각을 못한 것 같다. 

코드

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int tc = Integer.parseInt(br.readLine());
        for(int t = 0;t < tc;t++){
            // 입력값 저장
            char[] p = br.readLine().toCharArray();
            int n = Integer.parseInt(br.readLine());
            String[] numStrArr = br.readLine().split(",|\\[|\\]");  // 양 끝에는 빈 리스트가 올 것
            
            // 숫자 배열 전처리
            ArrayList<Integer> numArr = new ArrayList();

            for(int i = 0;i < n;i++)
                numArr.add(Integer.parseInt(numStrArr[i+1]));

            String res = solve(p, numArr);
            sb.append(res).append("\n");
        }
        
        System.out.println(sb.toString());
    }

    public static String solve(char[] commandArr, ArrayList<Integer> numArr){
        // 첫 번째 코드(시간 초과)
        /**
        int commandCnt = commandArr.length;
        for(int i = 0;i < commandCnt;i++){
            char c = commandArr[i];
            if(c == 'R'){
                Collections.reverse(numArr);
            }
            else {  // c == 'D'
                if(numArr.size() == 0)
                    return "error";
                else
                    numArr.remove(0);
            }
        }

        return numArr.toString();
        **/

        int commandCnt = commandArr.length;
        boolean reverseFlag = false;
        
        for(int i = 0;i < commandCnt;i++){
            char c = commandArr[i];
            if(c == 'R'){
                reverseFlag = !reverseFlag;
            }
            else {  // c == 'D'
                if(numArr.size() == 0)
                    return "error";
                else{
                    if(reverseFlag)
                        numArr.remove(numArr.size()-1);
                    else
                        numArr.remove(0);
                }
            }
        }

        if(reverseFlag)
            Collections.reverse(numArr);

        return numArr.toString().replaceAll(" ", "");
    }
}

접근

접근 자체는 어렵지 않은 문제였던 것 같다. 크레인과 박스의 무게를 내림차순으로 정렬하여, 무거운 것부터 크레인에 하나씩 할당해주면 된다. 그럼 이제 그걸 어떻게 구현하느냐의 문제이다. 해당 짐을 실었는지 여부를 확인하는 방법은 다양하게 있겠지만, 결국 원본 리스트에서 remove를 하는 것이 제일 간편한 방식이다. 그래서 일반 일차원 배열보다는 ArrayList에 저장하여 remove 함수를 쓰기로 했다. 다만 remove 사용 시 주의할 점은, 전체 리스트의 길이가 동적으로 변하기 때문에 반복문을 돌 때 인덱스를 넘어가지 않도록 조심해야 한다.

코드

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

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

        // 입력값 저장
        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        ArrayList<Integer> crains = new ArrayList();
        
        for(int i = 0;i < n;i++)
            crains.add(Integer.parseInt(st.nextToken()));

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        ArrayList<Integer> boxes = new ArrayList();
        
        for(int i = 0;i < m;i++)
            boxes.add(Integer.parseInt(st.nextToken()));

        // 내림차순 정렬
        Collections.sort(crains, Collections.reverseOrder());
        Collections.sort(boxes, Collections.reverseOrder());

        int answer = solve(crains, boxes);
        System.out.println(answer);
    }

    static int solve(ArrayList<Integer> crains, ArrayList<Integer> boxes){
        int result = 0;

        // 불가능한 경우
        if(boxes.get(0) > crains.get(0)){
            result = -1;
            return result;
        }

        // 그리디 계산
        while(!boxes.isEmpty()){
            int boxIdx = 0;
            int crainIdx = 0;
            int crainSize = crains.size();

            while(crainIdx < crainSize){
                if(boxIdx >= boxes.size())
                    break;

                if(crains.get(crainIdx) >= boxes.get(boxIdx)){
                    boxes.remove(boxIdx);
                    crainIdx++;
                }
                else boxIdx++;
            }
            result++;            
        }
        
        return result;
    }
}

접근

바로 이전 게시글에서 풀었던 경로 찾기 문제와 매우 유사하다. 여행 동선을 체크할 때 중간에 여러 도시를 지나가도 되고 동일한 도시를 여러 번 방문해도 된다는 얘기는, 결국 A > B 도시로 이동 가능한 경로가 있는가만 확인하면 된다. 어차피 양방향 그래프이기 때문에 나는 스택에 저장해두고 뒤쪽 도시부터 반대 방향으로 확인했다. 

처음에 75%에서 틀렸다는 결과가 나왔는데, 질문 게시판에서 반례를 찾았다. 여행 계획이 A > A, 즉 같은 도시로 이동할 수도 있는거다. 문제에서 연결 정보를 입력받을 때에는 같은 도시에 대한 정보는 포함되어 있지 않으므로 이 부분이 누락됐던 것 같다. 그래서 if(i == j) graph[i][j] = 1 조건을 추가해주었다. 

코드

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

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

        // 입력값 저장
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int[][] graph = new int[n+1][n+1];
        
        for(int i = 1;i <= n;i++){
            st = new StringTokenizer(br.readLine());
            
            for(int j = 1;j <= n;j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
                if(i == j) graph[i][j] = 1;
            }
        }

        // 여행 계획
        st = new StringTokenizer(br.readLine());
        Queue<Integer> q = new LinkedList();
        while(st.hasMoreTokens()){
            int cur = Integer.parseInt(st.nextToken());
            q.add(cur);
        }

        // 플로이드 워셜 알고리즘
        solve(graph, n);

        // 결과 출력
        Boolean possible = true;
        int cur = q.poll();
        while(!q.isEmpty()){
            int next = q.poll();
            
            if(graph[cur][next] == 0){
                possible = false;
                break;
            }
            cur = next;
        }

        String answer = possible ? "YES" : "NO";
        System.out.println(answer);
    }

    static void solve(int[][] graph, int n){
        for(int k = 1;k <= n;k++){
            for(int i = 1;i <= n;i++){
                for(int j = 1;j <= n;j++){
                    if(graph[i][k] == 0 || graph[k][j] == 0) continue;  // 양수 길이 없음
                    graph[i][j] = 1;                    
                }
            }
        }
    }
}

접근

1. 우선 그래프 문제이므로, 어떤 형태로 저장할지를 결정해야 한다. 이중 ArrayList로 할지, 아니면 단순 이차원 배열로 할지. 이는 사용하는 알고리즘과 문제에서 주어지는 N의 범위에 따라 다르다. 우선 N의 범위는 100 이하로 매우 작기 때문에 단순 배열로 저장해도 된다. 

2. 그래프 중에서 어떤 알고리즘으로 풀 것인가? 문제를 읽어보면 모든 노드 → 모든 노드로 가는 경로를 찾아야한다. 즉, 플로이드 워셜 알고리즘이 적절하다. 그렇기 때문에 간선 정보는 더더욱 배열로 저장해야 한다는 소리가 된다. 

위와 같이 생각하고 처음에 코드를 짰는데, 테스트 케이스와 결과가 다르게 나왔었다. 알고보니 3중 for문에서 k, i, j 순이 아니라 i, j, k순서로 했었다. 그런 자세한 부분까지 기억하고 있는 것은 아니라서 오히려 잘못된 부분을 찾기가 더 어려웠던 것 같다. 

코드

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

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

        // 입력값 저장
        int n = Integer.parseInt(br.readLine());
        int[][] graph = new int[n][n];
        
        for(int i = 0;i < n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0;j < n;j++)
                graph[i][j] = Integer.parseInt(st.nextToken());
        }

        // 플로이드 워셜 알고리즘
        solve(graph, n);

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                sb.append(graph[i][j]).append(" ");
            }
            sb.append("\n");
        }
        
        System.out.println(sb.toString());
    }

    static void solve(int[][] graph, int n){
        for(int k = 0;k < n;k++){
            for(int i = 0;i < n;i++){
                for(int j = 0;j < n;j++){
                    if(graph[i][k] == 0 || graph[k][j] == 0) continue;  // 양수 길이 없음
                    graph[i][j] = 1;                    
                }
            }
        }
    }
}

접근

처음엔 기존 냅색 알고리즘(평범한 배낭 문제)처럼 이차원 dp 배열을 선언했었다. dp[i][j] = i번째 동전까지 써서 j원을 만들 수 있는 경우의 수로 정의하고. 그런데 문제를 다시 생각해보니, 서로 다른 물건을 담는 것과는 다르게 이 문제에서는 같은 금액의 동전을 여러 번 써도 된다는 점을 깨달았다. 그래서 for(int i = 0;i < m;i += coin) 과 같이 n개의 동전에 대해서 모두 1을 설정한 후 시작해야 하나? 싶었다. 근데 그러면 배열에 0이 너무 많고 비효율적인 것 같아서 접근이 잘못된 것 같았다. 

그래서 사실 솔루션을 살짝 참고했다.. 역시나 이차원이나 쓸 필요가 없었다. 2년 만에 알고리즘을 풀다보니 까먹은 내용이 너무 많았는데, 특히 dp가 감을 다시 되살리기 제일 어려운 것 같다. 앞으로는 일차원 배열을 재사용할 수 있는지 고려해볼 것! 그리고 무엇보다 dp는 직접 표를 그려가며 규칙을 찾는게 제일 쉬운 접근법인 것 같다. 머리로만 풀려고 하지 말자. 

코드

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int tc = Integer.parseInt(br.readLine());
        for(int t = 0;t < tc;t++){
            // 입력값 저장
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] coins = new int[n];
            
            for(int i = 0;i < n;i++){
                int coin = Integer.parseInt(st.nextToken());
                coins[i] = coin;
            }

            int m = Integer.parseInt(br.readLine());

            // 냅색 알고리즘 계산
            int answer = solve(coins, n, m);
            sb.append(answer).append("\n");
        }

        // 결과값 출력
        System.out.println(sb.toString());
    }

    static int solve(int[] coins, int n, int m){
        int result = 0;
        int[] dp = new int[m+1];

        for(int i = 1;i <= n;i++){
            int curCoin = coins[i-1];
            
            for(int j = 0;j <= m;j++){
                if(j == curCoin) dp[j] += 1;
                else if(curCoin < j) dp[j] += dp[j-curCoin];
            }
        }
        result = dp[m];
        return result;
    }
}

접근

우선 이 블로그에서 냅색 알고리즘을 공부한 뒤 문제를 풀었다. 자꾸 내 머리로 생각을 안하고 블로그에서 본 점화식을 은연중에 따라하려고 해서 자꾸 답은 안나오는데 이유는 모르겠고 더 헤맸던 것 같다. 아예 작성하던 코드를 버리고 처음부터 내 방식대로(나는 물건 인덱스가 첫 번째 차원에 오는게 더 이해하기 쉬운 것 같다) 풀었더니 금방 성공했다. 

여기서 주의할 점은, (현재 수납 가능한 무게) - (넣고자 하는 물건의 무게)가 음수가 될 때의 처리인 것 같다. 나는 처음에 continue만 했기 때문에 최종 결과값이 0이 나오기도 했었다. dp 배열값은 항상 갱신해줘야 함에 유의하자. 

코드

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

class Main {
    static int n, k;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 입력값 저장
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        int[] weights = new int[n];
        int[] values = new int[n];
        
        for(int i = 0;i < n;i++){
            st = new StringTokenizer(br.readLine());
            weights[i] = Integer.parseInt(st.nextToken());
            values[i] = Integer.parseInt(st.nextToken());
        }

        // 냅색 알고리즘
        int answer = solve(weights, values);
        
        // 결과 출력
        System.out.println(answer); 
    }

    static int solve(int[] weights, int[] values){
        int result = 0;
        int[][] dp = new int[n+1][k+1];  // dp[i][j] = i번째 물건까지 넣었을 때, j 무게까지의 최대 가치

        for(int i = 1;i <= n;i++){
            int weight = weights[i-1];
            int value = values[i-1];
            
            for(int j = 1;j <= k;j++){
                if(j < weight) {
                    dp[i][j] = dp[i-1][j];
                    continue;
                }
                
                int curMaxVal = Math.max(dp[i-1][j], dp[i-1][j-weight] + value);
                dp[i][j] = curMaxVal;
                result = Math.max(result, curMaxVal);
            }
        }

        return result;
    }
}

접근

처음에 접근을 잘못해서 시간을 많이 써버렸는데, 다른 솔루션을 통해 과제 마감일이 늦은 기준으로 정렬하면 더 편하다는 점을 참고했다. 풀이 방법을 설명하기에 앞서, 나는 두 개의 우선순위 큐를 사용했지만 다른 분들의 솔루션을 참고해보면 N 크기를 가지는 일차원 배열을 선언하여 과제별로 각각의 값을 비교해준 것 같다. 아마 O(N^2)의 시간복잡도가 나올 것 같은데, N의 최댓값이 작기 때문에 후자의 방식이 실행 시간이 더 빠른 것 같다. 그 중 92ms의 속도가 나온 결과가 있어 눈에 띄었다.

우선 과제 정보를 저장하기 위해 Task라는 클래스를 선언했고, 과제 마감일을 기준으로 정렬하며 우선순위 큐에 저장했다. 이후 날짜를 하루씩 줄여가며 큐에 저장된 데이터의 마감일과 비교하며, 해당 날짜에 수행 가능한 과제들 중 점수가 가장 높은 것을 수행한다. 이때 나는 점수가 큰 순서대로 정렬하는 우선순위큐를 하나 더 선언하여, 현재 작업 가능한 과제들을 또 넣어주었다. 

이렇게 풀기 위해서는 Task라는 동일한 클래스에 대해 두 가지 방식으로 정렬해야 했는데, 기존에 사용하던 compareTo 함수를 오버라이딩하는 방식으로는 불가능했다. 이를 위해서 처음으로 람다식을 사용해봤다.

마지막으로 도움받았던 질문 게시판의 반례 링크를 함께 첨부한다. 

코드

package week10;

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

public class BJ13904 {
    static class Task{
        int dDay, score;

        public Task(int dDay, int score) {
            this.dDay = dDay;
            this.score = score;
        }
    }

    static int MAX_DAY = 1001;

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

        int n = Integer.parseInt(br.readLine());
        // 마감 일자가 늦은 순서대로 정렬
        PriorityQueue<Task> pq = new PriorityQueue<>((o1, o2) -> o2.dDay - o1.dDay);

        // 입력값 저장
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            pq.add(new Task(d, w));
        }

        int answer = 0;
        PriorityQueue<Task> greedy = new PriorityQueue<>((o1, o2) -> o2.score - o1.score);

        for (int today = MAX_DAY; today > 0; today--) {
            // 현재 날짜를 기준으로 수행 가능한 과제를 누적
            if(!pq.isEmpty()){
                while(!pq.isEmpty() && today <= pq.peek().dDay)
                    greedy.add(pq.poll());
            }

            // 수행할 과제가 없음
            if(greedy.isEmpty()) continue;

            // 점수가 가장 높은 과제를 수행
            Task task = greedy.poll();
            answer += task.score;
        }

        System.out.println(answer);
    }
}