<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

Rest API는 API 작동 방식에 대한 조건을 부과하는 소프트웨어 아키텍처이다.

좀더 간단하게 말하자면 서버의 api가 적절하게 http를 준수하며 잘 설계되었다면 RESTful하게 설계되어 있다고 생각하면 된다.

고유 리소스 식별자

서버는 고유한 리소스 식별자로 각 리소스를 식별한다. REST 서비스의 경우 서버는 일반적으로 URL을 사용하여 리소스 식별을 수행한다. URL은 리소스에 대한 경로를 지정한다. URL은 웹페이지를 방문하기 위해 브라우저에 입력하는 웹 사이트 주소와 유사하다. URL은 요청 엔드포인트라고도 하며 클라이언트가 요구하는 사항을 서버에 명확하게 지정한다.

메서드

HTTP 베서드는 리소스에 수행해야 하는 작업을 서버에 알려준다.

GET

클라이언트는 GET을 사용하여 서버의 지정된 URL에 있는 리소스에 엑세스한다. GET 요청을 캐싱하고 RESTful API 요청에 파라미터를 넣어 전송하여 전송 전에 데이터를 필터링하도록 서버에 지시할 수 있다.

POST

클라이언트는 POST를 사용하여 서버에 데이터를 전송한다. 여기에는 요청과 함께 데이터 표현이 포함된다. 동일한 POST 요청을 여러 번 전송하면 동일한 리소스를 여러 번 생성하는 부작용이 있다.

PUT

클라이언트는 PUT을 사용하여 서버의 기존 리소스를 업데이트한다. POST와 달리 RESTful 웹 서비스에서 동일한 PUT요청을 여러 번 전송해도 결과는 동일하다.

예를들어 API의 리소스 식별자를 중복 없이 고유하게 잘 만들고 해당 API에 적절하게 HTTP 메서드를 사용했다면 RESTful 하게 설계했다고 볼 수 있다.

[문제 링크]

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을 기준으로 신기한 소수를 찾는다. 소수 판별함수는 숫자가 어떤 특정한 수로 나눠떨어지면 소수가 아닌 성질을 활용한다.