돌 그룹 시간 제한 메모리 제한
2 초 512 MB
문제 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.

크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

입력 첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)

출력 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.

풀이

시간 복잡도

• 그룹 하나당 가질수 있는 경우수는 A+B+C
• 전체 돌 그룹 3개가 모두 다르다면 A != B != C 3가지 경우를 모두 탐색한다.
• 만약 3가지 경우를 모두 본다면 N^3 이되서 1500^3 이 된다.
• 메모리의 경우 1500^3 이 넘는다.
• 여기서 총합은 변하지 않는다 라는 사실을 활용하면 N^2 로 줄일 수 있다.
• 값 두개가 변하면 나머지값을 알수 있다 라는 사실을 이용할텐데, A, B 를 알면 C 를 알 수 있기 떄문에 한 그룹이 가질수 있는 값 M = A+B+C check[M][M][M] -> check[M][M] 로 상태에 대한 체크를 줄일 수 있다.
• 가능성만 구하면 되기때문에 값의 위치는 상관없이 중복 체크를 하면된다
• 또한 전체가 3으로 나눠 떨어지지 않으면 무조건 0 이라는 사실을 활용해 입력에 대한 가지 치기가 가능하다.
• 시간 복잡도 O(N^2), 공간 복잡도 O(M^2) 로 상태 BFS 로 풀이 가능

  코드

  package gold.BJ12886GroupSton;
  

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

class State { int a; int b; int c;

public State(int a, int b, int c) {
    this.a = a;
    this.b = b;
    this.c = c;
}

public boolean isSame() {
    return a == b && b == c;
}

}

public class Main { static boolean[][] check; // X < Y 일때 X + X < Y성립? yes

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int A = Integer.parseInt(st.nextToken());
    int B = Integer.parseInt(st.nextToken());
    int C = Integer.parseInt(st.nextToken());
    check = new boolean[A + B + C + 1][A + B + C + 1]; // 조합의 중복을 체크 해야한다. 총합은 같으니 마지막하나는 몰라도 된다 2차원으로 가능
    if ((A + B + C) % 3 != 0) {
        System.out.println(0);
        return;
    }
    System.out.println(bfs(A, B, C));


}

public static int bfs(int a, int b, int c) {

    Queue<State> q = new ArrayDeque<>();
    q.add(new State(a, b, c));
    while (!q.isEmpty()) {
        State curState = q.poll();
        if (curState.isSame()) {
            return 1;
        }

        if (curState.a != curState.b) {
            int[] ab = {curState.a, curState.b};
            int[] calAB = cal(ab);
            State nextState = new State(calAB[0], calAB[1], curState.c);
            if (calAB[0] >= 0 && calAB[1] >= 0 && !check[calAB[0]][calAB[1]]) {
                check[calAB[0]][calAB[1]] = true;
                q.add(nextState);

            }
        }
        if (curState.b != curState.c) {
            int[] bc = {curState.b, curState.c};
            int[] calBC = cal(bc);
            State nextState = new State(curState.a, calBC[0], calBC[1]);
            if (calBC[0] > 0 && calBC[1] > 0 && !check[calBC[0]][calBC[1]]) {
                check[calBC[0]][calBC[1]] = true;
                q.add(nextState);
            }
        }
        if (curState.a != curState.c) {// 앞에서 체크를 해버리면?
            int[] ac = {curState.a, curState.c};
            int[] calAC = cal(ac);
            State nextState = new State(calAC[0], curState.b, calAC[1]);
            if (calAC[0] > 0 && calAC[1] > 0 && !check[calAC[0]][calAC[1]]) {
                check[calAC[0]][calAC[1]] = true;
                q.add(nextState);
            }
        }

    }

    return 0;
}

public static int[] cal(int[] input) {
    int[] res = {-1, -1};
    int x;
    int y;
    // 둘다 양수여야하는데..
    if (input[0] < input[1]) {// 첫번쨰가 작을때
        x = input[0];
        y = input[1];
        //, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.
        x += input[0];
        y -= input[0];
        res[0] = x;
        res[1] = y;
    } else { // 첫번째가 클때
        x = input[1];
        y = input[0];
        x += input[1];
        y -= input[1];
        res[1] = x;
        res[0] = y;

    }
    return res;

}

}

우선 insert 의 성능에 영향주는 요소 delete 의 성능에 영향주는 요소를 비교해보자

INSERT

• 로그 기록 (redo.rlog)

  • LOG AHEAD 기법으로 인해 항상 리두 로그를 기록하고 디스크에 기록한다.
  • insert 는 다이렉트 로딩 힌트를 사용해 데이터를 저장해 성능을 확보할수 있다.

• HWM BUMP UP

  • 데이터를 INSERT 테이블내 논리적 저장단위인 블록 을 새롭게 확보해야하는데 이때 HWM 기준으로 블록의 더 하위 저장단위인 EXTNT 가 저장되기 떄문에 HWM 가 이동한다 (뒤로) HWM 이동하는 작업은 고비용작업이기 때문에 성능에 영향을 주게 된다.
  • 즉 HWM 이 후진 해야 데이터 저장이 가능해진다.

• 인덱스 갯수

  • 인덱스가 이전에 존재 하고 있다면 인덱스를 추가하는 작업이진행된다.
  • 데이터 겟수만큼 인덱스 추가작업이 일어난다.
  • 인덱스는 순서를 유지해야하기 때문에 고비용의 작업이 일어난다.

• 롤백을 위한 로그기록 (undo.log)

  • 커밋의 ROLL BACK 수행할때 사용하는 undo.log 를 갱신하는 작업이 데이터 갯수만큼 일어난다
  • 변경전 데이터를 기록하는 방식으로 동작한다.

• 디스크 I/O

  • HWP BUMP UP 을 제외한 작업은 모두 디스크에서 일어난다.

DELETE

• HWM BUMP UP 를 제외하고 인서트와 동일하다.

성능은INSERT 보다 DELETE 가 더느리다

• 분명 성능에 영향을 주는 요소는 DELTE 가 더 적지만 동일한 데이터양에 대해선 DELETE 가 더느리다.
• undo 를 진행하면서 이전데이터를 기록하냐 안하냐 차이가 있기 떄문에 delete 가 더느림.
• insert 는 이전 데이터가 없기 떄문에 undo 에서 기억할데이터가 update, delete 보다 적다.
• undo 는 디스크 IO 기 떄문에 같은 디스크에 성능에서 이런 논리가 가능.

추가 질문

• update 와 delete 중 누가더 느릴까?
• 성능이 느린 delete 를 어떻게 하면 빠르게 할수 있을까?

참조

• dml 의 성능 고찰
• http://www.gurubee.net/lecture/2283
• update 가 더 비용을 발생시키다.
• http://www.gurubee.net/lecture/2283
• delete 와 update 성능 최적화
• https://dataonair.or.kr/db-tech-reference/d-story/data-story/?mod=document&uid=62944

https://softeer.ai/practice/info.do?idx=1&eid=577

요약

로봇은 명령어로 동작한다

A 는 2번 앞으로 이동 R 은 오르쪽으로 돌기 L 은 왼쪽으로 돌기 로봇이 정해진 경로로 이동해야하는 이동하는 최소의 명령어 길이를 구하는거다. 로봇이 출발할수 있는 지점과 방향은 지정되지 않고 우리가 출력해야한다.

제약조건

5 ≤ H, W ≤ 25

사수는 한 번 이상의 A 명령을 내렸다. 따라서, 로봇이 방문한 칸 수는 최소 3개 이상이다.

이 문제의 경우 목표를 달성할 수 있는 방안이 여러개 일 수 있으며 그 중 아무 것이나 출력해도 답으로 처리된다.

Java 1초 1024MB

풀이

로봇이 할수 있는 경우의 수는 세가지다

• 앞으로 가기
• 왼쪽으로 돌기
• 오른쪽으로 돌기 이세가지 경우를 모두 탐방하되 갈수 없으면 재귀를 가지 않는 dfs 를 진행한다.

개선점

• 모든 칸에대해 출발가능성을 보는것 -> 출발지점을 찾고 그 지점만 탐색하는방방법 추가 findStart() 함수로 구현

• 하드 코딩 되있던 왼쪽 회전 수학으로 변경 int nextL = ((way - 1) + 4) % 4;

코드

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

public class Main {
    static int W;
    static int H;
    static boolean[][] map; // 시작 지점용
    static boolean[][] originCheck; // 초기 입력 check
    static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};// 위 오 아 왼 오른쪽 회전 기준
    static String result = ""; // 결과 로 전달할 문자열
    static int minSize = Integer.MAX_VALUE; // 명령어 길이 최소정보
    static int[] resultCordi = new int[3]; // 결과 좌표 + 방향 담을 배열

    public static void main(String args[]) throws IOException {
        // 입력 받기, 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        map = new boolean[H][W];
        originCheck = new boolean[H][W];
        for (int row = 0; row < H; row++) {
            String[] rowLine = br.readLine().split("");
            for (int col = 0; col < W; col++) {
                String value = rowLine[col];
                if (value.equals("#")) {
                    map[row][col] = false;
                    originCheck[row][col] = false;
                } else {
                    map[row][col] = true;
                    originCheck[row][col] = true;
                }
            }
        }
        // dfs

        int[] startArr = findStart();
        String temp = "";
        originCheck[startArr[0]][startArr[1]] = true;
        dfs(startArr[0], startArr[1], startArr[2], originCheck, temp);
        // 결과 출력 부분
        System.out.println((startArr[0] + 1) + " " + (startArr[1] + 1));
        if (startArr[2] == 0) { // 결과 매핑
            System.out.println("^");
        } else if (startArr[2] == 1) {
            System.out.println(">");
        } else if (startArr[2] == 2) {
            System.out.println("v");
        } else if (startArr[2] == 3) {
            System.out.println("<");
        }

        System.out.println(result);
    }
    public static int[] findStart(){
        int minCount = Integer.MAX_VALUE;
        int [] res = new int[3];
        for(int row = 0; row < H; row++){
            for(int col = 0; col < W; col++){
                // 주변에 칸이 제일 작은게 출발점이다!
                int neighborCount = 0;
                int resWay = -1;
                for(int way = 0; way < 4; way++){
                    int nextR = row + dir[way][0];
                    int nextC = col + dir[way][1];
                    if(!map[row][col] &&isIn(nextR, nextC) && !map[nextR][nextC]){
                        neighborCount+=1;
                        resWay = way;
                    }
                }
                if(minCount > neighborCount && neighborCount > 0){
                    minCount = neighborCount;
                    res[0] = row;
                    res[1] = col;
                    res[2] = resWay;
                }

            }
        }
        return res;
    }

    public static void dfs(int row, int col, int way, boolean[][] beforeCheck, String res) {

        if (isAllTrue(beforeCheck) && res.length() < minSize) {
            // 길이가 최소이고 전부 방문하면 종료하고 결과 전용 전역 변수에 넣는다.
            minSize = res.length();
            result = res;
            return;
        }

        // 전방이동
        boolean[][] nextCheck = checkCopy(beforeCheck);
        int[] d = dir[way];
        int forwardR = row + d[0];//전방으로 이동
        int forwardC = col + d[1];
        if (isIn(forwardR, forwardC) && !nextCheck[forwardR][forwardC]) {// 한칸앞이 가능하면 앞으로 2칸 앞으로 시도
            // A 명령어는 두번 이동한다 한번더 이동 + 체크
            nextCheck[forwardR][forwardC] = true;
            forwardR += d[0];
            forwardC += d[1];
            if (isIn(forwardR, forwardC) && !nextCheck[forwardR][forwardC]) {
                nextCheck[forwardR][forwardC] = true;// 한번더 가능하면 이동
            } else {// 불가능한 경우 다시 뒤로이동
                forwardR -= d[0];
                forwardC -= d[1];
            }
            dfs(forwardR, forwardC, way, nextCheck, res + "A");
        }
        // 오른쪽 이동
        nextCheck = checkCopy(beforeCheck);
        int nextR = (way + 1) % 4; // 오른쪽 방향 회전
        int[] rWay = dir[nextR];
        int nextRrow = row + rWay[0];
        int nextRcol = col + rWay[1];
        if (isIn(nextRrow, nextRcol) && !nextCheck[nextRrow][nextRcol]) {
            nextCheck[nextRrow][nextRcol] = true;
            dfs(nextRrow, nextRcol, nextR, nextCheck, res + "R");// 가능하면 재귀로 넘겨라
        }

        // 왼쪽이동
        nextCheck = checkCopy(beforeCheck);
        int nextL = ((way - 1) + 4) %4;
        int[] lWay = dir[nextL];
        int nextLRow = row + lWay[0];// 왼쪽 방향으로 이동
        int nextLCol = col + lWay[1];
        if (isIn(nextLRow, nextLCol) && !nextCheck[nextLRow][nextLCol]) {
            nextCheck[nextLRow][nextLCol] = true;
            dfs(nextLRow, nextLCol, nextL, nextCheck, res + "L");// 가능하면 재귀로 넘겨라
        }
    }

    // 결과 확인할때 방문다해야 결과를 보여줄수 있다 모두 방분 했는지 체크하는 함수
    public static boolean isAllTrue(boolean[][] checkTarget) {

        for (boolean[] rowTarget : checkTarget) {
            for (boolean b : rowTarget) {
                if (!b) {
                    return false;
                }
            }
        }
        return true;

    }

    public static boolean[][] checkCopy(boolean[][] inCheck) {
        boolean[][] re = new boolean[H][W];
        for (int row = 0; row < H; row++) {
            for (int col = 0; col < W; col++) {
                re[row][col] = inCheck[row][col];
            }
        }
        return re;
    }

    public static boolean isIn(int row, int col) {
        return row >= 0 && row < H && col >= 0 && col < W;
    }
}

https://softeer.ai/practice/info.do?idx=1&eid=577

요약

로봇은 명령어로 동작한다

• A 는 2번 앞으로 이동
• R 은 오르쪽으로 돌기
• L 은 왼쪽으로 돌기

로봇이 정해진 경로로 이동해야하는 이동하는 최소의 명령어 길이를 구하는거다. 로봇이 출발할수 있는 지점과 방향은 지정되지 않고 우리가 출력해야한다.

제약조건

• 5 ≤ H, W ≤ 25

• 사수는 한 번 이상의 A 명령을 내렸다. 따라서, 로봇이 방문한 칸 수는 최소 3개 이상이다.

• 이 문제의 경우 목표를 달성할 수 있는 방안이 여러개 일 수 있으며 그 중 아무 것이나 출력해도 답으로 처리된다.

Java 1초 1024MB

풀이

로봇이 할수 있는 경우의 수는 세가지다

• 앞으로 가기
• 왼쪽으로 돌기
• 오른쪽으로 돌기

이세가지 경우를 모두 탐방하되 갈수 없으면 재귀를 가지 않는 가지치기를 진행한다.

모든 칸 H * W 에 대해 가능 한지 확인해야하기 때문에 O(H * W *3 ^ H * W) = O(3 ^ H * W) 이지만 중간에 못가는곳은 dfs 재귀를 안태우는 가지치기를 해서 더 빠르게 나올수 있다.

메모리의 경우 완탐시 복제되는 check 가 보통 문제 인데 O(HW)로 조건을 충족할수 있다.

시간 메모리는 해결되었고,dfs 를 활용한 완전탐색 알고리즘으로 작성했다.

코드는 앞서 말한 dfs 재귀로 가능한 앞, 왼쪽, 오른쪽 탐색하고 경우의 수마다 check 를 넘겨줘 경우의 수별로 독립적인 진행을 했다.

코드

package softeer.robotPath;

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

public class Main {
    static int W;
    static int H;
    static boolean[][] map; // 시작 지점용
    static boolean[][] OriginCheck; // 초기 입력 check
    static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};// 위 오 아 왼 오른쪽 회전 기준
    static String result = ""; // 결과 로 전달할 문자열
    static int minSize = Integer.MAX_VALUE; // 명령어 길이 최소정보
    static int[] resultCordi = new int[3]; // 결과 좌표 + 방향 담을 배열

    public static void main(String args[]) throws IOException {
        // 입력 받기, 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        map = new boolean[H][W];
        OriginCheck = new boolean[H][W];
        for (int row = 0; row < H; row++) {
            String[] rowLine = br.readLine().split("");
            for (int col = 0; col < W; col++) {
                String value = rowLine[col];
                if (value.equals("#")) {
                    map[row][col] = false;
                    OriginCheck[row][col] = false;
                } else {
                    map[row][col] = true;
                    OriginCheck[row][col] = true;
                }
            }
        }
        // dfs
        for (int row = 0; row < H; row++) {
            for (int col = 0; col < W; col++) {
                if (!map[row][col]) {//모든 점을 확인하다 시작이 가능한 map 이면 시작해라
                    for (int way = 0; way < 4; way++) {
                        int[] resCordi = new int[3]; // 결과 출력을위해 재귀 매개변수로 넘길 좌표 + 방향
                        resCordi[0] = row;
                        resCordi[1] = col;
                        resCordi[2] = way;
                        boolean[][] nextCheck = checkCopy(OriginCheck); // 복제
                        nextCheck[row][col] = true;
                        dfs(row, col, way, nextCheck, "", resCordi);
                    }
                }
            }
        }
        // 결과 출력 부분
        System.out.println((resultCordi[0] + 1) + " " + (resultCordi[1] + 1));
        if (resultCordi[2] == 0) { // 결과 매핑
            System.out.println("^");
        } else if (resultCordi[2] == 1) {
            System.out.println(">");
        } else if (resultCordi[2] == 2) {
            System.out.println("v");
        } else if (resultCordi[2] == 3) {
            System.out.println("<");
        }

        System.out.println(result);
    }

    public static void dfs(int row, int col, int way, boolean[][] beforeCheck, String res, int[] resCordi) {
        if (isAllTrue(beforeCheck) && res.length() < minSize) {
            // 길이가 최소이고 전부 방문하면 종료하고 결과 전용 전역 변수에 넣는다.
            minSize = res.length();
            result = res;
            resultCordi = resCordi.clone();
            return;
        }

        // 전방이동
        boolean[][] nextCheck = checkCopy(beforeCheck);
        int[] d = dir[way];
        int forwardR = row + d[0];//전방으로 이동
        int forwardC = col + d[1];
        if (isIn(forwardR, forwardC) && !nextCheck[forwardR][forwardC]) {// 한칸앞이 가능하면 앞으로 2칸 앞으로 시도
            // A 명령어는 두번 이동한다 한번더 이동 + 체크
            nextCheck[forwardR][forwardC] = true;
            forwardR += d[0];
            forwardC += d[1];
            if (isIn(forwardR, forwardC) && !nextCheck[forwardR][forwardC]) {
                nextCheck[forwardR][forwardC] = true;// 한번더 가능하면 이동
            } else {// 불가능한 경우 다시 뒤로이동
                forwardR -= d[0];
                forwardC -= d[1];
            }
            dfs(forwardR, forwardC, way, nextCheck, res + "A", resCordi);
        }
        // 오른쪽 이동
        nextCheck = checkCopy(beforeCheck);
        int nextR = (way + 1) % 4; // 오른쪽 방향 회전
        int[] rWay = dir[nextR];
        int nextRrow = row + rWay[0];
        int nextRcol = col + rWay[1];
        if (isIn(nextRrow, nextRcol) && !nextCheck[nextRrow][nextRcol]) {
            nextCheck[nextRrow][nextRcol] = true;
            dfs(nextRrow, nextRcol, nextR, nextCheck, res + "R", resCordi);// 가능하면 재귀로 넘겨라
        }

        // 왼쪽이동
        nextCheck = checkCopy(beforeCheck);
        int nextL;
        if (way == 0) { // 왼쪽 으로 회전 하드코딩말고 좀더 쉬운 방법이 있을텐데
            nextL = 3;
        } else if (way == 1) {
            nextL = 0;
        } else if (way == 2) {
            nextL = 1;
        } else {
            nextL = 2;
        }
        int[] lWay = dir[nextL];
        int nextLRow = row + lWay[0];// 왼쪽 방향으로 이동
        int nextLCol = col + lWay[1];
        if (isIn(nextLRow, nextLCol) && !nextCheck[nextLRow][nextLCol]) {
            nextCheck[nextLRow][nextLCol] = true;
            dfs(nextLRow, nextLCol, nextL, nextCheck, res + "L", resCordi);// 가능하면 재귀로 넘겨라
        }
    }

    // 결과 확인할때 방문다해야 결과를 보여줄수 있다 모두 방분 했는지 체크하는 함수
    public static boolean isAllTrue(boolean[][] checkTarget) {

        for (boolean[] rowTarget : checkTarget) {
            for (boolean b : rowTarget) {
                if (!b) {
                    return false;
                }
            }
        }
        return true;

    }

    public static boolean[][] checkCopy(boolean[][] inCheck) {
        boolean[][] re = new boolean[H][W];
        for (int row = 0; row < H; row++) {
            for (int col = 0; col < W; col++) {
                re[row][col] = inCheck[row][col];
            }
        }
        return re;
    }

    public static boolean isIn(int row, int col) {
        return row >= 0 && row < H && col >= 0 && col < W;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/42883

요약

문제 내용은 문자열로 숫자가 제공되는데 이숫자중 k 개를 지워서 가장 큰수를 만들어야한다. 단, 숫자의 순서는 바뀌면 않된다.

제약조건 number는 2자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다.

풀이

완탐을 고려하게되면 10 ^ 6 라는 숫자를 제곱으로돌려야한다. 때문에 한번에 처리할수 있는 방법을 생각해야한다. 최종적으로 가장큰수를 구하기 위해선 앞자리 에 큰수들이 있게 배치해야한다. 입력을 순회하면서 최근 값을 계속 비교하면서 k 개 만큼만 지우면된다. 단순히 비교로 진행될 수 있지만 스텍을 활용하면 최근에 값을 저장하기도 비교하기도 유용하게 할수 있다. 즉 스텍에 최대한의 큰값을 넣는거다.

로직 구현

k 횟수만큼 값이 더 크다면 스텍에 저장된 값을빼고 큰값을 넣는다. 스텍의 값보다 작은 걸 만나면 값을 넣는다. 만약 스텍이 비어 있다면 값을 넣는다.

코드

package programers.makeBigNum.suc;

import java.util.*;

// 큰수만 스텍에 넣는다
public class Solution {
    public String solution(String number, int k) {
        Stack<Integer> stack = new Stack<>();
        int count = k;
        String[] splited = number.split("");
        for (String st : splited) {
            int value = Integer.parseInt(st);
            while (!stack.isEmpty() && stack.peek() < value && count-- > 0) {
                stack.pop();//값이 크다면 최근 값을빼고 값을 넣는다.
            }
            stack.push(value);
        }
        String answer = "";
        System.out.println(k);
        for (int i = 0; i < number.length() - k; i++) {
            answer += stack.get(i);
        }
        return answer;
    }
}

시행착오

처음에 입력들중에 가장 작은 수 k 만큼 정렬해 작은 수를 set 에 넣어 동작 k개 만큼 앞에서 지워나가려 했다. 하지만 반례로 417725, k = 2 가 있다. 이숫자의 가장 작은수 set 은 1,2 인데 그렇게 작은수 잘못된 로직은 4772 를 출력한다 정답(7725).

나중에 든 생각인데 만약 number.length()-k 갯수만큼 set 에 넣게하면 set = {1,2,3,4}, 그리고 k개만 지우개 잘 구현하면 될거 같다는 생각도든다.

import java.util.*;
//정렬하고 len-k 갯수 만큼 추출 돌면서 해당되면 지우기
public class Solution {
    public String solution(String number, int k) {
        // int count = number.length() -k;
        int count = k;
        String [] splited = number.split("");
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for(String s :splited){
            q.offer(Integer.parseInt(s));
        }
        Set<Integer> banSet = new HashSet<>();
        while(count-- > 0){
            banSet.add(q.poll());
        }
        // 제일 작은 len-k 를 구한다 -> 갯수만큼 제외한다...
        // 갯수가 안맞는 경우는? -> 숫자를 뽑아 왔는데 갯수가 부족한경우
        // 많이 있을수 있는데 부족할수 없다 중복된 경우가 많은 경우 작으면 애초에 와일문 에서 성립이 안됨
        int rmCount = k;
        StringBuilder sb = new StringBuilder();
        int idx = 0;
        while(rmCount > 0 && idx < number.length()){
            int value = Integer.parseInt(splited[idx]);
            if(banSet.contains(value)){
                rmCount--;
            }else{
                sb.append(value);// 포함이 안되면 넣어라
            }
            idx++;
        }
        for(;idx < number.length(); idx++){
            sb.append(splited[idx]);
        }
        int totalCount = number.length() - k;
        StringBuilder res = new StringBuilder();
        int resIdx = 0;
        while(totalCount-- >0){
            res.append(sb.toString().charAt(resIdx++));

        }
        System.out.println(banSet);
        return res.toString();
    }
}

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

요약

간단히 내용을 요약하면 왼쪽위에서 오른쪽아래 칸으로 가는경우를 구하는데 칸의 값이 낮아지는 방향으로 진행되다는 조건이 있다 0<= N,M < 500 칸의 값은 10000이하의 자연수이다. (0은 자연수다)

풀이

500 ^ 2 의 모든 칸을 조사해 경우의수르 따지는 완탐을 사용하면 꽤 많은 수가 나오게 된다. 그렇기 때문에 dp 를 활용하거나 그리디 를 활용해야한다. 찾으면서 값을 갱신하는 형태의 dp 를 활용하기로 결정했고 dp 함수의 정의는 해당 칸에서 목적지에 도착할수 있는 경우의 수를 삼아 진행하면서 합해가는 형태로 만들었다. 특징으로라면 -1 로 dp 를 초기화한 부분인데 그이유는 해당 칸이 목적지에 도착할수 있는 경우가 0인경우가 있기때문이다 여기서 방문을 별도로 관리하면 메모리가 초과날수도 있다는 생각이 들었다.

로직

피보나치 + 메모이제이션과 유사한 구조

1. 0,0 에서 부터 dp 에 값이 없다면 재귀를 시도한다
2. 만약 -1 값이라면 0으로 초기화한다.
3. 값이 가능한값 (점점커지근 값 && 내부에 있다면) 이라면 dp 누산시킨다.

   코드

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

/**

• 탑다운 방식

• dp[][] 해당칸에서 목적지 도착하는 경우

• 1. 기록된게 없다면 재귀타고 찾아온다 끝 닿을때까지
• 2. 처음 방문하면 0으로 바꿔줘라

• 방문처리를 배열로 하면 메모리 초과 (계속 넘겨줘야한다.)구할때 -1 이면 찾으러 가라 하자 like 피보나치 + 메모이제이션

• 내려막이기때문에 역주행 막을수 있다

• / public class Main { static int N; static int M; static int[][] dp; static int[][] input; static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    M = Integer.parseInt(st.nextToken());
    N = Integer.parseInt(st.nextToken());
    dp = new int[M][N];
    input = new int[M][N];
    for (int[] d : dp) {
        Arrays.fill(d, -1);
    }
    for (int row = 0; row < M; row++) {
        st = new StringTokenizer(br.readLine());
        for (int col = 0; col < N; col++) {
            input[row][col] = Integer.parseInt(st.nextToken());
        }
    }
    System.out.println(dfs(0, 0));

}

private static int dfs(int row, int col) {
    if (row == M - 1 && col == N - 1) {
        return 1; // 닿으면 한개 리턴
    }

    if (dp[row][col] != -1) {
        return dp[row][col]; // 값이 있다면 돌려줘라
    }
    dp[row][col] = 0; //일단 초기화
    for (int[] d : dir) {
        int nextRow = row + d[0];
        int nextCol = col + d[1];

        if (isIn(nextRow, nextCol) && input[row][col] > input[nextRow][nextCol]) {

            dp[row][col] += dfs(nextRow, nextCol); // 값더해주기

        }
    }
    return dp[row][col];
}



private static boolean isIn(int row, int col) {
    return row < M && row >= 0 && col < N && col >= 0;
}

}

# 시행착오

처음에 완탐으로 진행했다가 메모리터지고 확인해보니 128mb 이였다.
이후 dfs 의 check 부분을 좀 없에려는 여러시도를 해보다 결국 해답은 dp 라 생각했다.
<details>
<summary></summary>
<div markdown="1">



``` java


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

/**
 * 2초 시간이 오래 걸려도 하나의 배열에 담는 방법 없을까..
 * 각점별로 가능성을 보기
 *
 */

public class Main {
    static int N;
    static int M;
    static int[][] input;
    static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    static int count = 0;
    static int testCount = 0;
    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());
        input = new int[N][M];
        for (int row = 0; row < N; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < M; col++) {
                input[row][col] = Integer.parseInt(st.nextToken());
            }
        }
        boolean[][] check = new boolean[N][M];
        check[0][0] = true;
        dfs(0, 0);
        System.out.println(count);
    }

    private static void dfs(int row, int col) {
        testCount++;
        if (row == N - 1 && col == M - 1) {
            count++;
            return;
        }
        for (int d = 0; d < 4; d++) {
            int nextRow = row + dir[d][0];
            int nextCol = col + dir[d][1];
            if (isIn(nextRow, nextCol) && input[nextRow][nextCol] < input[row][col]) {
                for (int brow = 0; brow < N; brow++) {
                    for (int bcol = 0; bcol < M; bcol++) {
                    }
                }
                dfs(nextRow, nextCol);
            }
        }

    }

    private static void printArr(boolean[][] arr) {
        System.out.println();
        for (boolean[] br : arr) {
            for (boolean b : br) {
                System.out.print(b ? 1 : 0);
            }
            System.out.println();
        }
    }

    private static boolean isIn(int row, int col) {
        return row < N && row >= 0 && col < M && col >= 0;
    }
}

• 다음 링크에서 mysql connector 다운로드 https://dev.mysql.com/downloads/connector/j/5.1.html

• 압축 해제

• 다운로드한 커넥터 압출풀고 jar 파일 이동
• 저같은 경우 도커 컨테이너로 spark 구성 하였기에 docker cp 를 사용해 컨테이너 내부로 옮겼습니다
• 자신에 환경에 맞게 spark 내부 jar 폴더에 넣으면됩니다.

  docker cp mysql-connector-j-8.0.32.jar spark-master:/spark/jar

왜 mariaDB 커넥터를 사용하지 않나요?

• 처음에 mariaDB 커넥터를 사용했고 jdbc 를 통해 정상접근 확인.
• 하지만 spark 상에서 dataframe.show() 를 사용해 출력하면 데이터 자리에 컬럼명이 들어간체 오는걸로 확인했습니다.

MariaDB 조회 결과

Spark application 결과

+--------+
|nickname|
+--------+
|nickname|
|nickname|
|nickname|
+--------+

• 이 문제를 해결하기 위해 다음 링크를 참조해 지금 문서에 반영했습니다. https://stackoverflow.com/questions/40547993/spark-sql-jdbc-returning-only-column-names https://stackoverflow.com/questions/66983401/spark-mariadb-jdbc-sql-query-returns-column-names-instead-of-column-values

2.Spark Application 작성

Maria db 에 연결 하고 테이블을 읽어오는 pyspark application 입니다.

from pyspark.sql import SparkSession

# 스파크 세션 생성
spark = SparkSession.builder \
    .appName("MariaDB Connection Example") \
    .getOrCreate()
url = 'jdbc:mysql://maria-db:3306/dbName'

## dataFram api 활용 db 접근 아이디 비밀번호는 개인환경에 맞춰서 작성
jdbcDF = spark.read \
    .format("jdbc") \
    .option("url", url) \
    .option("user", "user") \
    .option("password", "pw") \
    .option("dbtable", "member") \
    .load()

jdbcDF.show()

다음 코드는 외부 접근이 가능한 디비 유저, 비밀번호 를 입력하면됩니다. 외부 접근되는 계정이 아닌 root 를 사용할경우 경우에 따라 permission 애러나 발생할수 있습니다.

    .option("user", "user") \
    .option("password", "pw") \

작성후 saprk/app/ 에 저장했습니다 각자 환경에 맞춰 저장하시면됩니다.

3.Spark-submit 으로 실행

실행에 들어가기 앞서 만약 MariaDB 가 도커 컨테이너로 구성 되어있다면 spark클러스터와 같은 네트워크 에 구성되어 있는지 화인하셔야합니다. 연결이 안되 있다면 다음 명령어를 사용해 연결하세요

docker network connect 스파크_네트워크 MariaDB_컨테이너이름

실행

./spark-submit --driver-class-path /usr/share/java/mysql-connector-8.0.32.jar --jars /usr/share/java/mysql-connector-8.0.32.jar  ../app/pyspark/dbConnect.py

결과

만약

출력시 UnicodeEncodeError: 'ascii' codec can't encode character 에러 발생 한다면 해결책 으로 다음 과 같이 환경변수를 추가하면됩니다

export PYTHONIOENCODING=utf8

https://stackoverflow.com/questions/39662384/pyspark-unicodeencodeerror-ascii-codec-cant-encode-character

등산로를 조성하려고 한다.

등산로를 만들기 위한 부지는 N * N 크기를 가지고 있으며, 이곳에 최대한 긴 등산로를 만들 계획이다.

등산로 부지는 아래 [Fig. 1]과 같이 숫자가 표시된 지도로 주어지며, 각 숫자는 지형의 높이를 나타낸다.

등산로를 만드는 규칙은 다음과 같다.

① 등산로는 가장 높은 봉우리에서 시작해야 한다.

② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다. 즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다.

③ 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.

N * N 크기의 지도가 주어지고, 최대 공사 가능 깊이 K가 주어진다.

이때 만들 수 있는 가장 긴 등산로를 찾아 그 길이를 출력하는 프로그램을 작성하라.

[예시]

위 [Fig. 1]과 같이 N = 5인 지도가 주어진 경우를 살펴보자.

가장 높은 봉우리는 높이가 9로 표시된 세 군데이다.

이 세 곳에서 출발하는 가장 긴 등산로 중 하나는 아래 [Fig. 2]와 같고, 이 때 길이는 5가 된다.

만약 최대 공사 가능 깊이 K = 1로 주어질 경우,

아래 [Fig. 3]과 같이 빨간색 부분의 높이를 9에서 8로 깎으면 길이가 6인 등산로를 만들 수 있다.

이 예에서 만들 수 있는 가장 긴 등산로는 위와 같으며, 출력할 정답은 6이 된다.

[제약 사항]

1. 시간 제한 : 최대 51개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초

2. 지도의 한 변의 길이 N은 3 이상 8 이하의 정수이다. (3 ≤ N ≤ 8)

3. 최대 공사 가능 깊이 K는 1 이상 5 이하의 정수이다. (1 ≤ K ≤ 5)

4. 지도에 나타나는 지형의 높이는 1 이상 20 이하의 정수이다.

5. 지도에서 가장 높은 봉우리는 최대 5개이다.

6. 지형은 정수 단위로만 깎을 수 있다.

7. 필요한 경우 지형을 깎아 높이를 1보다 작게 만드는 것도 가능하다.

[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 지도의 한 변의 길이 N, 최대 공사 가능 깊이 K가 차례로 주어진다.

그 다음 N개의 줄에는 N * N 크기의 지도 정보가 주어진다.

[출력]

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.

각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 만들 수 있는 가장 긴 등산로의 길이이다.

풀이

문제의 핵심은 어떻게 지형을 깍느냐이다 다행이 깍을수 있는 최대 높이 K 와 N 의 최대 크기가 5, 18 로 크지 않다 그리고 지형을 깍지만 무조건 하나만 깍기 때문에 모든 지형을 0 ~ K 만큼깍아 보아도 최악의 경우 18 * 18 * 5 로 1620 이다 그리고 경로를 찾아야하는데 찾을때 현제 경사보다 작은 경사를 골라야한다. 문제에서 가장긴 경로를 찾으라 했고 최단 경로를 구하는게 아니다 경로를 깊게 파고 가야하니 머리속에 dfs 먼저 그려졌다. dfs 의 시간복잡도는 O (V + E) 로 최악의 경우 모든 지형의 4방향을 탐색함으로 18*18 + 4 = 1296 이다 즉 총 시간복잡도는 1602 * 1296 = 2,076,192 2백만 정도 나오게 된다.

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class PointDto {
    int r;
    int c;

    public PointDto(int r, int c) {
        super();
        this.r = r;
        this.c = c;
    }

}

public class Solution {
    // 단순하게 생각하는 연습
    static int Tc;
    static int N;
    static int K;
    static int[][] originMap;
    static int maxRoad;
    static boolean[][] check;
    static int[][] dArr = { { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } };

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Tc = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < Tc; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            originMap = new int[N][N];
            check = new boolean[N][N];
            for (int row = 0; row < N; row++) {
                st = new StringTokenizer(br.readLine());
                for (int col = 0; col < N; col++) {
                    originMap[row][col] = Integer.parseInt(st.nextToken());
                }
            }
            // 바꿀거하나선택하는 부분
            maxRoad = 0;
            for (int row = 0; row < N; row++) {
                for (int col = 0; col < N; col++) {
                    for (int k = 0; k <= K; k++) {
                        List<PointDto> maxList = findMax(originMap);
                        originMap[row][col] -= k;
                        for(PointDto point : maxList) {
                            check = new boolean[N][N];
                            check[point.r][point.c] = true;
                            dfs(point.r, point.c, 1);
                        }
                        originMap[row][col] += k;
                    }
                }
            }
            System.out.printf("#%d %d\n", tc + 1, maxRoad);
        }

    }

    private static void dfs(int targetRow, int targetCol, int depth) {
        maxRoad = Math.max(maxRoad, depth);
        for (int d = 0; d < 4; d++) {
            int nextRow = targetRow + dArr[d][0];
            int nextCol = targetCol + dArr[d][1];
            if (isOut(nextRow, nextCol) && !check[nextRow][nextCol]) {
                if (originMap[targetRow][targetCol] > originMap[nextRow][nextCol]) {
                    check[nextRow][nextCol] = true;
                    dfs(nextRow, nextCol, depth + 1);
                    check[nextRow][nextCol] = false;
                }
            }
        }
    }

    private static boolean isOut(int nextRow, int nextCol) {
        return nextRow < N && nextRow >= 0 && nextCol < N && nextCol >= 0;
    }

    private static List<PointDto> findMax(int[][] inputMap) {
        int maxNum = 0;
        List<PointDto> res = new ArrayList<>();
        for (int[] row : inputMap) {
            for (int el : row) {
                maxNum = Math.max(el, maxNum);
            }
        }
        for (int row = 0; row < N; row++) {
            for (int col = 0; col < N; col++) {
                if (originMap[row][col] == maxNum) {
                    res.add(new PointDto(row, col));
                }
            }
        }
        return res;
    }

}

Valid Palindrome A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.

Constraints:

1 <= s.length <= 2 * 105 s consists only of printable ASCII characters.

문제의 내용은 대문자 등 소문자등 상관없이 앞으로 읽든 뒤로 읽든 같으면 true 틀리면 false 를 출력하는 함수를 만들라는것이다. 단 입력은 길이 2*105 만큼 아스키 문자 어떤것이든 온다

풀이

1. 입력이 어떠한 문자열이든지 가능하고 대문자 소문자 구분 없으니 특수문자를 거르고 소문자로 양식을 통일 or 대문자로 양식 통일 해야한다

• 대문자 소문자 char.lower() 활용
• 문자 판독 char.isalnum() 활용

2. 앞뒤로 읽었을을때 같은걸 검사해야하는데 이건 루프를 돌며 하는 방법도 있지만 덱 자료구조를 활용하는 방법이 있다 나는 덱을 활용하였다

• 큐 deque 활용

코드

from collections import deque
class Solution:
    def isPalindrome(self, s: str) -> bool:
        char_que = deque()
        for el in s:
            if el.isalnum():
                char_que.append(el.lower())

        len_que = len(char_que)
        for _ in range(len_que//2):
            if char_que.pop() != char_que.popleft():
                return False
        return True