2. 아이디어

• 공백을 기준으로 입력을 받지 않아서, StringTokenzier 활용은 어렵다. ->** charAt 함수를 활용하고, -'0' 연산으로 int로 바꾸어 준다.**

• 예제 출력을 처음 보고 당황했지만, 이해하고 나니 어렵지 않았다.

  인접한 4개의 칸이 모두 같은 숫자이면, 해당 숫자로 표현한다.

  -> 해당 숫자를 StringBuilder를 활용해서 이어붙여야겠다!

• 분할 정복에서 나오는 '작은문제'에 해당하는 답을 ( )로 감싸 주면 된다.

  함수가 호출되는 시점에 유념해서 괄호를 열고 닫아준다.

3. 코드

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

public class Main {
    public static int[][] map;
    public static int one;
    public static int zero;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {

            String str = bf.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = str.charAt(j)-'0';
            }
        }

        divide(0, 0, N);
        System.out.println(sb);
    }

    public static void divide(int row, int col, int size) {

        if(colorCheck(row, col, size)) {
            sb.append(map[row][col]);

            return;
        }

        int newSize = size/2;

        sb.append('(');
        divide(row, col, newSize); // 2사분면
        divide(row, col+newSize, newSize); // 1사분면
        divide(row+newSize, col, newSize); // 3사분면
        divide(row+newSize, col+newSize, newSize); // 4사분면
        sb.append(')');
    }

    public static boolean colorCheck(int row, int col, int size) {
        int color = map[row][col]; // 시작점(원점)의 색

        for(int i=row; i<row+size; i++) {
            for (int j = col; j < col+size; j++) {
                if(map[i][j]!=color) return false; // 시작점의 색이 무엇이든, 같지 않다면 false
            }
        }

        return true;
    }

}

4. 느낀점

• 문자열 입출력 받기와 StringBuilder 활용을 연습해볼 수 있어서 좋았다.

• 비슷한 유형으로 한 문제 씩 반복해서 풀다보니.. 분할정복 분할정복 완료 ^_^;

2. 아이디어

색종이 만들기 문제와 상당히 유사하다. (대부분의 코드를 재사용할 수 있었다.)

• 차이점으로는 체크해야 할 변수가 blue white 2개에서, -1, 0 , 1로 3개가 되었다.

• 쪼개는 단위가 절반이 아니라 3분의 1씩 쪼갠다. (newSize = size/3)

  따라서 색종이 만들기 문제에서는 1, 2, 3, 4분면 개념으로 나누어 Divide 함수를 호출 했다면,

  이 문제에서는 키패드와 같이 9분할 개념으로 접근해서 함수를 호출해주기만 하면 된다.

3. 코드

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

public class Main {
    public static int[][] map;
    public static int one;
    public static int zero;
    public static int minus;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        map = new int[N][N];
        StringTokenizer st;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        divide(0, 0, N);
        System.out.println(minus);
        System.out.println(zero);
        System.out.println(one);
    }

    public static void divide(int row, int col, int size) {
        if(colorCheck(row, col, size)) {
            if(map[row][col]==0) zero++;

            else if(map[row][col]==1) one++;

            else minus++;

            return;
        }

        int newSize = size/3;

        divide(row, col, newSize); // 키패드 1 위치
        divide(row, col+newSize, newSize); // 키패드 2 위치
        divide(row, col+2*newSize, newSize); // 키패드 3 위치

        divide(row+newSize, col, newSize); // 키패드 4 위치
        divide(row+newSize, col+newSize, newSize); // 키패드 5 위치
        divide(row+newSize, col+2*newSize, newSize); // 키패드 6 위치

        divide(row+2*newSize, col, newSize); // 키패드 7 위치
        divide(row+2*newSize, col+newSize, newSize); // 키패드 8 위치
        divide(row+2*newSize, col+2*newSize, newSize); // 키패드 9 위치

    }

    public static boolean colorCheck(int row, int col, int size) {
        int color = map[row][col]; // 시작점(원점)의 색

        for(int i=row; i<row+size; i++) {
            for (int j = col; j < col+size; j++) {
                if(map[i][j]!=color) return false; // 시작점의 색이 무엇이든, 같지 않다면 false
            }
        }

        return true;
    }

}

4. 느낀점

• 하나의 알고리즘 문제를 풀 때, 비슷한 유형의 문제들을 풀어보는 것이 확실히 좋은 것 같다.

• 분할 정복과 재귀함수 활용에 대해 익숙해져 간다!

2. 아이디어

* 분할 정복 알고리즘

① 큰 문제를 작은 문제로 분할하고 (Divide) ② 해당 작은 문제들을 풀고(Conquer) ③ 작은 문제들의 풀이 결과를 합한다.

• 음.. 복잡한 아이디어는 아니기 때문에 무슨 말인지는 알겠다. 근데 위의 내용만으로는 추상적이라 실제 코드 작성은 어렵다. 조금 더 구체화해서 생각해보았다!

1) 큰 문제를 가장 작은 단위의 문제까지 쪼개야 한다 -> 재귀호출 2) 어디까지 쪼갤지 알아야 한다 -> 가장 작은 문제 단위를 파악 할 수 있어야 한다.

위의의 두가지 아이디어로 문제를 접근해보자.

• 분할 정복 관련해서 몇가지 문제를 풀어보았는데, 문제 상황이 대부분 2차원 배열이었다. 아마 문제를 처음 보면 DFS/BFS인가?라는 생각을 먼저 할 것 같다.
  • 그렇다면, 분할 정복임을 어떻게 캐치할 수 있을까?

차이점? 특징?을 나름대로 생각해보았다. 정리하고 보니 꽤나 차이가 나는 것 같다.

1) 특정 행위를 계속해서 반복한다. (한 칸 씩 이동하면서 경로를 탐색하는 관점이 아님) 2) 1번에서의 반복 행위는 보통 나눗셈이 진행된다. -> 대부분의 입력 값이나 조건이 지수 형태를 띄고 있다. (나누어 떨어지도록)

3. 코드

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

public class Main {
    public static int[][] map;
    public static int white;
    public static int blue;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        map = new int[N][N];
        StringTokenizer st;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        divide(0, 0, N);
        System.out.println(white);
        System.out.println(blue);
    }

    public static void divide(int row, int col, int size) {
        if(colorCheck(row, col, size)) {
            if(map[row][col]==0) white++;
            else blue++;

            return;
        }

        int newSize = size/2;

        divide(row, col, newSize); // 2사분면
        divide(row, col+newSize, newSize); // 1사분면
        divide(row+newSize, col, newSize); // 3사분면
        divide(row+newSize, col+newSize, newSize); // 4사분면

    }

    public static boolean colorCheck(int row, int col, int size) {
        int color = map[row][col]; // 시작점(원점)의 색

        for(int i=row; i<row+size; i++) {
            for (int j = col; j < col+size; j++) {
                if(map[i][j]!=color) return false; // 시작점의 색이 무엇이든, 같지 않다면 false
            }
        }

        return true;
    }

}

4. 느낀점

• 여러 알고리즘을 공부하다 보니, 이제는 받아들이는 속도가 좀 빨라졌다.

• 재귀호출의 개념과 활용을 잘 할 수 있다면 어렵지 않게 풀 수 있는 개념 같다.

2. 아이디어

• 2579번 계단 오르기 문제와 상당히 유사하다. https://velog.io/@dev_su_noh/%EB%B0%B1%EC%A4%80-JAVA-2156%EB%B2%88-%ED%8F%AC%EB%8F%84%EC%A3%BC-%EC%8B%9C%EC%8B%9D

• 큰 차이점은, 계단은 1칸 혹은 2칸으로 제한되어 있었지만, 해당 문제는 그러한 조건이 없다.

• 바로 왼쪽(i-1)의 포도주를 마신 경우 / 마시지 않은 경우로 나누어 생각한다. 마시지 않은 경우에는, i-2까지의 경우 중 최선을 선택해야 한다.

3. 코드

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[] dp = new int[N + 1];
        int[] arr = new int[N + 1];


        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // index = 0 은 시작점
        dp[1] = arr[1];

        if (N > 1) {
            dp[2] = arr[1] + arr[2];
        }

        for (int i = 3; i <= N; i++) {
            dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]));

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

    }

}

4. 느낀점

• 계단 오르기 문제를 열심히 풀었더니 쉬웠다!

• DP 문제들은 index 및 dp/arr 배열 활용 로직을 고민하는 것이 중요하다. (역시 경우의 수를 몇가지 적어보는 것이 아주 좋다.)

2. 아이디어

• 제약조건 1) 마지막 계단은 무조건 밟아야 한다. 2) 세 계단을 연속으로 밟을 수 없다. 3) 계단은 1칸 혹은 2칸 씩 올라갈 수 있다.

• • 당연하게도 계단의 순서가 중요하니, 정렬을 하면 안된다 ㅎㅎ;

• 2)와 3)번 조건을 고려하며 몇가지 생각을 하다가 다이나믹 프로그래밍 개념 이해가 더욱 생겼다. (문제를 쪼개어 작은 문제부터 해결한다는게 무슨 뜻인지 알겠다는?) 아래는 사고의 흐름이다..!

1. 마지막 계단을 밟기 위해서는 D-F (2칸) 혹은 E-F(1칸)이다. D-E-F는 불가능하다.

2. "다음 계단을 몇 칸 올라가는 것이 이득인지"를 경우의 수 나열(도착지까지 가보기) 없이 판단할 수 있나? : 불가능하다. 다음 계단에 대한 의사결정은 그 이후에 나오는 계단을 고려해야 한다.

ex) " 현 위치 / 10 / 20 " 상황이라고 가정해보자.

당연히 두 칸을 올라가서 20에 도착 하는 것이 이득으로 보인다.

하지만 알고보니 계단의 점수가 현위치 / 10 / 20 / 100 / 1,000이었다면?

난 이미 20까지 올라왔기 때문에 "현 위치 - 20 - 1000"이 최고 득점이다. (총합 1,020) (100으로 가면 1,000을 얻지 못한다!)

하지만 "현 위치 - 10 - 100 - 1,000"이 더 좋은 경우의 수 이다. (총합 1,110)

해당 예시에서도, 이후에 오는 숫자의 절댓값과 순서에 따라 경로의 최선은 달라질 것이다.

이렇듯 이후의 숫자를 의사결정에 참고하지 않으면(경우의 수를 모두 나열해보지 않으면) 다음 계단을 몇 칸 가는 것이 이득인지 판단할 수 없다.

• 다음 계단을 예측할 수는 없지만, 현재 위치까지 오는 경로의 최선은 알 수 있다!

• 현 위치를 일종의 "도착지"라고 생각하고, 각각의 출발지~현위치(작은 단위의 문제)까지 오는 제일 좋은 값을 저장(Memoization)하고 활용한다.

"다음 (미래) 선택을 무엇으로 하느냐" 관점이 아니라, "현재 상태에 도달하기까지 과거의 경우" 중, 최선을 찾는다.

• 나름대로 정리한 DP 문제의 접근 방식이다. 타인에게는 전달이 잘 안될 수도 있고.. 엄밀하지 않을 수도 있지만, 굵은 글씨의 부분이 흔히 말하는 "작은 문제"라고 생각하면 될 것 같다.

3. 코드

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[] dp = new int[N + 1];
        int[] arr = new int[N + 1];


        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // index = 0 은 시작점
        dp[1] = arr[1];

        if (N >= 2) {
            dp[2] = arr[1] + arr[2];
        }


        for (int i = 3; i <= N; i++) {
            dp[i] = Math.max(dp[i - 2] , dp[i - 3] + arr[i - 1]) + arr[i];
        }

        System.out.println(dp[N]);

    }

}

4. 느낀점

• "가장 긴 감소하는 부분수열" 문제 풀 때보다 DP 개념 및 활용에 대한 이해가 생겼다. https://velog.io/@dev_su_noh/백준-JAVA-11722번-가장-긴-감소하는-부분수열

• 평소에 문제를 접근하는 방식과는 관점이 달라서 재미있었다!

2. 아이디어

• 처음에는 정렬을 해버렸는데.. 수열의 위치 자체가 의미 있는 값이기 때문에 현재 나열된 순서대로 해결해야 한다.

• 현재 인덱스(i)의 값까지 감소하는 부분 수열의 길이를 정답 배열(i)에 담아두고 비교한다.

2-1. 다이나믹 프로그래밍

• 문제를 더 작은 단위로 쪼개어, 작은 단계의 답을 활용하는 알고리즘 작은 단위의 결과를 저장할 배열 등을 미리 만들어 저장해둔다.

• Top - Down(재귀호출), Bottom-Up(반복문) 두 가지 접근이 존재한다.

3. 코드

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

public class Main{

public static void main(String[] args) throws NumberFormatException, IOException {

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

        int n = Integer.parseInt(reader.readLine());

        int[] arr = new int[n+1];
        int[] cnt = new int[n+1];

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

        for (int i=1; i<=n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int ans = 0;

        for (int i=1; i<=n; i++) {
            cnt[i] = 1;
            for (int j=1; j<i; j++) {
                if (arr[j] > arr[i]) {
                    cnt[i] = Math.max(cnt[i], cnt[j] + 1);
                }
            }
            ans = Math.max(ans, cnt[i]);
        }

        System.out.println(ans);

    }

}

4. 느낀점

• 사실 알고리즘 개념을 봐서는 딱히 와닿지는 않았다... ㅎㅎ; 몇가지 문제를 풀어보니 이런 상황이구나~ 싶긴 했다.

• 정답을 위한 배열을 만들어두고, 재귀 혹은 반복문을 활용해서 이전의 값들과 비교한다! 라는 문제풀이 도구를 하나 얻었다.

2. 아이디어

• 검문에 소요되는 시간과, 공백 시간, 최초 소가 도착까지의 시간을 합한다.

• 앞의 소가 검문을 하고 있어서 대기하는 시간은 무시할 수 있다.

  

3. 코드

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

public class Main{

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

         int N = Integer.parseInt(bf.readLine());
         int[][] arr = new int[N][2];

         for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken()); //도착시간
            arr[i][1] = Integer.parseInt(st.nextToken()); // 검문 소요시간
        }

         Arrays.sort(arr, (o1, o2) -> {
                return o1[0]-o2[0]; // 첫번째 숫자 기준 오름차순
         });

         int time = 0; // 정답에 쓰일 변수

        time = time + arr[0][0];

        for(int i=0; i<N; i++) {
            time = time + arr[i][1]; // 검문소요시간 합

            if(i<N-1 && arr[i+1][0]>time) { // 다음 소가 도착 안했을 경우에 생기는 비는 시간, 맨 마지막 도착 소는 제외
                time = time + (arr[i+1][0]-time);
            }
        }

        System.out.println(time);
    }
}

4. 느낀점

• key로 도착시간, value를 검문 시간으로 Map을 활용하려 했으나, key 값은 중복이 되지 않기 때문에 동시에 도착하는 경우를 계산할 수 없었다.

• 어떤 자료구조를 쓰는게 좋을지 머리를 쓰다.. 2차원 배열로 풀어둔 코드를 보고 아하! 했다. 이번 기회로 또 하나 배워간다~

2. 아이디어

• 손상 여부, 여분 여부를 나타내는 Boolean 배열을 2개 선언한다.

• 카약을 하나 더 가져왔더라도, 본인 팀의 카약이 손상되면 본인 팀을 수리한다. 이러한 경우에는 카약을 가져오지 않은 팀과 동일하다.

• 배열의 좌측부터 카약의 손상여부를 확인한다. 만약 카약이 손상되었다면 좌,우의 팀이 여분의 카약이 있는지 확인한다.

• 좌,우의 팀 모두가 여분 카약을 가져왔다면 좌측 팀의 카약을 사용한다. 좌측부터 손상여부를 확인하고 있기 때문에, 좌측 팀의 여분 카약은 현재 체크 중인 팀 외에는 어차피 사용 할 수 없기 때문이다.

3. 코드

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

public class BOJ_4_2891{

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());
        boolean[] arr = new boolean[N];

        st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < S; i++) {
            int s = Integer.parseInt(st.nextToken());
            arr[s-1]=true;
        }    // 손상된 팀은 true로 표현

        st = new StringTokenizer(bf.readLine());
        boolean[] rent = new boolean[N]; // 빌려줄 수 있는지 상태 관리 

        for (int i = 0; i < R; i++) {
            int r = Integer.parseInt(st.nextToken());
            rent[r-1]=true;
        }    // 여분을 가져온 팀은 true

        int ans = 0; // 출발 할 수 없는 팀 수

        // 자기꺼 먼저 다 수리하기
        for(int i=0; i<N; i++) {
            if(arr[i]&&rent[i]) {
                arr[i]=false;
                rent[i]=false;
            }
        }

        // 첫번째 팀이 손상된 경우
        if(arr[0]) {
            if(rent[1]) rent[1]=false;
            else ans++;
        }

        // 중간 팀이 손상된 경우
        for(int i=1; i<N-1; i++) {
            if(arr[i]) {
                if(rent[i-1]) continue;
                else if(rent[i+1]) rent[i+1]=false;
                else ans++;
            }
        }

        // 마지막 팀이 손상된 경우

        if(arr[N-1]) {
            if(rent[N-2]) rent[N-2]=false;
            else ans++;
        }

        System.out.println(ans);
    }
}

4. 느낀점

• 문제의 테스트 케이스 외에 본인 팀의 카약이 손상되었지만, 여분이 있어서 스스로 수리하는 경우를 생각해야 한다.

• 처음에는 -1, 0, 1로 각각 팀의 상태를 표현하려 했으나, boolean으로 표현하는 것이 코드 작성이나 생각하기에 더 편했다.

2. 아이디어

• (입장순서 -1)원은 어느 손님이 몇번째로 입장하는지와는 무관하다. 어차피 빼는 크기 총량은 동일하다

• 음수가 되어 팁을 주지 않는 경우의 절댓값을 최대로 만든다. (어차피 음수가 되어 팁을 주지 않는다면, 애초에 팁을 적게 주려고 생각했던 사람을 가장 후 순위에 배치한다.)

• 입력 값의 크기 때문에 출력 자료형은 int가 아니라 long으로 선언해야 한다.

3. 코드

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

public class BOJ_4_1758{

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int[] arr = new int[N+1];
        for(int i=1; i<N+1; i++) {
            arr[i]=Integer.parseInt(bf.readLine());
        }

        long ans = 0;
        Arrays.sort(arr); // 오름차순 정렬, 역순으로 체크해보자

        for (int i = N; i > 0; i--) {

            // 맨 뒤의 값(arr[N+1]이 가장 먼저 입장(1번), 해당 인덱스의 입장 순서는(N+1)-i
            if(arr[i]-(N+1-i-1)>0) { //음수가 아닌 경우에만 합한다.                
                ans= ans + arr[i]-(N+1-i-1);
            }

        }
        System.out.println(ans);
    }
}

4. 느낀점

• 그리디 알고리즘 풀이 시, 반례나 자료형에 대해 고민해보자.

2. 아이디어

• 본인의 등수를 낮게 예상한 사람일 수록 실제 등수를 작게 매기는 것이 불만도가 최소이다.

• 예상 등수를 오름차순으로 정렬하고, 실제 등수(1, 2, 3...)를 빼서 절댓값을 합한다.

• 인물과 등수를 매칭해서 등수에 관한 수열을 출력하는 것이 아니라, 불만도 총합을 출력하는 것이기 때문에 단순히 정렬을 해도 무관하다.

• 입력 값의 범위 때문에 int가 아니라 long을 사용해야 한다.

  3. 코드

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

public class BOJ_4_2012{

public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(bf.readLine());
    int[] arr = new int[N+1];
    for(int i=1; i<N+1; i++) {
        arr[i]=Integer.parseInt(bf.readLine());
    }

    long ans = 0;
    Arrays.sort(arr); // 오름차순 정렬, 역순으로 체크해보자

    for (int i = 1; i < N+1; i++) {
        ans = ans + Math.abs(arr[i]-i);
    }
    System.out.println(ans);
}

}

```

4. 느낀점

• long 자료형 활용에 대해 배웠다. 단순히 기계적으로 int라고 선언하지 말 것!

• https://velog.io/@dev_su_noh/백준-1758번-알바생-강호 이 문제를 풀고나서 푸니까 금방 풀렸다! 띠용,, 했음

2. 아이디어

• 문자열을 잘라서 출력하기만 하면 되는 간단한 문제이지만, StringTokenizer 활용을 연습해보려고 풀어보았다.

• 처음에는 자른 문자를 배열에 담아야 하나 싶었는데, 그냥 바로 출력하면 되는 문제이다.

• subString과 charAt, StringTokenizer와 split 등 다양한 문자열 분리 함수로 풀 수 있다.

3. 코드

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

public class Main{

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bf.readLine());

        for(int i=0; i<T; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());

            int R = Integer.parseInt(st.nextToken());

            String str = st.nextToken();

            for (int j = 0; j < str.length(); j++) {
                for (int k = 0; k < R; k++) {
                    System.out.print(str.charAt(j));
                }
            }
            System.out.println();
        }

    }
}

4. 느낀점

• 3중 for문이 나와서 이게 맞나..? 싶었다. 하지만 Tese Case 수, 반복 횟수, 글자 길이 값이 작게 제한되어 있어서, 최대 시간복잡도는 1000 * 20 *8로 예상되어 괜찮을 것 같았다.

2. 아이디어

• 처음에는 문자열을 한자리 씩 쪼개고, 배열에 담아서 찾아보고자 했다. 주어진 문자열을 줄 세우는 모든 경우의 수는 N!이니 해볼만 하다는 생각이 들었기 때문이다. ('같은 것이 있는 순열'일 수 있으므로 엄밀히는 N!이 아닐 수 있겠지만 어차피 모든 경우를 다 탐색해볼 것이니..)

• 그러나 위의 접근으로 N!개의 모든 문자열을 구하는 것에 실패하였고.. 각 알파벳의 등장 횟수가 홀수인가, 짝수인가, 홀수인 것이 몇개인가를 기준으로 생각하는 아이디어에 만감이 교차했다..^^;

3. 코드

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

public class Main{
    static int[] alphabet = new int[26];    //알파벳 개수 저장 배열
    static StringBuilder sb = new StringBuilder();    //결과 저장할 StringBuilder
    static StringBuilder front = new StringBuilder();
    static StringBuilder end = new StringBuilder();

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

        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String name = br.readLine();
        boolean check = false;    //팰린드롬 만들 수 있는지 확인 변수
        int oddCheck = 0;        //알파벳 홀수인 개수
        char mid = '0';
        //알파벳 개수를 구하기
        for(int i=0;i<name.length();i++)
            alphabet[name.charAt(i) - 65]++;

        //팰린드롬 만들기
        for(int i=0;i< alphabet.length;i++){
            if(alphabet[i] != 0 && alphabet[i]%2 == 1){
                if(oddCheck==0){    //홀수가 1개가 될 때
                    oddCheck++;
                    mid = (char)('A' + i);    //mid구하기
                }else{    //홀수가 2개가 될 때
                    //팰린드롬 만들지 못하기 때문에 "I'm Sorry Hansoo"를 저장
                    sb = new StringBuilder("I'm Sorry Hansoo");
                    check = true;
                    break;
                }
            }
            //"개수 ÷ 2"만큼 front, end 구성 
            for(int j=0;j<alphabet[i]/2;j++){
                front.append((char)('A' + i));
                end.insert(0, (char)('A' + i));
            }
        }
        if(!check){        //팰린드롬 만들었을 때
            if(mid == '0')    //홀수 개수가 0개일 때
                sb.append(front).append(end);    //front + end
            else        //홀수 개수가 1개일 때
                sb.append(front).append(mid).append(end);    //front + mid + end
        }

        bw.write(sb.toString());        //팰린드롬 BufferedWriter 저장
        bw.flush();        //결과 출력
        bw.close();
        br.close();
    }
}

4. 느낀점

• 어떤 방식으로 풀 것인지.. 접근하는 관점의 중요성에 대해 다시 한번 느꼈다.

• 때로는 하나씩 다 찾아보는 것이 유리할 수도 있지만, 문제 조건에 따라 기준/로직을 세워서 모든 케이스를 커버할 수 있다면 해당 방법이 더 깔끔하다.

2. 아이디어

• 처음에는 몫과 나머지 연산을 통해 풀어보려 했다만, 앞자리의 0에 대한 처리가 필요하고.. 숫자의 자리수 별로 케이스를 어떻게 나누어야 할지 감이 잘 오지 않았다. 너무 복잡할 것 같아서 다른 방법을 고민하기로 했다. (이렇게 푼 사람이 있다면 한번 보고 싶다 ㅠ.ㅠ)

• 숫자를 1씩 증가시키면서 하나씩 다 검사해보는 것도 시간복잡도가 크지 않을 것 같아서 시도해보았다.

3. 코드

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

public class BOJ_3_4096 {
    public static void main(String[] args) throws IOException  {

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

        while (true) {
            String s = br.readLine();
            if (s.equals("0")) break; // 마지막 입력 0

            int len = s.length(); // 숫자의 자리 수
            int num = Integer.parseInt(s); // 00012 -> 12
            int cnt = 0; // 더한 횟수

            while (!isPalindrome(len, num+(cnt++))) {}

            sb.append(cnt-1).append('\n');
        }

        System.out.print(sb);

    }

    // 문자열을 함수 인수로 넘기자니, ++연산을 해야해서 정수로 변환
    private static boolean isPalindrome(int len, int num) {

        String str = String.valueOf(num);
        StringBuilder sb = new StringBuilder();
        // 앞에 0 추가 ex 000
        for (int i = 0; i < len-str.length(); i++) {
            sb.append('0');
        }
        // 뒤에 숫자 추가 ex 00012
        sb.append(str);
        str = sb.toString();

        for(int i=0; i<len/2; i++) {            
            if(str.charAt(i)!=str.charAt(len-i-1)) return false;
        }
        return true;
    }
}

4. 느낀점

• String에서 Int, 다시 String으로 변환하는 과정에서 앞자리의 0 (ex. 00012)을 관리하는 아이디어와 방식이 재미있었다.

• 팰린드롬에 대해 익숙해져간다!

2. 아이디어

• 확장자의 종류(txt, jpg, etc..)와 길이가 다양하다. 따라서 '.'을 기준으로 SubString을 사용해야겠다.

• 처음에는 배열을 활용해서 정렬을 하려 했으나, 확장자 별 숫자를 count 하기 위해서는 map이 더욱 적합하다.

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;

public class BOJ_3_20291 {
    public static void main(String[] args) throws IOException  {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken());
        Map<String, Integer> map = new HashMap<>();

        for(int i=0; i<N; i++) {
            String name = bf.readLine();
            String file = name.substring(name.indexOf(".")+1); 
             map.put(file, map.getOrDefault(file, 0)+1);
        }

        Set<String> strings = map.keySet();

        List<String> list = new ArrayList<>(strings);

        Collections.sort(list);

        for(int i=0; i<list.size(); i++){
            System.out.println(list.get(i)+" "+map.get(list.get(i)));
        }
    }
}

4. 느낀점

• 문자열의 인덱스가 아니라 '.'과 같이 특정 문자를 기준으로 자르는 연습을 해보았다.

• map을 활용하여 값을 넣고, keySet을 활용하여 key 값을 얻는 방식을 익혔다.

2. 아이디어

• 입력 받은 문자열(번호판)의 종류나 순서, 길이가 동적이라 배열과 Index를 활용하긴 어려울 것 같았다. 따라서 Map을 활용하여 Key로 번호판, Value로 순서로 값을 관리하는 것이 좋겠다.

• ** 단순히 나오는 순서만 고려한다면, 문제에 기입된 테스트 케이스 외에 반례를 통과할 수 없었다.** (1명을 추월했으나, 다른 1명에게 추월당해서 결과적으로 나오는 순서는 똑같은 경우)

3. 코드

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

public class BOJ_3_2002 {
    public static void main(String[] args) throws IOException  {

        // 문자열 여러개에 대해 값 비교, 숫자 카운트 등을 하려하면, 인덱스를 알기 어렵거나 동적인 경우가 많다 -> 맵을 써보자

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());

        HashMap<String,Integer> ys = new HashMap<>();
        for (int i = 0; i < N; i++) {
            ys.put(bf.readLine(), i);
        }

        int[] arr = new int[N];

        // 나간 순서대로 불러서 배열에 담음
        for (int i = 0; i < N; i++) {
            arr[i]=ys.get(bf.readLine());
        }

        int count = 0;
        // 추월을 안했으면 오름차순으로 정렬이 되어 있어야 함
        for (int i = 0; i < N-1; i++) {
            for (int j = i+1; j < N; j++) {
                if(arr[i]>arr[j]) {
                    count++;
                    break;
                }
            }
        }

        System.out.println(count);
    }

}

4. 느낀점

• Map 자료구조에 어느정도 익숙해진 것 같다. 문제를 보고 떠올릴 수 있을 정도가 되었다.

• 주어져 있는 Test Case 통과만 고려하지 말자는 교훈을 얻었다 ^_^;

2. 아이디어

• 우선순위 큐를 활용한다

2-1 우선순위 큐

• 큐(Queue)는 First in-First Out 구조로, 어떤 부가적인 조건 없이 먼저 들어온 데이터가 먼저 나가는 구조이다. 유통기한에 민감한 우유 판매와 같은 형태.

• 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

3. 코드

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

public class BOJ_2_1927 {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> minQueue = new PriorityQueue<Integer>(); // 낮은 숫자가 우선순위 높은게 기본 기준

        for (int i = 0; i < N; i++) {
           int x = Integer.parseInt(br.readLine());

            if (x>0) { // x가 자연수면 배열에 추가하는 연산
                minQueue.offer(x);
            } else { // x가 0인데 배열이 비어있으면 0 출력
                if (minQueue.isEmpty()) {
                    System.out.println(0);                    
                }
                else{ // x가 0이면 배열 값 중에 최솟값 출력
                    System.out.println(minQueue.poll());
                }
            }
        }

    }
}

4. 느낀점

• 우선순위 큐의 기본 설정 값이 최솟값이므로, 별도의 Comparator 설정이 없어도 풀 수 있었다.

• 해당 시리즈의 최대 힙 등의 문제를 풀기 위해서는 우선순위 기준에 대해 별도 설정이 필요하겠다.

2. 아이디어

• 문제의 조건을 그대로 구현해보자.

• Queue의 가장 앞에 있는 문서의 중요도를 확인한다. 나머지 문서들과 비교하여 현재 문서보다 중요도가 높은 문서가 하나라도 있다면 이 문서를 인쇄하지 않고, Queue의 가장 뒤에 재배치한다. 비교 결과 현재 맨 앞의 문서가 가장 높은 중요도를 가진다면 바로 인쇄 한다.

3. 코드

import java.util.LinkedList;
import java.util.Scanner;

public class BOJ_2_1966 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int T = sc.nextInt();    // 테스트 케이스 

        while (T-- > 0) {

            int N = sc.nextInt();
            int M = sc.nextInt();

            LinkedList<int[]> que = new LinkedList<>();    // Queue로 활용 할 연결리스트

            for (int i = 0; i < N; i++) {
                // {초기 위치, 중요도}
                que.offer(new int[] { i, sc.nextInt() });
            }

            int count = 0;

            while (!que.isEmpty()) {    // 한 케이스에 대한 반복문

                int[] front = que.poll();    // 가장 첫 원소
                boolean isMax = true;    // front 원소가 가장 큰 원소인지를 판단하는 변수

                // 큐에 남아있는 원소들과 중요도를 비교 
                for(int i = 0; i < que.size(); i++) {

                    // 처음 뽑은 원소보다 큐에 있는 i번째 원소가 중요도가 클 경우 
                    if(front[1] < que.get(i)[1]) {

                        // 뽑은 원소 및 i 이전의 원소들을 뒤로 보낸다.
                        que.offer(front);
                        for(int j = 0; j < i; j++) {
                            que.offer(que.poll());
                        }

                        // front원소가 가장 큰 원소가 아니였으므로 false를 하고 탐색을 마침
                        isMax = false;
                        break;
                    }
                }

                // front 원소가 가장 큰 원소가 아니였으므로 다음 반복문으로 넘어감
                if(isMax == false) {
                    continue;
                }

                // front 원소가 가장 큰 원소였으므로 해당 원소는 출력해야하는 문서다.
                count++;
                if(front[0] == M) {    // 찾고자 하는 문서라면 해당 테스트케이스 종료
                    break;
                }

            }

            sb.append(count).append('\n');

        }
        System.out.println(sb);
    }

}

4. 느낀점

• 큐 자료구조 활용에 대해 익힐 수 있었다.

2. 아이디어

• 쉽게 생각하면 N^N개의 수 중에, N번 째로 큰 수를 구하는 것이다.
• 입력되는 수의 크기는 -10억 ~ 10억이지만, 수의 개수는 1500^2이므로 생각보다 연산 시간은 얼마 안걸리지 않을까 생각했다.

3. 코드

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

public class BOJ_2_2075 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int[] arr = new int[N*N];
        int idx=0;

        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            for(int j=0; j<N; j++) {                
                arr[idx++] = Integer.parseInt(st.nextToken());
            }
        }
        //System.out.println(Arrays.toString(arr));
        //[12, 7, 9, 15, 5, 13, 8, 11, 19, 6, 21, 10, 26, 31, 16, 48, 14, 28, 35, 25, 52, 20, 32, 41, 49]
        Arrays.sort(arr);
        //System.out.println(Arrays.toString(arr));
        // [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 19, 20, 21, 25, 26, 28, 31, 32, 35, 41, 48, 49, 52]
        System.out.println(arr[N*N-N]);
    }
}

4. 느낀점

• 해당 문제는 우선순위 큐를 쓰는 것이 보편적인 것 같다만, 떠오른 사고 과정대로 일단 풀어보았다.

2. 아이디어

• 괄호는 방향성이 있다. '(' 혹은 ')'
• 닫히기 위해서는 괄호의 수가 짝수어야 한다.
• 짝수개이더라도, ')'가 '('보다 먼저 오면 안된다.

3. 코드

import java.util.Scanner;

public class BOJ_2_9012 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        String[] arr = new String[T];

        for(int i=0; i<T; i++) {
            arr[i]=sc.next();

            boolean ans = true; // ( 가 오지 않았는데 ) 괄호가 먼저 오는 경우는 무조건 NO
            int count=0;

            for (int j = 0; j < arr[i].length(); j++) {
                String str = arr[i];
                char sub = str.charAt(j);

                if(sub=='(') count++;
                else if(sub==')') count--;

                if(count<0) ans=false;

            }
            if(count==0 && ans) System.out.println("YES");
            else System.out.println("NO");
        }

    }
}

4. 느낀점

• 배열과 홀, 짝수 개념만을 이용해서 풀었으나 스터디 조원들은 스택을 활용하여 풀었다.

• 스택과 외의 자료구조에도 익숙해져서, 풀이 과정에서 여러 자료구조를 고려할 수 있도록 해야겠다.

2. 아이디어

• 위치가 같으면 찾았다 : (보폭) D의 약수와 배수 개념을 활용해야겠다.
• 나눗셈의 편의를 위해 원점으로 평행이동 (-S) 시키고, 음수 처리를 위해 절댓값을 취한다.

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_1_17087 {
    public static void main(String[] args) throws IOException  {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); 
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken()); 
        int[] arr = new int[N];
        st = new StringTokenizer(bf.readLine());

        for(int i =0; i<N; i++) {
            arr[i]= Integer.parseInt(st.nextToken());
            arr[i]=Math.abs(arr[i]-S);
        }

        int D = arr[0];

        for (int i = 0; i < N; i++) {            
             D = findD(D, arr[i]);
        }

        System.out.println(D);

    }

    public static int findD(int a, int b){
        if(a%b==0) return b;
        return findD(b,a%b);
    }

}

4. 느낀점

• 수학적으로 사고하는 느낌이 들어서 재미있었다.

• 모호할 땐 직접 그림을 그려보는 것이 좋다!