깽미는 24살 모태솔로이다. 깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다. 미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다.

이 앱은 사용자들을 위해 사심 경로를 제공한다. 이 경로는 3가지 특징을 가지고 있다.

1. 사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다.
2. 사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서든 모든 대학교로 이동이 가능한 경로이다.
3. 시간을 낭비하지 않고 미팅할 수 있도록 이 경로의 길이는 최단 거리가 되어야 한다.

만약 도로 데이터가 만약 왼쪽의 그림과 같다면, 오른쪽 그림의 보라색 선과 같이 경로를 구성하면 위의 3가지 조건을 만족하는 경로를 만들 수 있다.

이때, 주어지는 거리 데이터를 이용하여 사심 경로의 길이를 구해보자.

입력

입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000)

둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다.

다음 M개의 줄에 u v d가 주어지며 u학교와 v학교가 연결되어 있으며 이 거리는 d임을 나타낸다. (1 ≤ u, v ≤ N) , (1 ≤ d ≤ 1,000)

출력

깽미가 만든 앱의 경로 길이를 출력한다. (모든 학교를 연결하는 경로가 없을 경우 -1을 출력한다.)

문제 풀이

• 모든 경로를 만든 것을 구하는 최소 스패닝 트리를 구하는 문제라고 생각했다
• MST를 구현하는 알고리즘 중 크루스칼 알고리즘을 사용해서 문제를 해결하자고 생각했다.

1. 먼저 주어진 입력값을 받는다
2. 조건중 동일한 성별이면 LIst에 처음부터 넣지 않는다

int u, v, d;
for (int i = 0; i < M; i++) {
    in = br.readLine().split(" ");
    u = Integer.parseInt(in[0]);
    v = Integer.parseInt(in[1]);
    d = Integer.parseInt(in[2]);

    // 동일한 성별이면 리스트에서 제외한다
    if (arr[u] == arr[v]) continue;

    edgeList.add(new Edge(u, v, d));
}

3. 가중치 크기 순으로 정렬한다

Collections.sort(edgeList, (o1, o2) -> Integer.compare(o1.d, o2.d));

4. 부모를 초기화하고 N-1 까지 연결되면 답을 출력한다

initParents();

int nodeCnt = 0;
int answer = 0;
for (Edge temp : edgeList) {

    if (union(temp.u, temp.v)) {
        nodeCnt++;
        answer += temp.d;
        if (nodeCnt == N - 1) {
            System.out.println(answer);
            return;
        }
    }
}

System.out.println(-1);

풀이 코드

package BOJ;

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

public class BOJ_나만안되는연애_HoonyCode {

    static int N, M;
    static char[] arr;
    static int[] parents;

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


        // 학교의 수 N 과 도로의 개수 M;
        String[] in = br.readLine().split(" ");
        N = Integer.parseInt(in[0]);
        M = Integer.parseInt(in[1]);
        parents = new int[N + 1];

        arr = new char[N + 1];
        in = br.readLine().split(" ");
        // 남 녀 구별 M // W;
        for (int i = 1; i <= N; i++) {
            arr[i] = in[i - 1].charAt(0);
        }

        List<Edge> edgeList = new ArrayList<>();

        int u, v, d;
        for (int i = 0; i < M; i++) {
            in = br.readLine().split(" ");
            u = Integer.parseInt(in[0]);
            v = Integer.parseInt(in[1]);
            d = Integer.parseInt(in[2]);

            if (arr[u] == arr[v]) continue;

            edgeList.add(new Edge(u, v, d));
        }

        Collections.sort(edgeList, (o1, o2) -> Integer.compare(o1.d, o2.d));

        initParents();

        int nodeCnt = 0;
        int answer = 0;
        for (Edge temp : edgeList) {

            if (union(temp.u, temp.v)) {
                nodeCnt++;
                answer += temp.d;
                if (nodeCnt == N - 1) {
                    System.out.println(answer);
                    return;
                }
            }
        }

        System.out.println(-1);
    }

    static boolean union(int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) {
            return false;
        } else {
            parents[y] = x;
            return true;
        }
    }

    static void initParents() {
        for (int i = 1; i <= N; i++) {
            parents[i] = i;
        }
    }

    static int find(int x) {

        if (x != parents[x]) {
            return parents[x] = find(parents[x]);
        }
        return parents[x];
    }

    static class Edge {
        int u, v, d;

        public Edge(int u, int v, int d) {
            this.u = u;
            this.v = v;
            this.d = d;
        }
    }

}

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

문제 풀이

• 음의 가중치 값이 있는 문제는 벨만포드 알고리즘을 사용해서 풀면 된다고 생각했다

1. Edge class 를 만들어서 다음 노드와 가중치를 adjList에 넣는다

for (int i = 0; i < M; i++) {
    input = br.readLine().split(" ");
    from = Integer.parseInt(input[0]);
    to = Integer.parseInt(input[1]);
    weight = Integer.parseInt(input[2]);
    adjlist[from].add(new Edge(to, weight));
}

2. 벨만포드 알고리즘을 사용해서 N번 돌았을 때 값이 변경된다면 사이클이 존재한다는 뜻으로 -1값을 출력한다

long[] dist = new long[N + 1];
Arrays.fill(dist, Integer.MAX_VALUE);

dist[1] = 0;
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        for (Edge edge : adjlist[j]) {
            if (dist[j] != Integer.MAX_VALUE && dist[edge.to] > dist[j] + edge.weight) {
                dist[edge.to] = dist[j] + edge.weight;
                if (i == N) {
                    System.out.println(-1);
                    return;
                }
            }
        }
    }
}

3. 사이클이 존재하지 않는다면 갈수 없는 지역은 -1로 갈 수 있는 곳은 최소값을 출력한다

StringBuilder sb = new StringBuilder();
for (int i = 2; i <= N; i++) {
    if (dist[i] == Integer.MAX_VALUE)
        sb.append(-1).append('\n');
    else
        sb.append(dist[i]).append('\n');
}
System.out.print(sb.toString());

코드

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

public class Main {

    static int N, M;
    static List<Edge>[] adjlist;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

        adjlist = new List[N + 1];
        for (int i = 1; i <= N; i++) {
            adjlist[i] = new ArrayList<>();
        }

        int from, to, weight;
        for (int i = 0; i < M; i++) {
            input = br.readLine().split(" ");
            from = Integer.parseInt(input[0]);
            to = Integer.parseInt(input[1]);
            weight = Integer.parseInt(input[2]);
            adjlist[from].add(new Edge(to, weight));
        }

        bellmanford();

    }

    private static void bellmanford() {
        long[] dist = new long[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        dist[1] = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                for (Edge edge : adjlist[j]) {
                    if (dist[j] != Integer.MAX_VALUE && dist[edge.to] > dist[j] + edge.weight) {
                        dist[edge.to] = dist[j] + edge.weight;
                        if (i == N) {
                            System.out.println(-1);
                            return;
                        }
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= N; i++) {
            if (dist[i] == Integer.MAX_VALUE)
                sb.append(-1).append('\n');
            else
                sb.append(dist[i]).append('\n');
        }
        System.out.print(sb.toString());

    }

    static class Edge {
        int to;
        int weight;

        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
}

명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하는지 결정하지 못했다. 어떤 경로를 거칠지 정해서, 이를 경로표로 정리하는 것이 여러분이 할 일이다.

예시된 그래프에서 굵게 표시된 1, 2, 3, 4, 5, 6은 집하장을 나타낸다. 정점간의 간선은 두 집하장간에 화물 이동이 가능함을 나타내며, 가중치는 이동에 걸리는 시간이다. 이로부터 얻어내야 하는 경로표는 다음과 같다.

경로표는 한 집하장에서 다른 집하장으로 최단경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 나타낸 것이다. 예를 들어 4행 5열의 6은 4번 집하장에서 5번 집하장으로 최단 경로를 통해 가기 위해서는 제일 먼저 6번 집하장으로 이동해야 한다는 의미이다.

이와 같은 경로표를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경로가 주어지는데, 두 집하장의 번호와 그 사이를 오가는데 필요한 시간이 순서대로 주어진다. 집하장의 번호들과 경로의 소요시간은 모두 1000이하의 자연수이다.

출력

예시된 것과 같은 형식의 경로표를 출력한다.

문제 풀이

• 문제를 보고 든 생각은 노드가 200개 밖에 안 되는 것이 보였다
• 200 * 200 * 200 = 8000000 => 플로이드 와샬로 문제를 해결 할 수 있다고 판단했다

먼저 플로이드 와샬로 최단거리를 구하는 동시에

PointMap이라는 배열에 중간에 처음으로 거치는 자표를 넣어서 문제를 해결할려고 했다

1. 먼저 PointMap를 자신의 노드 값으로 초기화 한다

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        pointMap[i][j] = j;
    }
}

2. 플로이드 와샬을 사용해서 중간에 거치는 노드가 생기면 pointMap[i][j] = pointMap[i][k] 값을 저장한다

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (map[i][j] > map[i][k] + map[k][j]) {
                map[i][j] = map[i][k] + map[k][j];
                pointMap[i][j] = pointMap[i][k];
            }
        }
    }
}

3. 저장된 값을 출력한다

StringBuilder sb = new StringBuilder();

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if (i == j) {
            sb.append('-').append(' ');
            continue;
        }
        sb.append(pointMap[i][j]).append(' ');
    }
    sb.append('\n');
}

System.out.print(sb);

풀이 코드

package BOJ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ_택배_HoonyCode {

    static int n, m;
    static int[][] map;
    static int[][] pointMap;

    private static final int MAX = 200 * 10000;

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

        String[] in = br.readLine().split(" ");

        n = Integer.parseInt(in[0]);
        m = Integer.parseInt(in[1]);

        map = new int[n + 1][n + 1];
        pointMap = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            Arrays.fill(map[i], MAX);
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                pointMap[i][j] = j;
            }
        }

        int A, B, W;
        for (int i = 0; i < m; i++) {
            in = br.readLine().split(" ");
            A = Integer.parseInt(in[0]);
            B = Integer.parseInt(in[1]);
            W = Integer.parseInt(in[2]);

            map[B][A] = map[A][B] = Math.min(map[A][B], W);
        }


        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (map[i][j] > map[i][k] + map[k][j]) {
                        map[i][j] = map[i][k] + map[k][j];
                        pointMap[i][j] = pointMap[i][k];
                    }
                }
            }
        }


        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    sb.append('-').append(' ');
                    continue;
                }
                sb.append(pointMap[i][j]).append(' ');
            }
            sb.append('\n');
        }

        System.out.print(sb);
    }

}

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한 사항

• n은 1 이상, 2000 이하인 정수입니다.

입출력 예

입출력 예 설명

입출력 예 #1 위에서 설명한 내용과 같습니다.

입출력 예 #2 (2칸, 1칸) (1칸, 2칸) (1칸, 1칸, 1칸) 총 3가지 방법으로 멀리 뛸 수 있습니다.

풀이 과정

전형적인 dp 문제라고 생각하고 문제를 풀었다

• 점화식을 세우면

  dp[i] = dp[i-1] + dp[i-2] 이다

• 위의 점화식을 이용해서 코드를 구현한다

코드

class Solution {
    public long solution(int n) {
        long answer = 0;

        // dp 문제인것 같다
        final int div = 1234567;

        //n은 1이상 2000이하인 정수
        int[] dp = new int[2001];

        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n ; i++){
            dp[i] = (dp[i-1] + dp[i-2])%div;
        }

        answer = dp[n];

        return answer;
    }
}

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

1. 124 나라에는 자연수만 존재합니다.
2. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.

예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• n은 500,000,000이하의 자연수 입니다.

풀이 과정

1, 2, 4가 3개이기 때문에 3의 배수로 문제를 풀 수 있다고 생각했다.

• 먼저 각 수를 3으로 나누어 보았다
• 나머지가 그 12일 때는 그 수가 되었고, 0일 때는 4를 나타내면 된다는 것을 발견했다.
• 마지막으로 나눈 나머지가 0일 때는 몫에서 -1을 해주면 되고 아니면 몫을 또 3으로 나누었을때 나머지가 그 자리수가 되는 것을 발견했다

위의 내용을 코드로 구현하자면,

코드

class Solution {
    public String solution(int n) {
        StringBuilder sb = new StringBuilder();

        int temp = n;
        int remain;

        while (temp > 0) {
            remain = temp % 3;
            if (remain == 0){
                temp = temp/3 - 1;
            }else
                temp = temp/3;

            if (remain == 0) {
                sb.append(4);
            } else {
                sb.append(remain);
            }
        }

        return sb.reverse().toString();
    }
}

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.

동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.

동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다.

출력

첫째 줄에 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력한다.

예제 입력 1 복사

abab

예제 출력 1 복사

5

풀이

• 팰린드롬이 홀수일 경우와 짝수일 경우로 나뉘어 풀 수 있었다.

• 길이가 홀수일 경우
  • len-2 부터 시작해서 [i-J+1] [i+J]를 탐색한다

• 길이가 짝수일 경우

  • 문자 길이가 2로 나눴을때 1이 남는다면 길이에 +1을 더해준다
  • len-2 부터 시작해서 [i-j+1] [i+j]를 탐색한다

• 길이가 짧은 것을 answer에 담는다.

코드

public class Main {

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

        char[] chars = br.readLine().toCharArray();

        int len = chars.length;

        int answer = (len-1) * 2 + 1;

        if (len == 1){
            System.out.println(1);
            return;
        }


        // 홀수일 경우
        loop : for (int i  = len-2 ; i > len/2-1 ; i--){

            for (int j = 1; j + i < len;  j++){
                if (chars[i-j] != chars[i+j]) continue loop;
            }

            answer = Math.min(answer, i * 2 + 1 );
        }


        // 짝수일 경우
        int end = len;
        if (len % 2 == 1) end++;
        loop : for (int i  = len-2 ; i >= end/2-1 ; i--){

            for (int j = 1; j + i < len;  j++){
                if (chars[i-j+1] != chars[i+j]) continue loop;
            }

            answer = Math.min(answer, (i+1)*2) ;
        }

        System.out.println(answer);
    }
}

총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.

이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.

톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 예를 들어, 아래와 같은 경우를 살펴보자.

두 톱니바퀴의 맞닿은 부분은 초록색 점선으로 묶여있는 부분이다. 여기서, 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다. 2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다. 따라서, 아래 그림과 같은 모양을 만들게 된다.

위와 같은 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면, 2번 톱니바퀴가 반시계 방향으로 회전하게 되고, 2번이 회전하기 때문에, 3번도 동시에 시계 방향으로 회전하게 된다. 4번은 3번이 회전하지만, 맞닿은 극이 같기 때문에 회전하지 않는다. 따라서, 아래와 같은 상태가 된다.

톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

출력

총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

문제 풀이

• 먼저 시계방향으로 돌 때
• 반시계방향으로 돌 때
• 톱니바퀴의 변화를 구현한다

public static void rotate(int[] spins, int state) {
    if (state == 1) { // 시계방향

        int temp = spins[7];

        for (int i = 7; i > 0; i--) {
            spins[i] = spins[i - 1];
        }

        spins[0] = temp;

    } else { // 반시계 방향

        int temp = spins[0];

        for (int i = 0; i < 7; i++) {
            spins[i] = spins[(i + 1)];
        }

        spins[7] = temp;
    }
}

• 위의 구현이 끝나면
• 오른쪽 왼쪽 톱니바퀴가 돌 수 있는지 확인하고 탐색한다

for (int i = 0; i < K; i++) {
    in = br.readLine().split(" ");
    N = Integer.parseInt(in[0]) - 1;
    S = Integer.parseInt(in[1]); // 1시게 -1 반시계 // 0 멈춤

    Arrays.fill(v, false);
    queue.clear();
    queue.offer(new int[]{N, S});
    v[N] = true;

    int[] cur;
    while (!queue.isEmpty()) {
        cur = queue.poll();

        int nx;
        for (int d = 0; d < 2; d++) {
            nx = cur[0] + dx[d];

            if (nx < 0 || nx > 3) continue;
            if (v[nx]) continue;
            v[nx] = true;
            //왼쪽일 떄
            if (d == 0) {
                if (spins[nx][2] == spins[cur[0]][6]) continue;
                queue.offer(new int[]{nx, -cur[1]});
            } else {//오른쪽 일 떄
                if (spins[nx][6] == spins[cur[0]][2]) continue;
                queue.offer(new int[]{nx, -cur[1]});
            }
        }

        rotate(spins[cur[0]], cur[1]);
    }
}

• 마지막으로 톱니바퀴 점수를 answer에 저장하고 출력한다.

for (int i = 0; i < 4; i++) {
    answer += (spins[i][0] << i);
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    static int[] dx = {-1, 1};

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 톱니바퀴
        int[][] spins = new int[4][8];
        int answer = 0;
        String[] in;

        for (int i = 0; i < 4; i++) {
            in = br.readLine().split("");
            for (int j = 0; j < 8; j++) {
                spins[i][j] = Integer.parseInt(in[j]);
            }
        }


        // 회전 횟수
        int K = Integer.parseInt(br.readLine());

        int N;
        int S;

        boolean[] v = new boolean[4];
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < K; i++) {
            in = br.readLine().split(" ");
            N = Integer.parseInt(in[0]) - 1;
            S = Integer.parseInt(in[1]); // 1시게 -1 반시계 // 0 멈춤

            Arrays.fill(v, false);
            queue.clear();
            queue.offer(new int[]{N, S});
            v[N] = true;

            int[] cur;
            while (!queue.isEmpty()) {
                cur = queue.poll();

                int nx;
                for (int d = 0; d < 2; d++) {
                    nx = cur[0] + dx[d];

                    if (nx < 0 || nx > 3) continue;
                    if (v[nx]) continue;
                    v[nx] = true;
                    //왼쪽일 떄
                    if (d == 0) {
                        if (spins[nx][2] == spins[cur[0]][6]) continue;
                        queue.offer(new int[]{nx, -cur[1]});
                    } else {//오른쪽 일 떄
                        if (spins[nx][6] == spins[cur[0]][2]) continue;
                        queue.offer(new int[]{nx, -cur[1]});
                    }
                }

                rotate(spins[cur[0]], cur[1]);
            }
        }


        for (int i = 0; i < 4; i++) {
            answer += (spins[i][0] << i);
        }

        System.out.println(answer);

    }


    public static void rotate(int[] spins, int state) {
        if (state == 1) { // 시계방향

            int temp = spins[7];

            for (int i = 7; i > 0; i--) {
                spins[i] = spins[i - 1];
            }

            spins[0] = temp;

        } else { // 반시계 방향

            int temp = spins[0];

            for (int i = 0; i < 7; i++) {
                spins[i] = spins[(i + 1)];
            }

            spins[7] = temp;
        }
    }
}

팩토리 매서드 패턴은 객체를 생성하는 공장을 만드는 것으로서 어떤 객체를 만드는 지는 자식 클래스에서 결정하게 하는 디자인 패턴이다.

• 객체를 생성하기 위해 인터페이스를 정의하지만, 어떤 클래스의 인스턴스를 생성할지에 대한 결정은 서브 클래스가 내리도록 하는 패턴
• 하위 클래스에서 팩토리 매서드를 override해서 객체를 반환하게 하는 패턴이다.

왜 사용하는가?

• 어떤 클래스가 자신이 생성해야 하는 객체의 클래스를 예측할 수 없을 때
• 생성할 객체를 기술하는 책임을 자신의 서브클래스가 지정했으면 할 때
• 객체 생성의 책임을 몇 개의 보조 서브클래스 가운데 하나에게 위임하고, 어떤 서브클래스가 위임자인지에 대한 정보를 국소화 시키고 싶을 때

팩토리 메서드 구조

Product

• 팩토리 매서드가 생성하는 객체의 인터페이스를 정의한다.

ConcreteProduct

• Product 클래스에 정의된 인터페이스를 실제로 구현하는 클래스

Creator

• Product 타입의 객체를 반환하는 팩토리 매서드를 선언하는 클래스
• 팩토리 매서드를 기본적으로 구현, ConcreteProduct 객체를 반환한다.
• Product 객체의 생성을 위해 팩토리 매서드를 호출한다.

ConcreteCreator

• 팩토리 메서드를 재정의하여 ConcreteProduct의 인스턴스를 반환

구현시 고려할 점

팩토리 매서드 패턴의 구현 방법은 크게 두가지가 있다

• Creator를 추상 클래스로 정의하고, 팩토리 매서드는 abstract로 선언하는 방법
• Creator를 구체 클래스이고, 팩토리 메서드의 기본 구현을 제공하는 방법

팩토리 매서드의 인자를 통해 다양한 Product를 생성하게 된다.

• 팩토리 매서드에 잘못된 인자가 들어올 경우의 런타임 에러 처리에 대해 고민할 것
• Enum 등을 사용하는 것도 고려할 필요가 있다.

장점과 단점

장점

• 객체 생성에 관련한 코드와 동작 코드를 분리할 수 있다.

예시

• 궁수와 전사 캐릭터가 있습니다.
• 레벨업시 두 직업간의 차이가 계속 생길 것을 대비하여, 다른 클래스를 통해 두 개의 클래스를 생성합니다.
  • 이러한 과정에서 신규캐릭터를 인스턴스화 하는 경우, 팩토리 패턴을 사용하여 이를 구성하겠습니다.

코드

Character.java

package Velog;

public abstract class Character {

    protected int STR;
    protected int DEX;

    public abstract void levelUp();

    public int getSTR() {
        return STR;
    }

    public void setSTR(int STR) {
        this.STR = STR;
    }

    public int getDEX() {
        return DEX;
    }

    public void setDEX(int DEX) {
        this.DEX = DEX;
    }
}

Archer.java

package Velog;

public class Archer extends Character {
    @Override
    public void levelUp() {
        this.STR += 10;
        this.DEX += 30;
    }
}

Warrior.java

package Velog;

public class Warrior extends Character {

    @Override
    public void levelUp() {
        this.STR += 30;
        this.DEX += 10;
    }
}

CharacterCreator.java

package Velog;

public abstract class CharacterCreator {

    public Character CharacterCreator() {
        final Character character = character();

        character.setDEX(100);
        character.setSTR(100);

        return character;
    }


    protected abstract Character character();
}

ArcherCreator.java

package Velog;

public class ArcherCreator extends CharacterCreator{
    @Override
    protected Character character() {
        return new Archer();
    }
}

warriorCreator.java

package Velog;

public class WarriorCreator extends CharacterCreator{
    @Override
    protected Character character() {
        return new Warrior();
    }
}

연산이 많이 않을때는 특별한 이슈가 발생할 가능성이 거의 없지만, 연산횟수가 많아지거나 멀티스레드, 경쟁 상태(Race Condition) 등의 상황이 자주 발생하면 각 클래스의 특징을 이해하고 상황에 맞는 적절한 클래스를 사용해야 한다.

String과 StringBuffer와 StringBuilder의 기본적인 차이는 String은 불변(Immutable), StringBuffer와 StringBuilder는 변함(Mutable) 이다.

1. String

string 객체는 한번 생성됨면 할당된 메모리 공간이 변하지 않는다.

concat 메서드 또는 + 연산자를 통해 기존에 생성된 String 클래스 객체 문자열에 다른 문자열을 붙여도 기존 문자열에 새로운 문자열을 붙이는 것이 아니라 새로운 String 객체를 만든 후 새 String 객체에 연결된 문자열을 저장하고 그 객체를 참조하도록 하는 것이다.

즉, String 클래스 객체는 Heap 메모리 영역에 생성하고 한번 생성된 객체 내부 내용을 변화시킬 수 없다.

String 객체는 문자열 연산이 많은 경우 성능이 좋지 않다

String str = "Hello"; // 메모리에 Hello 담는다.

str = str.concat(" World"); //기존 메로리 Hello에 값을 붙이는 것이 아니라 새로운 메모리에 Hello World를 담는다.

2. StringBuffer와 StringBuilder

StringBuffer와 StringBuilder는 String과 다르게 동작한다.

문자열 연산 등으로 기존 객체의 공간이 부족하게 되는 경우 기존의 버퍼 크기를 늘리면 유연하게 동작한다. StringBuffer와 StringBuilder 클래스가 제공하는 메서드는 서로 동일하다.

차이점

• 멀티스레드 환경이라면 값의 동기화 보장을 위해 StringBuffer를 사용하는 것이 좋다.
• 단일스레드 환경이라면 StringBuilder를 사용하는 것이 좋다.
  • StringBuffer는 동기화 관련 처리로 인해 StringBuilder에 비해 성능이 좋지 않다

StringBuilder sb = new StringBuilder();
sb.append("Hello"); // 기존 메모리를 늘려 Hello 추가
sb.append(" ").append("world") // 기존 메모리를 늘려 " "와 "world" 추가

3. 정리

보통 사용할 떄 String을 사용하고,

출력값이 많아지거나 String에서 + 연산자나 , concat() 메서드 사용이 많아진다면 StringBuilder를 사용하자!

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
• 바위는 1개 이상 50,000개 이하가 있습니다.
• n 은 1 이상 바위의 개수 이하입니다.

입출력 예

입출력 예 설명

문제에 나온 예와 같습니다.

출처

※ 공지 - 2020년 2월 17일 테스트케이스가 추가되었습니다.

문제 풀이

문제를 풀 때 먼저 생각한 방법은 n개를 고르고 완전 탐색하는 방법이었다 하지만 그 방법을 실행했을 때

최악의 경우일 때 시간 초과를 발생시킨다는 것을 알고 다른 방법을 찾았다.

다른 방법은 문제를 다르게 생각해보는 것이었다.

특정 값에서 n개를 지울 수 있는지?를 생각하는 방법이었다.

특정 값(돌의 길의 최솟값)보다 작은 사이에 값을 가질 때마다 제거할 수 있는 돌로 remove++ 해준다

모든 거리를 비교하고 나서, 제거할 수 있는 돌이 n개보다 큰 경우, 작은 경우에 따라서 범위를 재 조정해간다

코드

import java.util.Arrays;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;

        Arrays.sort(rocks);

        int start = 0;
        int end = distance;

        while (start <= end) {
            int mid = (start + end) / 2;
            int remove = 0;
            int prev = 0;

            for (int i = 0; i < rocks.length; i++) {

                if (rocks[i] - prev < mid) {
                    remove++;
                } else {
                    prev = rocks[i];
                }

            }

            if (distance - prev < mid) remove++;

            if (remove <= n) {
                answer = Math.max(answer, mid);

                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }


        return answer;
    }
}

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

입출력 예 설명

예제 #1 문제에 나온 예와 같습니다.

예제 #2 target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

문제 풀이

넓이 우선 탐색을 사용하자

1. 단어와 과정의 수를 넣을 Pair라는 클래스를 만들자
2. Queue를 만들어서 new pair(과정의수 : 0, 시작 단어 : begin)을 넣습니다.
3. queue에서 데이터를 뽑고 str와 한 문자가 다른 문자열을 words에서 찾아 다시 queue에 넣습니다
4. 위의 과정을 반복하면서 target 문자열을 찾습니다.

없을 경우를 처리할때

cnt가 words의 개수보다 커지면 모든 경우를 다 둘러보았기 때문에 없다고 판단하면 됩니다.

아래와 같은 if문으로 처리해줍니다.

if (cur.str.equals(target)) {
  answer = cur.cnt;
  break;
}

코드

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 100;
        Queue<Pair> queue = new LinkedList<>();
        queue.offer(new Pair(0, begin));
        int len = words.length;
        Pair cur;

        while (!queue.isEmpty()) {
            cur = queue.poll();

            if (cur.str.equals(target)) {
                answer = cur.cnt;
                break;
            }
            if (cur.cnt > len){
                continue;
            }

            for (String word : words) {
                int cnt = 0;

                for (int i = 0 ; i < begin.length() ; i++){
                    if (word.charAt(i) != cur.str.charAt(i)) {
                        cnt++;
                    }
                }

                if (cnt == 1){
                    queue.offer(new Pair(cur.cnt + 1, word));
                }
            }

        }

        return answer == 100 ? 0 : answer;
    }
}

class Pair{
    int cnt;
    String str;

    public Pair(int cnt, String str) {
        this.cnt = cnt;
        this.str = str;
    }
}

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

입출력 예 설명

예제 #1 아래와 같이 2개의 네트워크가 있습니다.

예제 #2 아래와 같이 1개의 네트워크가 있습니다.

풀이 과정

BFS(넓이 우선 탐색)을 이용해서 문제를 풀자

1. boolean[] v 배열을 이용해서 탐색한 곳은 true로 만들어 준다
2. v[i] = false이면 그 지점부터 연결된 곳들을 모두 탐색한다
3. 탐색을 시작할 때마다 answer을 1증가 시키면 답이 된다

package PROGRAMMERS;

import java.util.LinkedList;
import java.util.Queue;

public class PRO_네트워크_HoonyCode {

    class Solution {

        boolean[] v;

        public int solution(int n, int[][] computers) {
            int answer = 0;

            //bfs로 그 점이랑 연결되어 있는 부분을 찾아 내자
            v = new boolean[n];

            for (int i = 0; i < n; i++) {
                if (v[i]) continue;
                answer++;
                bfs(i, computers, n);
            }

            return answer;
        }


        public void bfs(int start, int[][] computers, int size) {
            Queue<Integer> que = new LinkedList<>();
            que.offer(start);
            v[start] = true;


            int cur;
            while (!que.isEmpty()) {
                cur = que.poll();

                for (int i = 0; i < size; i++) {
                    if (computers[cur][i] != 1) continue;
                    if (v[i]) continue;

                    v[i] = true;
                    que.offer(i);
                }
            }

        }
    }
}

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

입출력 예 설명

문제 풀이

문제 풀이는 아래의 그림과 같다

1. map[i][1] = 1로 초기화 시킨다.
2. map[1][i] = 1로 초기화 시킨다.,
3. map[i][j] = map[i-1][j] + ma[i][j-1] 를 하면 아래의 그림과 같이 나타낼 수 있다.

예외 처리

1. map[1][i], map[i][1]에 연못이 있는 경우에는 그 연못부터 끝까지 0처리를 해줘야 한다
2. map[i][j]에 연못이 있는 경우에는 그 부분만 0로 만들어 주면된다!
3. 1_000_000_007을 넘어가는 경우가 있을 수 있기 때문에 map[i][j] = ((map[i-1][j] % DIV ) + (map[i][j-1] % DIV)) % DIV 하면 된다

예시 아래의 그림과 같다.

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        final int DIV = 1_000_000_007;

        // m, n이 주어진다 m : col n : row;

        int[][] map = new int[n + 1][m + 1];

        for (int i = 1 ; i <= n ; i++){
            Arrays.fill(map[i], Integer.MAX_VALUE);
        }

        // 초기화
        for (int i = 1 ; i <= n ; i++) map[i][1] = 1;
        for (int j = 1 ; j <= m ; j++) map[1][j] = 1;



        //puddles m , n
        int row, col;
        for (int[] puddle : puddles){
            col = puddle[0];
            row = puddle[1];

            if (row == 1){
                for (int i = col ; i <= m ; i++){
                    map[row][i] = 0;
                }
            }else if(col == 1){
                for (int i = row ; i <= n ; i++){
                    map[i][col] = 0;
                }
            }else{
                map[row][col] = 0;
            }
        }

        for (int i = 2 ; i <= n ; i++){
            for (int j = 2 ; j <= m ; j++){
                if (map[i][j] == 0) continue;
                map[i][j] = ((map[i - 1][j] % DIV) + (map[i][j - 1] % DIV)) % DIV;
            }
        }


        return map[n][m];
    }
}