haleylog

요구사항

주어진 수식들 중 일부 결괏값이 'X'표시로 지워져 있으며, 수식은 2~9진법 중 하나의 진법을 사용할 때

지워진 수식을 완성하여 출력하기

(가능한 결괏값이 여러개인 경우 ?로 표시)

입력 값

풀이

1. 수식의 확인하고 저장할 변수 생성

2. 수식 전체를 탐색

    -> 공란으로 수식을 잘라서 0번째는 첫번째 숫자(fNum), 2번째는 두번째 숫자(sNum), 4번째는 세번째 숫자(rNum) 저장

    -> 1번째는 연산부호로 + 인 경우 +1을 -인 경우 -1을 oper 에 저장

    -> 4번째 숫자가 "X" 인 경우 지워진 수식 List(unsolves) 에 추가

3. 사용 가능한 진법 별로 수식 연산 하여 불가능한 수식은 진법 리스트(numbers) 에서 제외 처리

    -> 주어진 진법으로 변환하지 못하는 숫자가 포함된 경우 제외 (= 진법과 같거나 큰 숫자라 표현할수 없는 숫자)
    -> 정상 수식일때 주어진 정답과 다르면 제외

4. 가능한 진법 숫자 리스트를 통해 지워진 수식 List 별로 정답 재 작성하기

    -> 숫자 별 정답 생성하여 하나라도 다른 정답이 있는 경우 X를 ?로 변환

    -> 모두 같은 정답인 경우 X를 정답으로 변경  

5. 재 작성 된 수식 return

Java 코드

import java.util.*;

class Solution {
    public String[] solution(String[] expressions) {
        String[] answer = {};
        
        List<Integer> numbers = new ArrayList<>(Arrays.asList(2,3,4,5,6,7,8,9));
        List<String> unsolves = new ArrayList<>();
        String fNum, sNum, rNum;
        int oper;
        
        for(String expression : expressions) {
            fNum = expression.split(" ")[0];
            sNum = expression.split(" ")[2];
            rNum = expression.split(" ")[4];
            oper = "+".equals(expression.split(" ")[1]) ? 1 : -1;
            
            if("X".equals(rNum)) unsolves.add(expression);

            for(int i=2; i<=9; i++) {
                if(numbers.indexOf(i) == -1) continue;
                
                try {
                    if("X".equals(rNum)) {
                        // 변환 가능한지 여부만 체크
                        Integer.parseInt(fNum, i);
                        Integer.parseInt(sNum, i);
                    } else if(Integer.parseInt(fNum, i) + Integer.parseInt(sNum, i) * oper
                       != Integer.parseInt(rNum, i)) throw new NumberFormatException();
                } catch (NumberFormatException e) {
                    numbers.remove(numbers.indexOf(i));
                }
            }
        }
        
        answer = new String[unsolves.size()];
        String result, nowVal;
        
        for(int i=0; i<unsolves.size(); i++) {
            result  = "";
            fNum    = unsolves.get(i).split(" ")[0];
            oper    = "+".equals(unsolves.get(i).split(" ")[1]) ? 1:-1;
            sNum    = unsolves.get(i).split(" ")[2];
            
            for(int n : numbers) {
                nowVal = Integer.toString(Integer.parseInt(fNum, n) + Integer.parseInt(sNum, n)*oper, n);
                
                if(!"".equals(result) && !nowVal.equals(result)) {
                    result = "?";
                    break;
                }
                
                result = nowVal;
            }
            
            answer[i] = unsolves.get(i).replace("X", result);
        }
        
        return answer;
    }
}

문제 출처

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

요구사항

주어진 퍼즐판에서 빨간색과 파란색 수레가 각각의 주어진 도착 칸으로 이동해야 할때

1. 각 수레는 벽이나 격자 밖으로 나갈 수 없다.

2. 동시에 두 수레가 같은 칸에 있을 수 없다.

3. 수레는 상하좌우로만 움직일 수 있다.

4. 도착지에 도착하기 전까지 각 턴마다 수레를 무조건 움직여야 한다.

5. 두 수레가 서로 위치를 바꿀수 없다.

위와 같은 조건으로 가는 경로의 경우의 수 중에 최소값 구하기.

입력 값

풀이

1. 각 수레의 출발 칸과 도착 칸의 좌표 구하기

    -> 출발 칸 방문 여부 수레 별 각각 저장

2. 상하좌우 이동 가능한 모든 경우의 수 구하기 (Backtracking)

    -> 상하좌우 칸 중 퍼즐 판 내에서 벽인 경우 Pass

    -> 상하좌우 칸 중 각 수레가 방문한 적 있는 경우 Pass

    -> 상하좌우 칸 중 두 수레가 동일한 칸으로 이동하는 경우 Pass

    -> 상하좌우 칸 중 수레간 상호 교환하는 이동인 경우 Pass

    -> 이동 경로 저장 후 이동횟수 + 1 처리 하여 다음 이동 경로 추가 탐색 반복 (재귀)

3. 빨간 수레와 파란 수레가 각각 도착 좌표에 도착하면 총 이동 횟수 Min 비교

    -> 퍼즐은 최대 4*4 크기이므로 최초 minCount 는 16으로 시작 (16회 이상 움직일 수 없음)

4. 최소 이동 횟수 return

    -> minCount가 16 인 경우 한번도 도착하지 못했으므로 0 return

Java 코드

import java.util.*;

class Solution {
    // 수레 별 이동 경로
    static boolean[][] rMove, bMove;
    static int minCount = 16;
    
    public int solution(int[][] maze) {
        int answer = 0;
        
        rMove = new boolean[maze.length][maze[0].length];
        bMove = new boolean[maze.length][maze[0].length];
        
        // 수레 별 현재/끝 좌표
        int[] red       = new int[2];
        int[] redGoal   = new int[2];
        int[] blue      = new int[2];
        int[] blueGoal  = new int[2];
        
        // 시작 칸과 끝 칸 먼저 구하기
        for(int i=0; i<maze.length;i++) {
            for(int j=0; j<maze[0].length;j++) {
                if(maze[i][j] == 1) { red       = new int[]{i, j}; rMove[i][j] = true;}
                if(maze[i][j] == 2) { blue      = new int[]{i, j}; bMove[i][j] = true;}
                if(maze[i][j] == 3) { redGoal   = new int[]{i, j}; }
                if(maze[i][j] == 4) { blueGoal  = new int[]{i, j}; }
            }
        }
        
        move(red, blue, redGoal, blueGoal, maze, 0);
        answer = minCount == 16 ? 0 : minCount;
         
        return answer;
    }
    
    private void move(int[] red, int[] blue, int[] redGoal, int[] blueGoal, int[][] maze, int moveCnt) {
        int redX    = red[1];
        int redY    = red[0];
        int blueX   = blue[1];
        int blueY   = blue[0];
        
        if(redX == redGoal[1] && redY == redGoal[0] && blueX == blueGoal[1] && blueY == blueGoal[0]) {
            minCount = Math.min(minCount, moveCnt);
            return;
        }
        
        // 상하좌우 탐색용
        int[] rx    = {0, 0, -1, 1};
        int[] ry    = {-1, 1, 0, 0};
        int maxX    = maze[0].length;
        int maxY    = maze.length;
        
        List<int[]> redDirections   = new ArrayList<>();
        List<int[]> blueDirections  = new ArrayList<>();

        if(redX == redGoal[1] && redY == redGoal[0]) redDirections.add(red);
        else {
            for(int i=0; i<4; i++) {
                if(redX + rx[i] < 0 || redX + rx[i] >= maxX || redY + ry[i] < 0 || redY + ry[i] >= maxY
                  || rMove[redY + ry[i]][redX + rx[i]]
                  || maze[redY + ry[i]][redX + rx[i]] == 5
                  ) continue;

                redDirections.add(new int[]{redY + ry[i], redX + rx[i]});
            }
        }

        if(blueX == blueGoal[1] && blueY == blueGoal[0]) blueDirections.add(blue);
        else {
            for(int i=0; i<4; i++) {
                if(blueX + rx[i] < 0 || blueX + rx[i] >= maxX || blueY + ry[i] < 0 || blueY + ry[i] >= maxY
                  || bMove[blueY + ry[i]][blueX + rx[i]]
                  || maze[blueY + ry[i]][blueX + rx[i]] == 5
                  ) continue;

                blueDirections.add(new int[]{blueY + ry[i], blueX + rx[i]});
            }
        }

        for(int[] rDirection : redDirections) {
            for(int[] bDirection : blueDirections) {
                // 동일한 장소로 이동하는 경우 Pass
                if(rDirection[0] == bDirection[0] && rDirection[1] == bDirection[1]) continue;
                // 서로 자리 바꾸는 경우 Pass
                if(rDirection[0] == blueY && rDirection[1] == blueX
                  && bDirection[0] == redY && bDirection[1] == redX) continue;

                rMove[rDirection[0]][rDirection[1]] = true;
                bMove[bDirection[0]][bDirection[1]] = true;

                move(rDirection, bDirection, redGoal, blueGoal, maze, moveCnt+1);
                
                rMove[rDirection[0]][rDirection[1]] = false;
                bMove[bDirection[0]][bDirection[1]] = false;
            }
        }
    }
    
}

문제 출처

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

요구사항

각자 지정된 출발 지점에서 운송 지점 까지 최단 경로로 이동하는 로봇이 있으며

이동 중 같은 좌표에 로봇이 2대 이상 모이면 위험 상황으로 판단된다.

모든 로봇이 운송을 마칠 때까지 발생하는 위험 상황의 횟수 구하기

(최단 경로가 여러가지 인 경우 r좌표 이동을 우선함)

입력 값

풀이

1. 로봇 이동경로 비교 및 저장을 위한 변수 생성

2. 모든 좌표 저장을 위해 모든 로봇의 모든 운송 지점 loop

3. 로봇의 출발 지점 좌표를 현재 시간과 함께 moves(이동 경로 좌표)에 저장

4. 로봇의 현재 좌표와 다음 좌표를 비교하여 최단 거리로 이동하며  현재 시간과 함께 moves(이동 경로 좌표)에 저장

    -> 최단 경로가 여러가지 인 경우 r좌표 이동을 우선함

5. 동 시간대에 같은 좌표가 이미 있다면 dupMoves(충돌 좌표)에 저장

6. 모든 로봇이 모든 운송 지점을 방문할때까지 반복

7. 충돌 좌표 갯수 return

Java 코드

import java.util.*;

class Solution {
    public int solution(int[][] points, int[][] routes) {
        int answer = 0;
        
        // 출발 지점 좌표
        int sttPointR, sttPointC;
        // 도착 지점 좌표
        int endPointR, endPointC;
        // 시간
        int sec;
        // 이동 좌표
        Set<String> moves    = new HashSet<>();
        // 충돌 좌표
        Set<String> dupMoves = new HashSet<>();

        // 로봇 별
        for(int i = 0; i < routes.length; i++) {
            sec = 0;
            
            // 첫 출발점 저장
            sttPointR = points[routes[i][0] - 1][0];
            sttPointC = points[routes[i][0] - 1][1];
            
            if(moves.contains(sec + "-" + sttPointR + "-" + sttPointC)) {
                dupMoves.add(sec + "-" + sttPointR + "-" + sttPointC);
            }
            moves.add(sec + "-" + sttPointR + "-" + sttPointC);
            
            for(int j = 0; j < routes[0].length - 1; j++) {
                // 출발 지점
                sttPointR = points[routes[i][j] - 1][0];
                sttPointC = points[routes[i][j] - 1][1];
                // 도착 지점
                endPointR = points[routes[i][j+1] - 1][0];
                endPointC = points[routes[i][j+1] - 1][1];

                while((sttPointR != endPointR) || (sttPointC != endPointC)) {
                    sec++;
                    
                    if(endPointR > sttPointR) { // 아래 이동
                        sttPointR += 1;
                    } else if (endPointR < sttPointR) { // 위 이동
                        sttPointR -= 1;
                    } else if(endPointC > sttPointC) { // 오른쪽 이동
                        sttPointC += 1;
                    } else if(endPointC < sttPointC) { // 왼쪽 이동
                        sttPointC -= 1;
                    }

                    if(moves.contains(sec + "-" + sttPointR + "-" + sttPointC)) {
                        dupMoves.add(sec + "-" + sttPointR + "-" + sttPointC);
                    }
                    moves.add(sec + "-" + sttPointR + "-" + sttPointC);
                }
            }
            
        }
        
        answer = dupMoves.size();
        
        return answer;
    }
}

문제 출처

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

n개 퍼즐의 난이도와 각 퍼즐의 소요 시간이 주어지고 

퍼즐의 난이도보다 숙련도가 낮으면 난이도와 숙련도의 차이 만큼 이전 퍼즐을 다시 풀어야 한다.

주어진 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값 구하기

입력 값

풀이

1. 이진탐색을 위해 범위 설정

2. 범위 내 중간 값 으로 난이도 가정

3. 퍼즐 배열 loop 돌리며 퍼즐 별 푸는 시간 합산

   -> 숙련도보다 퍼즐 난이도가 높은경우

       (이전 퍼즐 소요시간 + 현재 퍼즐 소요시간) * (난이도 - 숙련도) + 현재 퍼즐 소요시간

   -> 숙련도가 퍼즐 난이도보다 높은 경우

4. 퍼즐 푸는 시간 합산 값과 전체 제한 시간 비교하여 탐색 범위 재설정

   -> 제한 시간 초과인 경우 범위 시작 지점 조정

   -> 제한 시간 남는 경우 범위 종료 지점 조정

   -> 제한 시간과 퍼즐 푸는 시간이 동일한 경우 현재 임시 난이도가 최소값이므로 return

5. 재설정된 범위로 2~4 반복

   -> 범위 시작 지점과 종료 지점이 1이하로 차이나면 종료 지점이 최소값이므로 return

Java 코드

import java.util.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        
        // 이진탐색용 범위 변수
        int rangeStt = 0;
        int rangeEnd = Arrays.stream(diffs).max().getAsInt();
        
        int tempDiff = 1;
        long totalTime;
        
        while(true){
            // 현재 난이도가 범위 경계인 경우 
            if(rangeEnd - rangeStt <= 1) {
                tempDiff = rangeEnd;
                break;
            }
            
            totalTime = 0;
            
            // 난이도 가정
            tempDiff = rangeStt + ((rangeEnd - rangeStt) / 2);
            
            for(int i = 0; i < diffs.length; i++) {
                if(diffs[i] > tempDiff) // 난이도가 숙련도보다 높은경우
                   totalTime += ((times[i-1] + times[i]) * (diffs[i] - tempDiff)) + times[i];
                else
                    totalTime += times[i];

                // 제한시간 초과 시 break
                if(totalTime > limit) break;
            }

            // 범위 재설정
            if(totalTime > limit)
                rangeStt = tempDiff;
            else if(totalTime < limit)
                rangeEnd = tempDiff;
            else break;
            
        }
        
        answer = tempDiff;

        return answer;
    }
}

문제 출처

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

요구사항

주어진 두 시간(시, 분, 초) 사이에 초침과 시침/분침이 만나는 횟수 구하기

(초침, 시침, 분침이 한번에 만나는 경우 1회로 count)

입력 값

풀이

1. 시작 시간의 각(시/분/초) 침의 위치 구하기

   -> 0에서 60 사이의 double 형으로 지정

2. 시작 시간의 초침과 시/분 침이 만나있는 경우 알람 count + 1

3. 시작 시간에서 1초 씩 더해가며 초침과 시/분 침이 만날 경우 count

   -> 초침이 시/분침보다 1칸 미만 작은 경우 1초 후엔 초침이 시/분침을 넘어가므로 알람 count + 1

   -> 시/분/초 침이 한번에 만나는 0시 정각과 12시 정각의 경우 중복 카운팅 방지를 위해 count - 1

4. 알람 count return

Java 코드

class Solution {
    public int solution(int h1, int m1, int s1, int h2, int m2, int s2) {
        int answer = -1;
        
        // 침 위치
        double positionH = getPosition(h1, m1, s1);
        double positionM = getPosition(m1, s1);
        double positionS = getPosition(s1);
        
        // 이동 후 시간
        int nowH = h1;
        int nowM = m1;
        int nowS = s1;
        
        int alarmCount = 0;
        
        // 시작 위치 같은 경우도 count 필요
        if(positionS == positionM || positionS == positionH) alarmCount++;
        
        while(nowH != h2 || nowM != m2 || nowS != s2) {
            // 초침이 분침보다 1칸 미만 차이일때
            if(positionS < positionM && (positionM - positionS < 1)) alarmCount++;
            
            // 초침이 시침보다 1칸 미만 차이일때
            if(positionS < positionH && (positionH - positionS < 1)) alarmCount++;
            
            // 시분초 모두 만나는 정오는 제외
            if((nowH == 11 || nowH == 23) && nowM == 59 && nowS == 59) alarmCount--;
            
            // 현재 시간 설정
            nowH = (nowH + ((nowM + (nowS + 1) / 60) / 60));
            nowM = (nowM + ((nowS + 1) / 60)) % 60;
            nowS = (nowS + 1) % 60;
            
            // 침 위치 재 설정
            positionH = getPosition(nowH, nowM, nowS);
            positionM = getPosition(nowM, nowS);
            positionS = getPosition(nowS);
        }
        answer = alarmCount;
        
        return answer;
    }
    
    private double getPosition(int h, int m, int s){
        double movement = 1.0 / (60*60);
        return (h + (((m * 60) + s) * movement)) * 5 % 60;
    }
    
    private double getPosition(int m, int s){
        double movement = 1.0 / 60;
        return m + (s * movement);
    }
        
    private double getPosition(int s){
        double movement = 1;
        return s * movement;
    }
}

문제 출처

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

요구사항

시추관을 세로로 1개 설치 할 때 가장 많은 석유량을 뽑을 수 있는 열의 석유량 구하기

(해당 열의 땅과 연결 된 석유는 모두 합산됨)

입력 값

풀이

1. 탐색에 사용 될 변수 생성

2. 모든 땅 탐색을 위해 이중 loop 블럭

3. 석유 덩어리 찾기

   -> 처음 탐색하는 땅이고 석유가 있는 경우 상하좌우 탐색 시작을 위해 Queue에 Add

   -> 재 탐색 방지를 위해 탐색 시 마다 탐색 여부 저장

4. 석유 덩어리 크기 구하기 (BFS)

   -> 상하좌우 탐색 중에 처음 탐색하는 땅이고 석유가 있는 땅은 Queue에 다시 Add 하여 상하좌우 탐색 반복

   -> 재 탐색 방지를 위해 탐색 시 마다 탐색 여부 저장

   -> 석유가 포함된 열 저장 (oilCols[n] = true)

   -> 석유 덩어리 양 저장 (oilCnt++)

5. 탐색 중이던  석유 덩어리의 탐색이 완료되면 석유 덩어리 정보 저장 후 3번 부터 다시 시작

    -> 탐색된 석유 덩어리 크기 열 별 합산  (oilCnts[n] += oilCnt)

6. 모든 땅 탐색이 완료 되면 열 별 석유량 정렬하여, 가장 많은 석유량 return

Java 코드

import java.util.*;

class Solution {
    public int solution(int[][] land) {
        int answer = 0;
        
        int landH = land.length;
        int landV = land[0].length;
        
        int[] dfsX = {0, 0, -1, 1};
        int[] dfsY = {-1, 1, 0, 0};
        
        boolean[][] checkedLand = new boolean[landH][landV];
        Queue<int[]> que = new LinkedList<>();
        
        int[] oilCnts = new int[landV];
        
        boolean[] oilCols;
        int[] now;
        int oilCnt, x, y;
        
        for(int i = 0; i < landH; i++) {
            for(int j = 0; j < landV; j++) {
                
                // 이미 탐색한 곳이면 pass
                if(checkedLand[i][j]) continue;
                
                // 탐색 여부 저장
                checkedLand[i][j] = true;
                
                // 석유가 없으면 pass
                if(land[i][j] != 1) continue;
                
                oilCnt = 1;
                oilCols = new boolean[landV];
                oilCols[j] = true;
                
                // 탐색용 큐에 추가
                que.add(new int[]{i, j});

                while(!que.isEmpty()) {
                    now = que.poll();
                    y = now[0];
                    x = now[1];

                    // 상하좌우 탐색
                    for(int k = 0; k < 4; k++) {
                        if((y + dfsY[k]) < 0 || (y + dfsY[k]) >= landH      // 상하 범위 이탈
                           || (x + dfsX[k]) < 0 || (x + dfsX[k]) >= landV   // 좌우 범위 이탈
                           || checkedLand[y + dfsY[k]][x + dfsX[k]]         // 이미 탐색
                          ) continue;
                        
                        // 탐색 여부 저장
                        checkedLand[y + dfsY[k]][x + dfsX[k]] = true;
                        
                        // 석유가 없으면 pass
                        if(land[y + dfsY[k]][x + dfsX[k]] != 1) continue;   

                        // 탐색 필요 큐에 추가
                        que.add(new int[]{y + dfsY[k], x + dfsX[k]});

                        // 현재 탐색 석유 증가처리
                        oilCnt++;
                        
                        // 탐색 col 저장
                        oilCols[x + dfsX[k]] = true;
                    }
                }
                
                for(int l = 0; l < oilCols.length; l++){
                    if(oilCols[l]) {
                        oilCnts[l] += oilCnt;
                    }
                }
            }
        }
        
        Arrays.sort(oilCnts);
        answer = oilCnts[oilCnts.length - 1];
        
        return answer;
    }
}

문제 출처

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