문제 링크 : https://www.acmicpc.net/problem/2252

위상 정렬 문제입니다.

위상 정렬에 대한 포스팅 https://bcp0109.tistory.com/21

노드 갯수 N, 간선 갯수 M 을 받은 다음에 간선의 가중치를 입력받아서 위상 정렬하면 간단하게 해결됩니다.

result 큐를 사용해서 결과값을 저장했지만 q 에 대한 while 문이 도는 동안 그대로 출력해도 상관없습니다.

문제 링크 : https://www.acmicpc.net/problem/1182

부분집합을 이용하는 문제입니다.

부분집합에 대한 이전 포스팅 https://bcp0109.tistory.com/17

원소를 일일히 기억할 필요가 없어서 코드가 훨씬 간단해집니다.

배열 인덱스의 처음부터 끝까지 진행하며

1) arr[idx] 값을 더한 경우

2) arr[idx] 값을 더하지 않은 경우

두 가지 경우로 나누어서 탐색합니다.

인덱스의 끝에 도달하면 지금까지 더한 값과 S 를 비교하여 일치할 경우 count++ 해주시면 됩니다.

** 주의사항 **

부분집합을 구하다보면 공집합이 생깁니다.

만약 S 가 0 이라면 공집합때문에 아무 값도 더하지 않아서 0 인 경우도 카운트 하게 됩니다.

이 부분에 대해서만 예외처리를 해주시면 됩니다.

파이썬에서는 조합에 대한 라이브러리를 제공해주기 때문에 그냥 n번만큼 조합을 돌렸습니다.

Problem

• 문제 링크

일곱 난쟁이의 키가 주어졌을 때 합이 100 이 되도록 하는 일곱 난쟁이의 키를 출력하는 문제입니다.

Solution

문제를 살펴보면 일곱명의 합을 전부 다 구해봐야 할 것 같지만 사실은 두명만 구하면 됩니다.

주어진 난쟁이는 9명, 실제 난쟁이는 7명입니다.

9명 중에서 2명의 키를 뺀 값이 100이기 때문에

2명의 합 = 9명의 합 - 100

위 식을 이루는 2명을 구하면 됩니다.

2명의 합을 O(n) 에 구하는 방법은 정렬 후에 양 끝 인덱스부터 차례로 합을 구해서 비교하면 됩니다.

두 값의 합이 target 보다 작다면 왼쪽 인덱스를 하나 증가시키고, target 보다 크다면 오른쪽 인덱스를 하나 감소시킵니다.

Java Code

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] height = new int[9];
        int sum = 0;

        for (int i=0; i<9; i++) {
            int input = Integer.parseInt(br.readLine());
            height[i] = input;
            sum += input;
        }

        Arrays.sort(height);

        eraseTwoHeight(height, sum - 100);

        for (int i=0; i<9; i++) {
            if (height[i] != 0) {
                bw.write(height[i] + "\n");
            }
        }
        bw.flush();
    }

    static void eraseTwoHeight(int[] arr, int target) {
        int left = 0;
        int right = 8;

        while (left < right) {
            int sum = arr[left] + arr[right];

            if (sum == target) {
                arr[left] = 0;
                arr[right] = 0;
                return;
            }
            
            if (sum > target) {
                right--;
            } else {
                left++;
            }
        }
    }
}

문제 링크 : https://www.acmicpc.net/problem/10974

N 을 입력받아 순열을 출력하는 프로그램입니다.

사전 순으로 출력해야하기 때문에  swap 을 이용한 순열 대신 visited 배열로 방문을 체크하는 DFS 방법을 사용하였습니다.

순열에 대한 이전 포스팅 https://bcp0109.tistory.com/14

arr : 순열을 만들 배열

output : 순열을 만든 후 배열

visited : 방문 체크

depth : dfs 깊이

이렇게 4개의 값을 사용하였고, n개중에서 r개를 뽑는 순열을 구현하였습니다.

문제에서 원하는건 n개 중 n개를 뽑는 경우밖에 없으므로 nPn 만 하시면 됩니다.

문제 링크 : https://www.acmicpc.net/problem/2573

빙산 덩어리가 몇년 째에 두 덩어리 이상이 되는 지 계산하는 문제입니다.

<접근>

먼저 빙산이 몇 덩어리 인지는 DFS 로 계산을 하였습니다.

메인 코드에서 DFS 에 들어가는 횟수가 곧 빙산의 갯수입니다.

만약 모든 빙산이 상, 하, 좌, 우로 연결되어 있다면 메인에서 DFS 한번 들어가는 것만으로 모든 빙산을 돌고 나올겁니다.

두번째로 melt 배열을 만들어 녹는 빙산의 높이를 저장하였습니다.

높이는 DFS 를 한번 돌때마다 해당 좌표의 상, 하, 좌, 우를 확인하여 0 인 값이 있으면 melt++ 를 하였습니다.

그리고 빙산의 갯수를 세어 0 개면 0 출력하고 빙산의 갯수가 2개 이상이면 년수를 출력했습니다.

만약 빙산이 아직 한 덩어리라면 높이를 빼주는 melting 함수를 만들었습니다.

2중 for문을 돌면서 빙산의 원래 높이인 map 배열에서 녹은 높이인 melt 배열을 빼줍니다.

그리고 빼준 값이 음수라면 0으로 바꿔줍니다.

이 함수에서 다음 빙산의 갯수를 체크하기 위해 visited 배열과 melt 배열을 초기화해주었습니다.

문제 링크 : https://www.acmicpc.net/problem/7576

제 생각하는 가장 기본적인 BFS 문제입니다.

만약 누군가 BFS 개념을 이제 막 배워서 문제를 추천해달라고 한다면 이 문제를 추천할 겁니다.

<접근>

하루에 상, 하, 좌, 우 한 칸씩 이동하니 BFS가 바로 떠오릅니다.

저는 좌표 관련된 BFS 문제에서는 좌표에 대한 Class를 만들어서 사용합니다.

아래 그림처럼 배열의 숫자를 하나씩 증가시키는 방법도 있지만

저는 클래스에 변수를 하나 더 추가하여 카운트 하는 방법로 풀었습니다.

일반적으로 BFS 문제에서는 visited 2차원 배열을 사용하여 중복 방문을 방지하지만 이 문제에서는 1 이 그 역할을 하고 있습니다.

<순서>

1. 2중 for문으로 box 배열을 돌면서 익은 토마토를 Queue 자료구조에 넣기

2. bfs를 돌면서 토마토 모두 익게 하기

3. 다시 2중 for문 돌면서 안 익은 토마토가 있다면 -1 출력, 없으면 날짜 출력

문제 링크 : https://www.acmicpc.net/problem/1436

666을 포함하는 N 번째 숫자를 출력하는 문제입니다.

한가지 주의할 점은 666이 연속으로 들어가야 하기 때문에 6606, 6066 같은 숫자는 제외된다는 점입니다.

1.  while 문을 통해 숫자를 하나씩 증가시킴

2.  "666"을 포함하는지 비교

3.  만약 포함한다면 N을 1씩 감소시킨 후 N이 0이 되면 break

문제 링크 : https://www.acmicpc.net/problem/1181

N 개의 단어를 받아서

1. 길이가 짧은 것부터

2. 길이가 같으면 사전 순으로

정렬하여 출력하는 문제입니다.

하지만 문제를 자세히 읽어보면 중복된 단어의 경우 한번만 출력한다는 조건이 하나 더 있습니다.

그래서 입력받은 문자를 Set 자료구조에 담아서 중복을 제거한 뒤에 ArrayList로 옮겨서 정렬해주었습니다.