<stdio.han>

[문제 링크]

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

[난이도]

- Level 2

[알고리즘]

- 구현

- 배열

[코드]

import java.util.*;

class Solution {
    public String[] solution(int[][] line) {
        long maxX = Long.MIN_VALUE;
        long maxY = Long.MIN_VALUE;
        long minX = Long.MAX_VALUE;
        long minY = Long.MAX_VALUE;

        List<long[]> list = new ArrayList<>();

        for (int i = 0; i < line.length - 1; i++) {
            for (int j = i + 1; j < line.length; j++) {
                long A = line[i][0];
                long B = line[i][1];
                long E = line[i][2];
                long C = line[j][0];
                long D = line[j][1];
                long F = line[j][2];

                long denominator = A * D - B * C;

                if (denominator == 0) continue;  // 평행 또는 동일 직선

                long numeratorX = B * F - E * D;
                long numeratorY = E * C - A * F;

                // 정수 교차점인지 확인
                if (numeratorX % denominator != 0 || numeratorY % denominator != 0) continue;

                long x = numeratorX / denominator;
                long y = numeratorY / denominator;

                maxX = Math.max(maxX, x);
                maxY = Math.max(maxY, y);
                minX = Math.min(minX, x);
                minY = Math.min(minY, y);

                list.add(new long[]{x, y});
            }
        }

        int width = (int)(maxX - minX + 1);
        int height = (int)(maxY - minY + 1);

        char[][] graph = new char[height][width];
        for (char[] row : graph) {
            Arrays.fill(row, '.');
        }

        for (long[] point : list) {
            int x = (int)(point[0] - minX);
            int y = (int)(maxY - point[1]);  // y축 뒤집기

            graph[y][x] = '*';
        }

        String[] answer = new String[height];
        for (int i = 0; i < height; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < width; j++) {
                sb.append(graph[i][j]);
            }
            answer[i] = sb.toString();
        }

        return answer;
    }
}

[풀이]

단순 구현 문제이다. 중요한점은 int가 아닌 long타입으로 변환해서 풀어야한다는것이다. 그 이유는 int*int가 int의 범위를 벗어나는 경우가 있어 테스트케이스29번을 통과하지 못하기 때문이다.

[문제 링크]

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

[난이도]

- Level 1

[알고리즘]

- 구현

[코드]

class Solution {
    public int solution(int[] schedules, int[][] timelogs, int startday) {
        int answer = 0;
        boolean flag = false;
        for(int i=0;i<schedules.length;i++){
            int time = function(schedules[i]);
            flag = false;
            for(int j=0;j<7;j++){
               if(j == 7-startday || j == 6-startday){
                   continue;
               }
                if(6-startday == -1){
                    if(j==6){
                        continue;
                    }
                }

                
                if(timelogs[i][j]>time){
                    flag = true;
                    break;
                }
            }
            if(!flag){
                answer++;
            }
        }
        return answer;
    }
    static int function(int time){
        int min = time%100;
        int hour = time/100;
        int newMin = min+10;
        if(newMin>=60){
            newMin -=60;
            hour++;
        }
        int newTime = hour*100 + newMin;
        return newTime;
    }
}

[풀이]

단순 구현 문제이다. 토요일과 일요일이 위치할 배열을 고르는 법은 6 - startday, 7-startday이다. 중요한점은 startday가 7일때를 고려해야한다. 이때 토요일은 배열의 마지막에 위치하기 때문에 한 번 더 if문으로 해결했다.

10분이 지난시간이 60분을 넘길때를 고려해주어야 한다. 

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

[난이도]

- level 2

[알고리즘]

- BFS

[코드]

import java.util.*;

class Solution {
    static int answer = -1; // 우측하단에 도착하지못할경우 -1출력
    public int solution(int[][] maps) {
        bfs(maps);
        
        return answer;
    }
    static void bfs(int[][] maps){
        int n = maps.length;
        int m = maps[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 1});
        boolean[][] visited = new boolean[n][m];
        visited[0][0] = true;
        int[] dx = {-1, 1, 0, 0}; // 4방탐색
        int[] dy = {0, 0, -1, 1};
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int count = tmp[2];
            if(x == n-1 && y == m-1){ // 우측하단에 도착했을 경우
                answer = count;
                return;
            }
            for(int i=0;i<4;i++) { // 4방탐색
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx>=0&&nx<n&&ny>=0&&ny<m){ // 지도 내에 있을 경우
                    if(!visited[nx][ny] && maps[nx][ny] == 1){ // 방문한 적 없고, 벽이 아닐경우
                        queue.offer(new int[]{nx, ny, count+1});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        return;
    }
}

[풀이]

일반적인 미로찾기 BFS 알고리즘이다. 

큐에 x좌표, y좌표, 밟은블럭의 수를 담아준다.

queue.offer(new int[]{x, y, count});

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

[난이도]

- level 2

[알고리즘]

- BFS

[코드]

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

class Solution {
    static char[][] graph;
    static int n, m, answer = 0;
    static boolean[][] visited;
    static Queue<int[]> queue = new LinkedList<>();
    static int[] dx = {-1, 1, 0, 0}; // 상, 하
    static int[] dy = {0, 0, -1, 1}; // 좌, 우 4방탐색
    static boolean lever = false;
    public int solution(String[] maps) {
        n = maps.length;
        m = maps[0].length();
        visited = new boolean[n][m];
        graph = new char[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                graph[i][j] = maps[i].charAt(j);
                if(graph[i][j] == 'S'){
                    queue.offer(new int[]{i, j, 0});
                    visited[i][j] = true;
                }
            }
        }
        bfs();
    
        return answer;
    }
    static void bfs(){
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int count = tmp[2];
            if(!lever&&graph[x][y] == 'L') { // 레버에 도착했을 경우, 레버를 아직 안켰을경우
                visited = new boolean[n][m];
                queue.clear();
                queue.offer(new int[]{x, y, count});
                visited[x][y] = true;
                lever = true;
            } else if(lever && graph[x][y] == 'E'){ // 레버를 켠 후 출구에 도착했을 경우
                answer = count;
                return;
            }
            for(int i=0;i<4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx>=0&&nx<n&&ny>=0&&ny<m){ // 맵 범위 내에 있을 경우
                    if(!visited[nx][ny] && graph[nx][ny] != 'X'){ // 방문한 적이 없고 벽이 아닐경우
                        queue.offer(new int[]{nx, ny, count+1});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        answer = -1;
        return;
    }
}

[풀이]

일반적인 BFS와 같지만 두 가지의 조건을 추가했다.

레버에 처음 도착했을경우 visited 배열을 다시 초기화해준다. 이유는 레버를 켠 후부터는 방문했던칸을 다시 방문해도 되기 때문이다.

queue를 queue.clear()메서드로 모두 비워준다. 레버에 도착한 순간 큐에담겨있던 데이터들은 쓸모없는 데이터들이기 때문이다.

레버를 켰다는 표시인 lever = true; 해준다.

if(!lever&&graph[x][y] == 'L') { // 레버에 도착했을 경우, 레버를 아직 안켰을경우
                visited = new boolean[n][m];
                queue.clear();
                queue.offer(new int[]{x, y, count});
                visited[x][y] = true;
                lever = true;
            }

lever를 켜서 lever = true로 된상태이면서 출구('E')에 도착했을 경우 answer = count; 해준 후 return으로 종료해준다.

else if(lever && graph[x][y] == 'E'){ // 레버를 켠 후 출구에 도착했을 경우
                answer = count;
                return;
            }

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

[난이도]

- level 2

[알고리즘]

- BFS

[코드]

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

class Solution {
    public int solution(String[] board) {
        int answer = 0;
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        boolean[][] visited = new boolean[board.length][board[0].length()];
        Queue<int[]> queue = new LinkedList<>();
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length();j++){
                if(board[i].charAt(j) == 'R')
                { // 시작위치 저장
                    queue.offer(new int[]{i, j, 0});
                    visited[i][j] = true;
                }   
            }
        }
        
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int count = tmp[2];
            if(board[x].charAt(y) == 'G'){
                answer = count;
                return answer;
            }
            for(int i=0;i<4;i++){
                int nx = x;
                int ny = y;
                while(nx>=0&&nx<board.length&&ny>=0&&ny<board[0].length()&&board[nx].charAt(ny) != 'D'){ // 범위내에 있거나, 장애물 'D' 를 만날때 까지 계속 이동
                    nx += dx[i];
                    ny += dy[i];
                }
                // 범위 벗어나거나 장애물 만나기 직전으로 수정
                nx -= dx[i];
                ny -= dy[i];
                
                if(visited[nx][ny] || (x == nx && y == ny)){ // 방문한 적이 없고 같은 위치가 아닐경우
                    continue;
                    
                }
                    visited[nx][ny] = true;
                    queue.offer(new int[]{nx, ny, count+1});
                }
            }
        answer = -1;
        return answer;
    }
}

[풀이]

일반적인 bfs, 4방탐색 알고리즘을 활용한 문제이다.

다른점이 있다면 4방탐색 시 한 칸만 움직이는게 아닌 장애물을 만나거나 범위를 벗어나기전까지 계속 움직여야 한다는점이다.

                while(nx>=0&&nx<board.length&&ny>=0&&ny<board[0].length()&&board[nx].charAt(ny) != 'D'){ // 범위내에 있거나, 장애물 'D' 를 만날때 까지 계속 이동
                    nx += dx[i];
                    ny += dy[i];
                }
                // 범위 벗어나거나 장애물 만나기 직전으로 수정
                nx -= dx[i];
                ny -= dy[i];

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

[시행 착오]

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        String basket = "0";
        for(int i=0;i<moves.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[j][moves[i] - 1] != 0){
                    int tmp = board[j][moves[i] - 1];
                    board[j][moves[i] - 1] = 0;
                    if(basket.substring(basket.length()-1).equals(Integer.toString(tmp))){
                        answer+=2;
                        basket = basket.substring(0,basket.length()-1);
                        break;
                    } else {
                        basket += (String.valueOf(tmp));
                    }
                    break;
                }
            }
        }
        return answer;
    }
}

[정답 코드]

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        Stack<Integer> stack = new Stack<>();
        
        for(int i=0;i<moves.length;i++){
            for(int j=0;j<board.length;j++){
                if(board[j][moves[i]-1] != 0){
                    if(!stack.empty() && stack.peek() == board[j][moves[i]-1]){
                        answer+=2;
                        stack.pop();
                            board[j][moves[i]-1]=0;
                        break;
                    } else {
                        stack.push(board[j][moves[i]-1]);
                        board[j][moves[i]-1]=0;
                        break;
                    }
                } 
            }
        }     
        return answer;
    }
}

[설명]

이 문제는 시물레이션 문제로 보기에는 어려워 보이지만 생각보다 쉬운 문제라고 생각한다.

아이디어는 크레인이 인형을 뽑을 때마다 해당 위치에 가장 위에 쌓여있는 인형을 뽑은 후 해당 위치를 0 으로 변경해준다.

뽑은 인형은 stack에 담고, stack.peek() 함수를 사용해 stack의 가장 최근 숫자를 확인 후 뽑은 인형과 같다면 stack.pop()을 해 스택에서 제거해준다.

이론은 간단한데 처음에 틀렸던 이유는 스택을 사용하면 쉬운데 스택이 순간 생각나지 않아서 문자열로 풀다가 문제 일부분만 맞았었다. 문자열의 마지막숫자와 뽑은 인형을 비교해 나가는 로직이였는데 안되는 이유는 문제에서 인형의 번호가 0~100 까지 존재해 문자열의 마지막숫자로 비교하면 틀리게 되는것이였다.