<stdio.han>

[문제 링크]

https://www.acmicpc.net/problem/22233

[난이도]

- Silver 2

[알고리즘]

- LinkedHashSet

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 🔹 HashSet 대신 LinkedHashSet 사용 (입력 순서 유지 가능)
        Set<String> keywords = new LinkedHashSet<>();
        for (int i = 0; i < N; i++) {
            keywords.add(br.readLine());
        }

        for (int i = 0; i < M; i++) {
            String[] words = br.readLine().split(",");
            for (String word : words) {
                keywords.remove(word); // ✅ 평균 O(1)로 최적화됨
            }
            bw.write(keywords.size() + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

[풀이]

처음엔 List로 풀었지만 List.remove() 는 for문으로 전체탐색을 한번진행하며 삭제하는 메서드이므로 최악의 경우 O(N*M)가 걸린다. LinkedHashSet은 O(1)이 걸린다.

그렇다면 언제 LinkedHashSet을 쓰면 좋을까?

1. 중복을 허용하지 않아야 할때 -> List는 중복 허용, LinkedHashSet은 중복을 제거함.

2. 입력된 순서를 유지해야 할 때 -> HashSet은 순서를 보장하지 않지만, LinkedHashSet은 순서를 유지.

3. 탐색보다는 삭제 연산이 많을 때 -> ArrayList는 삭제 시 O(N)인데, LinkedHashSet은 O(1)에 가깝다.

하지만 LinkedHashSet을 쓰면 안되는 경우도 있다.

1. 빠른 인덱스 접근이 필요할 때

• ArrayList.get(index)는 O(1)로 빠르지만 LinkedHashSet은 인덱스로 직접 접근할 수 없다.

2. 메모리를 아껴야 할 때

3. 데이터가 중복될 가능성이 없거나, 순서가 중요하지 않을 때

결론 : 언제 LinkedHashSet을 써야 할까?

• 중복을 방지해야 하고, 순서를 유지해야하며, 삭제 연산이 많을 때 -> LinkedHashSet
• 탐색이나 삽입 속도가 중요하고, 중복을 허용해도 된다면 -> ArrayList
• 인덱스로 직접 접근해야 한다면 -> ArrayList

[문제 링크]

https://www.acmicpc.net/problem/14502

[난이도]

- Gold 4

[알고리즘]

- BFS

- 백트래킹

[코드]

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

public class Main {
    static int N, M, result = 0;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 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());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        backTracking(0);
        System.out.println(result);
    }

    static void backTracking(int depth) {
        if (depth == 3) {
            result = Math.max(result, checkSafeArea(bfs()));
            return;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1; // 벽을세움
                    backTracking(depth + 1);
                    map[i][j] = 0; // 벽을 되돌려놓음
                }
            }
        }
    }
    static int[][] bfs() {
        int[][] newMap = new int[N][M];
        for (int i = 0; i < N; i++) {
            System.arraycopy(map[i], 0, newMap[i], 0, M);
        }
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (newMap[i][j] == 2) {
                    queue.add(new int[]{i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                    if (newMap[nx][ny] == 0) {
                        newMap[nx][ny] = 2;
                        queue.add(new int[]{nx, ny});
                    }
                }
            }
        }
        return newMap;
    }
    static int checkSafeArea(int[][] newMap) {
        int safeArea = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (newMap[i][j] == 0) {
                    safeArea++;
                }
            }
        }
        return safeArea;
    }
}

[풀이]

4방탐색을하며 바이러스를 퍼트리는 부분은 일반적인 bfs알고리즘을 활용해 푼다. 더 생각해야할 부분은 벽을 3개 세우는데 반드시 3개를 세워야하기 때문에 백트래킹을 활용해 벽 3개를 세울 수 있는 가능한 모든 경우의 수를 생각해 세운 후 바이러스를 퍼트리고 다 퍼진후 안전한 공간의 개수를 세준다.

[문제 링크]

https://www.acmicpc.net/problem/1931

[난이도]

- Silver 1

[알고리즘]

- 그리디

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] meetings = new int[N][2];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            meetings[i][0] = Integer.parseInt(st.nextToken());
            meetings[i][1] = Integer.parseInt(st.nextToken());
        }

        // 끝나는 시간을 기준으로 정렬, 끝나는 시간이 같으면 시작 시간을 기준으로 정렬
        Arrays.sort(meetings, (a, b) -> {
            if (a[1] == b[1]) {
                return Integer.compare(a[0], b[0]);
            }
            return Integer.compare(a[1], b[1]);
        });

        int count = 0;
        int lastEndTime = 0;

        for (int i = 0; i < N; i++) {
            if (meetings[i][0] >= lastEndTime) {
                lastEndTime = meetings[i][1];
                count++;
            }
        }

        System.out.println(count);
    }
}

[풀이]

정렬을 할 때 끝나는 시간을 기준으로 오름차순 정렬을 해준다.

그 후 현재시간이 0이라고 할 때 해당 배열의 시작 시간이 현재시간보다 크거나 같을 경우 현재시간을 해당 배열의 끝나는시간으로 변경해준다. 변경될 때 마다 count를 늘려준다.

[문제 링크]

https://www.acmicpc.net/problem/1446

[난이도]

- Silver 1

[알고리즘]

- DP

- 다익스트라

[코드]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt(); // 지름길의 개수
        int D = scanner.nextInt(); // 고속도로의 길이

        // graph를 생성하고 초기화
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= D; i++) {
            graph.add(new ArrayList<>()); // 노드의 개수만큼 생성
        }

        // 지름길 정보를 graph에 추가
        for (int i = 0; i < N; i++) {
            int u = scanner.nextInt(); // 시작 노드
            int v = scanner.nextInt(); // 도착 노드
            int w = scanner.nextInt(); // 가중치
            if (v <= D) { // 노드범위 이상일경우 추가하지 않는다.
                graph.get(u).add(new int[]{v, w}); //
            }
        }

        int[] dist = new int[D + 1]; // 가중치를 기록할 배열
        Arrays.fill(dist, Integer.MAX_VALUE); // 초기값은 모두 INF
        dist[0] = 0; // 시작 위치는 0

        // int[] a 중에서 두번째 요소인 a[1]을 기준으로 큐를 정렬, 즉 가중치(비용)을 기준으로 오름차순 정렬
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.add(new int[]{0, 0}); // {현재 위치, 현재 비용}

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int currentPos = current[0];
            int currentCost = current[1];

            // 만약 현재 비용이 기록된 비용보다 크다면, 이미 더 적은 비용으로 도달한 경로가 존재하므로 무시
            if (currentCost > dist[currentPos]) continue;

            // 다음 지점으로 이동 (일반 도로, 현재 위치에서 한 칸 앞으로 이동)
            // 현재위치에서 한 칸 앞으로 이동한 위치가 D(도로의 길이, 간선의 범위)를 넘지않는경우
            // 현재위치에서 한칸 앞으로 이동한 위치까지의 비용이 기존에 기록된 비용보다 작은 경우
            if (currentPos + 1 <= D && currentCost + 1 < dist[currentPos + 1]) {
                dist[currentPos + 1] = currentCost + 1; // 다음 위치까지의 비용 갱신
                pq.add(new int[]{currentPos + 1, currentCost + 1}); // 우선순위 큐에 추가
            }

            // 지름길로 이동 (현재 위치에서 연결된 모든 지름길을 탐색)
            for (int[] edge : graph.get(currentPos)) {
                int nextPos = edge[0]; // 지름길의 도착 위치
                int nextCost = currentCost + edge[1]; // 지름길을 이용한 다음 위치까지의 비용
                // 지름길을 이용한 비용이 더 적다면 비용 갱신
                if (nextCost < dist[nextPos]) {
                    dist[nextPos] = nextCost; // 다음 위치까지의 비용 갱신
                    pq.add(new int[]{nextPos, nextCost}); // 우선순위 큐에 추가
                }
            }
        }

        System.out.println(dist[D]);
    }
}

[풀이]

일반적인 다익스트라 알고리즘과 같다. 하지만 추가된 부분이 있다.

// 지름길로 이동 (현재 위치에서 연결된 모든 지름길을 탐색)
            for (int[] edge : graph.get(currentPos)) {
                int nextPos = edge[0]; // 지름길의 도착 위치
                int nextCost = currentCost + edge[1]; // 지름길을 이용한 다음 위치까지의 비용
                // 지름길을 이용한 비용이 더 적다면 비용 갱신
                if (nextCost < dist[nextPos]) {
                    dist[nextPos] = nextCost; // 다음 위치까지의 비용 갱신
                    pq.add(new int[]{nextPos, nextCost}); // 우선순위 큐에 추가
                }

지름길을 이용한 경우의 가중치를 한번 더 생각해주어야 한다는 것이다.

[문제 링크]

https://www.acmicpc.net/problem/2156

[난이도]

- Silver 1

[알고리즘]

- DP

[코드]

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

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

        int n = Integer.parseInt(br.readLine());
        int[] wine = new int[n+1];
        for (int i = 1; i <= n; i++) {
            wine[i] = Integer.parseInt(br.readLine());
        }

        if (n == 1) {
            System.out.println(wine[1]);
            return;
        }

        // 초기값 설정
        int[] dp = new int[n+1];
        dp[1] = wine[1];
        if (n > 1) {
            dp[2] = wine[1] + wine[2];
        }

        // 점화식 도출
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i]));
        }
        /**
         * dp[i-1]  = i번째 잔을 안마시는경우
         * dp[i-2] + wine[i] = i-1번째잔을 마시지 않고 현재와인을 마시는 경우
         * dp[i-3] + wine[i-1] + wine[i] = i번째 잔과 i-1번째 잔을 마시고, i-2번째 잔을 마시지 않는 경우
         */

        System.out.println(dp[n]);
    }
}

[풀이]

1. DP 배열 정의: dp[i]는 i번째 포도주 잔까지 최대로 마실 수 있는 포도주의 양을 의미합니다.
2. 점화식 수립:
   • dp[i]는 세 가지 경우 중 최댓값이 됩니다:
     1. i번째 잔을 마시지 않는 경우: dp[i-1]
     2. i번째 잔을 마시고, i-1번째 잔을 마시지 않는 경우: dp[i-2] + wine[i]
     3. i번째 잔과 i-1번째 잔을 마시고, i-2번째 잔을 마시지 않는 경우: dp[i-3] + wine[i-1] + wine[i]
3. 초기 조건 설정:
   • dp[0]은 첫 번째 잔을 마시는 경우입니다.
   • dp[1]은 첫 번째와 두 번째 잔을 마시는 경우입니다.
   • dp[2]은 세 번째 잔까지의 최댓값을 고려합니다.

[문제 링크]

https://www.acmicpc.net/problem/2529

[난이도]

- Silver 1

[알고리즘]

- 백트래킹

[코드]

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

public class Main {
    static int k;
    static char[] operators;
    static boolean[] visited = new boolean[10];
    static List<String> results = new ArrayList<>();

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

        // 공백을 없애고 각 글자를 char array로 담는다
        operators = br.readLine().replace(" ", "").toCharArray();

        solve("", 0);

        results.sort(String::compareTo); // results 리스트를 사전순으로 정렬

        System.out.println(results.get(results.size() - 1)); // 최댓값
        System.out.println(results.get(0)); // 최솟값
    }

    /**
     *
     * @param num 현재까지 생성된 숫자
     * @param index 현재 처리중인 숫자자리
     */
    static void solve(String num, int index) {
        if (index == k + 1) {
            results.add(num);
            return;
        }

        for (int i = 0; i <= 9; i++) {
            if (visited[i]) continue; // 이미사용한 숫자라면 통과

            // index가 0일경우에는 비교할 숫자가 하나밖에 없기때문에 다음숫자로 넘어감
            // 혹은 비교한 두 숫자가 주어진 부등호의 조건과 맞다면 계속 진행
            if (index == 0 || check(num.charAt(index - 1) - '0', i, operators[index - 1])) {
                visited[i] = true;
                solve(num + i, index + 1);
                visited[i] = false; // 완전탐색을 위해 복구
            }
        }
    }

    static boolean check(int a, int b, char operator) {
        if (operator == '<') return a < b;
        else return a > b;
    }
}

[풀이]

백트래킹 알고리즘을 활용할 때 넘겨주는 매개변수를 num : 현재까지 생성된 숫자, index 현재 처리중인 숫자 를 넘겨준다.

for문을 돌며 숫자 두개를 입력받은 부등호와 비교해 참일경우에만 다음숫자를 진행한다.

[문제 링크]

https://www.acmicpc.net/problem/2023

[난이도]

- Gold 5

[알고리즘]

- 백트래킹

[코드]

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

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

        // 초기 신기한 소수 시작 자리 설정
        int[] primeStarts = {2, 3, 5, 7};

        // 결과를 저장할 리스트
        List<Integer> results = new ArrayList<>();

        // 신기한 소수 찾기
        for (int start : primeStarts) { // 일의 자리가 2, 3, 5, 7 이여야함
            findAmazingPrimes(N, start, 1, results);
        }

        // 결과 정렬 및 출력
        Collections.sort(results); // 오름차순으로 정렬 후 출력
        for (int num : results) {
            System.out.println(num);
        }
    }

    // 재귀적으로 신기한 소수를 찾는 함수

    /**
     *
     * @param N N자리
     * @param current 현재 숫자
     * @param length 현재 숫자의 길이
     * @param results 현재 숫자의 길이가 N자리가 되면 results 리스트에 추가함
     */
    private static void findAmazingPrimes(int N, int current, int length, List<Integer> results) {
        if (length == N) { // N자리가 될 때까지 반복
            results.add(current);
            return;
        }

        // 다음 자리수로 확장
        for (int i = 1; i <= 9; i++) {
            int next = current * 10 + i;
            if (isPrime(next)) { // 소수면 true
                findAmazingPrimes(N, next, length + 1, results);
            }
        }
    }

    // 소수 판별 함수
    private static boolean isPrime(int num) {
        if (num < 2) return false; // 2보다 작으면 소수가 아님
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false; // num이 i로 나눠떨어지면 소수가 아님
        }
        return true;
    }
}

[풀이]

일의 자리가 소수인것은  2, 3, 5, 7 밖에 없으므로 2, 3, 5, 7을 기준으로 신기한 소수를 찾는다. 소수 판별함수는 숫자가 어떤 특정한 수로 나눠떨어지면 소수가 아닌 성질을 활용한다.

[문제 링크]

https://www.acmicpc.net/problem/13023

[난이도]

- Gold 5

[알고리즘]

- 백트래킹

[코드]

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

public class Main {
    static int N, M;
    static ArrayList<ArrayList<Integer>> adj;
    static boolean[] visited;
    static boolean found = false;

    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());

        adj = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            adj.add(new ArrayList<>()); // 정점의 수만큼 생성
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adj.get(a).add(b); // 양방향 간선
            adj.get(b).add(a); // 양방향 간선
        }

        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            if (!found) { // ABCDE가 존재하면 true 발견하지 못했다면 false
                dfs(i, 0);
            }
        }

        System.out.println(found ? 1 : 0);
    }

    static void dfs(int node, int depth) {
        if (depth == 4) { // depth가 4면 ABCDE가 서로 연결되어있다는 뜻
            found = true;
            return;
        }

        visited[node] = true;

        for (int next : adj.get(node)) {
            if (!visited[next]) { // 중복방문을 방지
                dfs(next, depth + 1);
                if (found) return;
            }
        }

        visited[node] = false; // 완전탐색을위해 다시 false로 변경
    }
}

[풀이]

이중 ArrayList로 인정리스트인 Adjacency list를 선언해준후.

각 정점을 기준으로 dfs를 반복해 depth가 4인경우를 찾아준다.

depth가 4일경우 ABCDE가 친구인 경우이다.

찾았다면 1을 못찾았다면 0을 출력한다.