<stdio.han>

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

[정답 코드]

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

public class Main {
    static char[][] board;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        String input = "";
        board = new char[3][3];
        while (true) {
            st = new StringTokenizer(br.readLine(), " ");
            input = st.nextToken();
            if (Objects.equals(input, "end")) {
                break;
            }
            int index = 0;
            int xCount = 0;
            int oCount = 0;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    board[i][j] = input.charAt(index);
                    if (board[i][j] == 'O') {
                        oCount++;
                    } else if (board[i][j] == 'X') {
                        xCount++;
                    }
                    index++;
                }
            }
            //게임판이 꽉 채워졌을 때
            //X가 먼저 말을 놓았음으로 O보다 1개 무조건 많아야 한다.
            if (xCount + oCount == 9 && xCount - oCount == 1) {
                //한 명이 빙고를 완성하면 게임이 끝나기 때문에
                //둘 다 빙고가 성립될 수 없다.
                if (isValid('X') && isValid('O')) {
                    bw.write("invalid\n");
                } else if (isValid('O')) {//말이 꽉 채워진 경우에는 O가 이길 수 없다
                    bw.write("invalid\n");
                } else { // X 가 이긴경우
                    bw.write("valid\n");
                }
            } else { // 게임판이 꽉 채워지지 않았을 경우
                //한 명이 빙고를 완성하면 게임이 끝나기 때문에
                //둘 다 빙고가 성립될 수 없다.
                if (isValid('X') && isValid('O')) {
                    bw.write("invalid\n");
                } else if (isValid('X') && xCount - oCount == 1) { //X가 이겼을 땐, X가 선공이어서 무조건 O보다 하나 많아야 한다
                    bw.write("valid\n");
                } else if (isValid('O') && xCount == oCount) { //O가 이겼을 땐, O가 후공이여서 X와 O의 개수가 같아야 한다
                    bw.write("valid\n");
                } else { // 아직 게임판이 덜채워졌는데 게임이 끝날 수는 없다
                    bw.write("invalid\n");
                }
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }

    public static boolean isValid(char c) {
        //가로가 성립할 때
        for (int i = 0; i < 3; i++) {
            int count = 0;
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == c) {
                    count++;
                }
            }
            if (count == 3) {
                return true;
            }
        }

        //세로가 성립할 때
        for (int i = 0; i < 3; i++) {
            int count = 0;
            for (int j = 0; j < 3; j++) {
                if (board[j][i] == c) {
                    count++;
                }
            }
            if (count == 3) {
                return true;
            }
        }

        // 대각선이 성립할 때
        if (board[0][0] == c && board[1][1] == c && board[2][2] == c) {
            return true;
        }
        if (board[0][2] == c && board[1][1] == c && board[2][0] == c) {
            return true;
        }

        return false;
    }
}

[설명]

단순 구현 문제이다. 크게 봤을 때는 게임판에 말이 가득 찼을 경우와 가득차지 않았을 경우로 나눌수 있다.

1. 말이 가득찼을 경우(X가 무조건 O보다 한개 많다)
   • X와 O둘다 동시에 이길 수는 없다
   • O가 이길수는 없다
   • X가 이긴다
   • 둘다 못 이긴다
2. 말이 가득차지 않았을 경우
   • X와 O둘다 동시에 이길 수는 없다
   • X가 이겼을 땐 X가 선공이라 X가 O보다 1개 많아야 한다
   • O가 이겼을 땐 O가 후공이라 X와 O는 같아야 한다
   • 아직 게임판이 덜 채워졌는데 게임이 끝날 수는 없다

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

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int T = Integer.parseInt(st.nextToken());
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            for (int j = 0; j < M; j++) {
                st = new StringTokenizer(br.readLine(), " ");
            }
            System.out.println(N - 1);
        }
    }
}

[설명]

문제를 풀면서 뭔가 좀 이상함을 느꼈었다. 문제가 이해하기 어렵게 적혀있지만 결국에는 노드와 간선의 관계를 물어보는 문제였다. 노드가 N개 있고 노드끼리 모드 연결되어있게하려면 간선은 최소 N - 1개 있어야한다는걸 알고있냐는 질문이였다. 비행기를 타는 최소 횟수 같은걸 물어보는거였다면 문제를 다르게 풀어야 했겠지만 그냥 비행기의 종류가 몇개냐는 물어보는거였기 때문에 정답 코드가 이렇다.

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

[정답 코드]

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

public class Main {
    static int n, num;
    static int[] arr;
    static boolean[] check;
    static List<Integer> answer;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        check = new boolean[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine()) - 1;
        }
        answer = new LinkedList<>(); // 답은 가변적이므로 리스트로 선언

        for (int i = 0; i < N; i++) {
            check[i] = true;
            num = i;
            dfs(i);
            check[i] = false;
        }
        Collections.sort(answer);
        System.out.println(answer.size());
        for (Integer integer : answer) {
            System.out.println(integer + 1);
        }
    }

    public static void dfs(int i) {
        if (arr[i] == num) { // 한바퀴돌아 다시 제자리로 돌아오는지 체크
            answer.add(num); // 돌아온다면 정답에 추가
        }
        if (!check[arr[i]]) {
            check[arr[i]] = true;
            dfs(arr[i]);
            check[arr[i]] = false;
        }
    }
}

[설명]

난이도가 높아질수록 문제를 이해하는것 자체부터가 힘들어진다. for문을 N번 만큼 돌면서 dfs 로직을 실행시켜준다.

dfs로직은 출발 숫자 -> arr[출발 숫자] -> arr[arr[출발 숫자]] 를 반복하다 출발 숫자를 다시 만나게 되면 첫째 줄과 둘째 줄 정수들의 집합이 일치한다고 볼 수 있다. 

for문을 N번 만큼 실행시키는 이유는 최대값을 찾기 위해서이다.

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

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

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

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int left = 0;
        int right = N - 1;
        int min = Integer.MAX_VALUE; // 현재 알고있는 최솟값
        int[] answer = new int[2];
        while (left < right) {
            int sum = Math.abs(arr[left] + arr[right]); // 새로운 최솟값
            if (sum < min) { // 새로운 최솟값이 원래 알고있는 최솟값보다 더 작다면 갱신
                min = sum;
                answer[0] = arr[left];
                answer[1] = arr[right];
            }
            if (sum == 0) {
                break;
            }
            if (arr[left] + arr[right] > 0) {
                right--;
            } else {
                left++;
            }
        }
        System.out.println(answer[0] + " " + answer[1]);
    }
}

[설명]

간단한 이분탐색 알고리즘 문제이다. 다른 이분탐색 알고리즘과 다른점은 left 와 right 가 arr배열의 인덱스 내에서만 이루어져야만 한다는것을 조심해야한다.

left는 0 (첫번째 인덱스), right는 N - 1 (마지막 인덱스)로 초기화하고 left가 right를 넘어갈때 까지 반복한다.

left 와 right를 더한 값이 0 이상일 경우 right-- 아닐 경우 left ++ 한다.

혹은 0 일경우 바로 출력한다.

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

[정답 코드]

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

public class Main {
    public static int N, M;
    public static ArrayList<ArrayList<Node>> graph = new ArrayList<>(); // 2차원 ArrayList 로 graph 를 구현(2차원 배열처럼)
    public static boolean[] visited;
    public static int[] d = new int[50001];
    public static int answer = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        visited = new boolean[N];

        //ArrayList 초기화
        for(int i=0;i<=N;i++) {
            graph.add(new ArrayList<>());
        }

        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()); // 시작 노드
            int b = Integer.parseInt(st.nextToken()); // 끝 노드
            int dist = Integer.parseInt(st.nextToken()); // 비용

            // 양방향 간선
            graph.get(a).add(new Node(b, dist)); // a 에서 b 까지의 가중치 dist
            graph.get(b).add(new Node(a, dist)); // b 에서 a 까지의 가중치 dist
        }

        //1부터 N 까지의 최소거리 구하기
        dijkstra(1);

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

    public static void dijkstra(int start) {
        Arrays.fill(d, Integer.MAX_VALUE); // d 배열의 모든 요소를 Integer.MAX_VALUE 로 채워줌

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0)); // 시작노드에서 시작노드로 가기위한 최단 경로는 0
        d[start] = 0; // 시작노드에서 시작노드까지의 가중치는 제자리 이므로 0

        while (!pq.isEmpty()) {
            Node temp = pq.poll();
            int nodeB = temp.nodeB; // 현재 노드번호
            int distance = temp.distance; // 현재 노드의 가중치

            if(d[nodeB] < distance) continue; // //현재 노드가 이미 처리된적이 있는 노드라면 무시 ( 거리가 더 작다는것은 이미 더 효율적인 방안으로 처리된 것 )
            for(int i=0;i<graph.get(nodeB).size();i++) { //현재 노드와 연결된 다른 인접한 노드들을 확인
                int cost = d[nodeB] + graph.get(nodeB).get(i).distance; // cost = 현재노드의 가중치 + 현재노드와 다음 노드까지의 간선의 가중치
                if( cost < d[graph.get(nodeB).get(i).nodeB]) { // 새롭게 측정한 비용이 다음 노드가 원래 가지고 있던 가중치보다 적을 경우
                    d[graph.get(nodeB).get(i).nodeB] = cost; // 더 적은 값으로 갱신해준다
                    pq.offer(new Node( graph.get(nodeB).get(i).nodeB, cost)); // 계속 탐색을 해봐야 모든 노드들의 최솟값을 알 수 있기 때문에 현재의 가중치를 가지고 계속 탐색
                }
            }
        }
    }

}


// 그래프의 간선을 표현하기 위한 클래스
class Node implements Comparable<Node>{
    int nodeB; // 이 간선이 연결하는 목적지 노드의 번호
    int distance; // 시작노드에서 nodeB 까지의 가중치
    public Node(int nodeB, int distance) {
        this.nodeB = nodeB;
        this.distance = distance;
    }

    // Node 인스턴스 끼리 비교할 때 사용
    // 우선순위 큐에 삽입되었을 때 distance 값이 작은 노드(가장 가까운 노드) 부터 우선순위가 높게 설정되어 먼저 처리된다
    @Override
    public int compareTo(Node other) {
        if(this.distance > other.distance) {
            return 1;
        }else if(this.distance == other.distance) {
            return 0;
        }else {
            return -1;
        }
    }
}

[설명]

이 문제는 다익스트라 알고리즘을 활용해 푸는 기본적인 문제이다. 코드는 다른사람의 코드를 참고했다. 

graph 를 이중 ArrayList로 선언해주고 노드끼리의 가중치를 초기화 해준다. 

graph는 이런형태로 값이 저장된다. 

코드에 주석을 자세히 달아 놨으므로 코드와 주석을 동시에 보면서 확인하면 이해가 쉽다.

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

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        int[] arr = new int[W];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < W; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int answer = 0;

        for (int i = 1; i < W - 1; i++) { // 처음벽과 마지막벽에는 물이 고일수 없다
            int current = arr[i]; // 현재 벽의 높이
            int leftMax = current; // 왼쪽 벽
            int rightMax = current; // 오른쪽 벽
            for (int j = i - 1; j >= 0; j--) { // 왼쪽 벽 최대 높이 탐색
                if (arr[j] > current) {
                    leftMax = Math.max(leftMax, arr[j]);
                }
            }
            for (int j = i + 1; j < W; j++) { // 오른쪽 벽 최대 높이 탐색
                if (arr[j] > current) {
                    rightMax = Math.max(rightMax, arr[j]);
                }
            }
            if (Math.min(leftMax, rightMax) > current) { // 현재 벽보다 높은 벽이 양쪽에 있는 경우
                answer += (Math.min(leftMax, rightMax) - arr[i]);
            }
        }
        System.out.println(answer);
    }
}

[설명]

처음에는 구현문제가 쉬운 문제인줄 알았는데 풀면 풀 수록 구현 문제도 어렵다는걸 깨달았다. 이 문제는 다른 블로그들을 대부분 참고했다.

문제 풀이방법은 for문을 돌며 현재 벽 기준으로 왼쪽 벽 중 가장 높은벽과 가장 높은 오른쪽 벽을 구한 후, 그 벽들이 현재 벽보다 높을 경우 빗물이 고이기 때문에 높은 벽에서 현재 벽을 빼주면 그 차이 만큼 빗물이 쌓인다.

이때 문제의 핵심은 두가지가 있다.

1. 가장 왼쪽벽과 가장 오른쪽 벽에는 빗물이 고일 수 없다.

그래서 for문을 돌릴때 i = 1부터 시작되고 끝은 W - 1까지 한다. 

2. 현재 벽보다 높은 양쪽 벽중에 더 낮은 벽 기준으로 빗물이 고인다.

예를 들면 빨간 체크한 벽이 for문에서 현재 current 라고 했을 때, 왼쪽벽 중 가장 높은벽은 4 이고 오른쪽벽 중  가장 높은 벽은 2이다. 이때 그림으로 보면 알 수 있듯이 왼쪽벽을 기준으로 계산하는게 아닌 오른쪽 벽을 기준으로 계산해야 한다.

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

[정답코드]

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

public class Main {
    static int[][] graph;
    static boolean[][] visited;
    static int[][] result;
    static int n, m;
    static int[] dx = {-1, 1, 0, 0}; // 상,하,좌,우
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new int[n][m];
        visited = new boolean[n][m];
        result = new int[n][m];
        int x=0, y=0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                if (graph[i][j] == 2) {
                    x = i;
                    y = j;
                } else if (graph[i][j] == 0) {
                    visited[i][j] = true;
                }
            }
        }
        bfs(x, y);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j]) {
                    result[i][j] = -1;
                }
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int tmp[] = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = tmp[0] + dx[i];
                int ny = tmp[1] + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (!visited[nx][ny] && graph[nx][ny] == 1) {
                        visited[nx][ny] = true;
                        result[nx][ny] = result[tmp[0]][tmp[1]] + 1;
                        queue.add(new int[]{nx, ny});
                    }
                }
            }
        }
    }
}

[설명]

bfs를 활용해야하는 문제이다. 시작지점의 위치를 입력받고 입력받은 위치를 큐에 넣고 bfs로직을 돌려준다.

bfs로직은 입력받은 x, y 를 큐에 넣고  해당 위치를 기준으로 4방탐색을 한다. 4방탐색을 했을 때 방문하지않은장소이고, 갈 수 있는 장소이고, 지도 내에 있다면 visited를 true로 변경해주고, 새로 탐색한 위치의 값을 이동할 때 마다 1씩 증가시켜준다. 그리고 새로탐색한 위치를 큐에 넣어준다.

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

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int X = Integer.parseInt(st.nextToken());
        int Y = Integer.parseInt(st.nextToken());
        int Z = (int) ((long) Y * 100 / X);
        int answer = -1;
        int left = 0;
        int right = (int) 1e9; // 범위는 문제에서 주어짐
        while (left <= right) { // left가 right를 넘어서면 종료
            int mid = (left + right) / 2;
            int newRate = (int) ((long) (Y + mid) * 100 / (X + mid));
            if (newRate != Z) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(answer);
    }
}

[설명]

이 문제는 이분탐색 문제이다. 처음에 이 문제를 풀 때 오른쪽 끝 범위를 몇으로 정해야 하는지 몰라 잠깐 막혔는데 문제에서 X의 범위는 10억이라고 정해줬다. 간단하게 알고리즘을 설명하자면

1. 범위내의 중간 값 mid 를 초기화해주고 X 외 Y 에 각각 mid를 더했을 때의 승률을 새로 구해준다.

2 - 1. 승률이 변했다면 횟수를 더 줄여야 하기 때문에 right = mid - 1 을 해준다.

2 - 2. 승률이 안변했다면 횟수를 더 늘여야 하기 때문에 left = mid + 1 을 해준다.

생각보다 간단한데 막상 아이디어가 떠오르지 않는다.