Problem

• 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17681

주어지는 두개의 지도를 겹친 결과를 출력하는 문제입니다.

Solution

그림만 봐도 알수 있듯이 겹치는 부분은 # 겹치지 않은 부분은 빈칸으로 나옵니다.

친절하게 비트로 풀라고 안내까지 해주고 있으니 Integer.toBinaryString 함수를 사용하여 계산을 해줍니다.

1 과 0 으로 이루어진 String을 replaceAll로 전부 바꿔주면 됩니다.

한 가지 주의할 점이 하나 있습니다.

1111(2) 처럼 자릿수가 작은 글자는 n이 5일때 01111로 바꿔주어야 합니다.

여기서는 자리수를 맞춰주는 String.format 함수를 사용하여 n 자리만큼 공백으로 채워줍니다.

Java Code

class Solution {
    static public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];

        for (int i=0; i<n; i++) {          
            String temp = Integer.toBinaryString(arr1[i] | arr2[i]);  
            temp = String.format("%" + n + "s", temp);
            temp = temp.replaceAll("1", "#");
            temp = temp.replaceAll("0", " ");
            answer[i] = temp;
        }

        return answer;
    }
}

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

해석 때문인지는 몰라도 문제를 이해하는데 살짝 어려움을 겪은 문제입니다.

결론을 말하자면 상범이에게 꽃을 주는 날의 최대값을 구하면 됩니다.

이 문제의 핵심은 다음과 같습니다.

1. 상범이의 우울한 정도는 상관없다. 양수, 음수인지만 판단

2. 꽃은 하루에 한개씩만 준다.

3. 꽃을 다 주지 못해도 최대한 준다. 둘째날이 우울한 날이라면 꽃은 첫째날밖에 못준다. 그래도 주자.

4. 3T만큼 꽃을 주는 날은 여러 개의 최장 우울 기간 중 한번이다.

문제를 해결하려면 결국 최장 우울 기간 중 가장 꽃을 많이 줄 수 있는 날이 언제인지 찾는 것이 중요합니다.

이걸 직접 구하는 것보다는 최장 우울 기간 전부 탐색하면서 max값을 구하는 것이 편합니다.

우선 모든 날에 대해서 2T만큼 꽃 주는 날을 구합니다.

그 후에 최장 우울 기간들만 스캔하면서 또다시 3T만큼 카운트합니다.

이 때 2T 구할때 체크했던 날들은 제외해서 중복 체크를 방지합니다.

문제에 있는 예제로 간단하게 설명해보겠습니다.

먼저 상범이의 우울한 날을 구합니다.

그림 1에서 상범이의 최장 우울 기간은 1이고, 최장 우울 기간의 갯수는 3개입니다.

그럼 우선 최장 우울 기간과 관계 없이 모든 우울 기간에 대해서 2T만큼 꽃을 주겠습니다.

우울한 날이 2일이므로 0일과 1일에 꽃을 주어야 합니다.

하지만 보시다시피 0일은 존재하지 않습니다.

이 때, 위에서 언급한 핵심 3번을 보시면 꽃을 다 주지 못해도 최대한 주라는 조건이 있습니다.

그래서 그림 2처럼 체크하면 됩니다.

그리고 두번째로 우울한 날에 대해서 꽃을 줍니다.

그림 3처럼 4일과 5일에 꽃을 줄 수 있습니다.

마지막으로 우울한 날에 대해서 꽃을 줍니다.

8일이 우울한 날이기 때문에 6일과 7일에 꽃을 줍니다.

여기서 헷갈릴 수 있는 요소가 하나 있는데 우울한 날과 관계없이 꽃은 줄 수 있습니다.

따라서 그림 4처럼 2T만큼 모든 우울한 날에 대해서 체크를 하였습니다.

2T를 전부 체크한 시점에서 꽃을 주는 날의 count는 5 입니다.

이제 3T의 최대값을 구해야 합니다.

최장 우울 기간에 해당하는 모든 우울한 날에 대해서 3T를 구합니다.

첫번째 날은 보시다시피 꽃을 더 줄 수 없습니다.

add는 0 입니다.

두번째 우울한 날에 대해서 3T를 구합니다.

우울 기간이 1이기 때문에 꽃을 하루 더 줄 수 있습니다.

이때, 꽃을 줄 수 있는 날은 카운트만 하고 표시는 하지 않습니다.

3T는 모든 여러가지 최장 우울 기간 중 단 한번만 주면 되기 때문입니다.

만약 최장 우울 기간이 1이 아니라 3 정도 되고 3T를 구할때마다 모든 날에 체크를 한다면 뒤에 나오는

최장 우울 기간에는 꽃을 줄  수 있는 날이 없을수도 있고, 그럼 모든 경우의 수를 알 수 없습니다.

아무튼 여기서 add는 1이고 기존의 count 5와 더해서 max 값을 6으로 갱신합니다.

마지막 우울한 날에 대해서 3T를 구합니다.

하지만 이미 3일 전인 5, 6, 7일 전부 꽃을 주기로 되있으므로 꽃을 더 줄 필요가 없습니다.

따라서 추가로 주는 꽃은 없고 add는 0입니다.

최종적으로 꽃을 주는 날은 위와 같고 최대값은 6이 됩니다.

** 코드에서는 뒤에서부터 돌면서 미리 꽃을 주었습니다.

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

매우 간단한 구현 문제입니다.

종료 조건이 없기 때문에 StringTokenizer의 st.hasMoreTokens로 토큰이 있는지 검사해도 되지만

저는 어차피 첫번째 줄에만 입력이 들어온다는 조건이 있기 때문에 한줄 받아서 Split(" ")을 사용했습니다.

출처 : https://gist.github.com/psayre23/c30a821239f4818b0709

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

숨바꼭질 시리즈의 세번째 문제입니다.

이번에는 수빈이가 동생을 만나는 최단 시간을 찾는 문제이지만, *2를 0초만에 이동할 수 있다는 점이 다릅니다.

역시 BFS를 이용해서 풀었으며 -1, +1 하는 위치를 구하기 전에 *2인 위치를 먼저 계산했습니다.

단순히 *2인 위치만을 계산한게 아니라 최대 위치인 100,000까지 전부 계산해둡니다.

그러면 시간이 작은 노드들이 무조건 Queue에 먼저 들어가게 됩니다.

이 문제를 푸는데 굉장히 많은 시도를 하였습니다.

처음에는 제 생각이 잘못되었나 해서 우선순위큐를 써보기도 하고 중복 방문에 대해서 계산도 하였습니다.

그런데 고생한 보람에 비해 해결은 굉장히 싱거웠습니다.

*2를 계산한 후에 저는 +1, -1 순서대로 계속 Queue에 넣었는데 -1, +1 순서로 바꾸니까 통과하였습니다.

정확히 계산을 해보진 않았지만 +1을 먼저 Queue에 넣게 되면 -k 만큼 이동한 후에 *2 를 한 경우를 간과하고 끝날 수 있는 것 같습니다.

예시로 들면 4 6 이라는 입력이 들어오면 +1 +1 이동보다 -1 *2 이동 시간이 더 작습니다.

하지만 Queue에 넣는 순서에 따라서 결과값이 달라질 수 있으니 앞으로는 좀 더 생각하며 로직을 짜야 할 것 같습니다.

<Java>

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

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

class Main {
    static int stoi(String s) {
        return Integer.parseInt(s);
    }

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

        st = new StringTokenizer(br.readLine());

        int N = stoi(st.nextToken());
        int K = stoi(st.nextToken());

        if(N >= K)
            System.out.println(N-K);
        else
            System.out.println(BFS(N, K));
    }

    static int BFS(int N, int K) {
        Queue q = new LinkedList();
        int[] subin = new int[100001];
        Arrays.fill(subin, -1);

        q.add(N);
        subin[N] = 0;

        while(!q.isEmpty()) {
            int now = q.poll();

            // 동생을 만나면 끝
            if(now == K)
                return subin[now];

            // *2 인 거리 중 방문하지 않은 곳 전부 체크
            int temp = now * 2;
            while(temp <= 100000 && subin[temp] == -1) {
                subin[temp] = subin[now];
                q.add(temp);
                temp *= 2;
            }

            for(int i=0; i<2; i++) {
                int next;
                
                if(i == 0)
                    next = now - 1;
                else
                    next = now + 1;

                if(0 <= next && next <= 100000) {
                    if(subin[next] == -1) {
                        q.add(next);
                        subin[next] = subin[now] + 1;
                    }
                }
            }
        }

        return 0;
    }
}

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

수혀니가 있는 1번 헛간으로부터 가장 먼 헛간들의 갯수, 거리를 구하는 문제입니다.

간선 가중치가 없고 모든 최장거리를 전부 구해야되기 때문에 BFS를 사용하면 쉽게 해결할 수 있습니다.

한가지 주의할 점은 N이 최대 20,000 이기 때문에 O(N^2)인 인접행렬을 이용할 경우 시간초과가 납니다.

인접리스트 BFS를 돌면서 최대 거리, 최대 거리의 갯수, 재서기가 숨은 가장 작은 헛간을 찾아주시면 됩니다.

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

문제는 굉장히 길지만 핵심은 포켓몬을 말하면 번호를, 번호를 말하면 포켓몬을 출력하는 문제입니다.

포켓몬이 최대 100,000마리이기 때문에 Map 자료구조를 사용하여 key, value를 바꿔가며 두번씩 넣었습니다.

간단하니 코드로 보는게 이해하기 쉽습니다.

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

수빈이가 동생과 만나는 시간을 출력하는 문제입니다.

간단하게 BFS를 이용하여 해결할 수 있습니다.

처음 수빈이의 위치를 Queue에 넣고 +1, -1, *2 한 위치를 각각 Queue에 넣어가며 BFS를 합니다.

그리고 수빈이가 한번 방문했던 위치를 계속 체크하여 중복 방문을 하지 않도록 하면 됩니다.

그리고 수빈이의 시작 위치가 동생보다 크다면 무조건 -1을 반복하여 만나는 수밖에 없으므로 N-K를 바로 출력합니다