알고리즘 문제풀이 2-5

문제 1 / CountTruncateLetter

목표 : 중복된 단어 제외한 단어의 수 출력

해결방법 : Set을 이용했다.

public int solution(String s) {
    int answer = 0;
    String[] splitStr = s.split(" ");

    answer = new HashSet<>(List.of(splitStr)).size();
    return answer;
}

문제 2 / DuplicatedNumber

목표 : 두배열의 교집합 구하기

해결방법 : List 이용해서 교집합을 구해줬다.

public int[] solution(int[] arr1, int[] arr2) {
    List<Integer> answer = new ArrayList<>();

    for(int num1 : arr1) {
        for(int num2 : arr2) {
            if(num1==num2) answer.add(num2);
        }
    }
    return answer.stream().mapToInt(n -> n).sorted().toArray();
}

문제 3 / JumpCase

목표 : 목적지까지 k이하의 정수로 도착할 때 직전 사용했던 숫자 연속으로 사용하지 않고 도착하는 경우의 수 구하기

해결방법 : 개인적으로 꽤 어렵게 풀었다. 이렇게 저렇게 시도 많이 하다 동적 프로그래밍과 메모이제이션으로 풀었다. 아직 dp가 익숙하지 않아 완전탐색으로 하는 습관이 생겨버렸다. 여러 유형에서 더 효율적인 알고리즘을 사용할 수 있도록 연습을 많이 해야겠다.

static int[][] memo;
static final int MOD = 1000000007;
public int solution(int n, int k) {
    int answer = 0;
    memo = new int[n+1][k+1];
    for (int[] row : memo) Arrays.fill(row, -1);
    answer = countPaths(n, k, 0, 0);
    return answer;
}
static int countPaths(int n, int k, int current, int lastUsed) {
    if(current==n) return 1;
    if(current > n) return 0;

    if (memo[current][lastUsed] != -1) return memo[current][lastUsed];
    

    int path=0;
    for(int i=1; i<=k; i++) {
        if(i != lastUsed) {
            path = (path+countPaths(n, k, current+i, i))%MOD;
        }
    }

    memo[current][lastUsed]=path;
    return path;
}

문제 4 / ArraySum

목표 : 연속 합이 가장 큰 수열의 합 반환

해결방법 : 누적 합으로 최대 부분 합을 갱신하면서 풀어주었다.

public int solution(int[] A) {
    int answer = Integer.MIN_VALUE;
    int[] prefix = new int[A.length+1];

    for(int i=0; i<A.length; i++) {
        prefix[i+1] = Math.max(prefix[i]+A[i], A[i]);
    }

    for(int i=1; i<prefix.length; i++) {
        answer = Math.max(answer, prefix[i]);
    }
    return answer<0 ? 0 : answer;
}

문제 5 / BusStop

목표 : 아파트 - 버스 정류장까지 거리 구하기

해결방법 : y, x로 버스 정류장들을 지정해서 가장 가까운 거리를 구해줬다.

static class Point {
    int y, x;
    public Point(int y, int x) {
        this.y = y;
        this.x = x;
    } 
}
public int[][] solution(int[][] n) {
    int[][] answer = new int[n.length][n[0].length];
    ArrayList<Point> list = new ArrayList<>();
    for(int i=0; i<n.length; i++) {
        for(int j=0; j<n[i].length; j++) {
            answer[i][j] = Integer.MAX_VALUE;
            if(n[i][j]==0) {
                list.add(new Point(i, j));
                answer[i][j]=0;
            } 
        }
    }
    for(int i=0; i<list.size(); i++) {
        for(int y=0; y<n.length; y++) {
            for(int x=0; x<n[y].length; x++) {
                if(n[y][x]==1) {
                    answer[y][x] = Math.min(answer[y][x], Math.abs(y-list.get(i).y)+Math.abs(x-list.get(i).x));
                }
            }
        }
    }
    return answer;
}

(25/03/16) bfs를 이용해서 다시 풀어봤다.

import java.util.*;

class Solution {
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, 1, 0, -1};
    public int[][] solution(int[][] n) {
        int[][] answer = new int[n.length][n[0].length];
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < n.length; i++) {
            Arrays.fill(answer[i], Integer.MAX_VALUE);
            for(int j=0; j< n[i].length; j++) {
                if(n[i][j]==0) {
                    answer[i][j] = 0;
                    queue.add(new int[]{i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int y = current[0], x = current[1];

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

                if (ny >= 0 && ny < n.length && nx >= 0 && nx < n[0].length) {
                    if (answer[ny][nx] > answer[y][x] + 1) {
                        answer[ny][nx] = answer[y][x] + 1;
                        queue.add(new int[]{ny, nx});
                    }
                }
            }
        }
        return answer;
    }
}