<stdio.han>

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

[난이도]

- Silver 4

[알고리즘]

- 이분탐색

[코드]

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

public class Main {
    static int T, N, M;
    static int[] noteOne;
    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;

        T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            N = Integer.parseInt(br.readLine());
            noteOne = new int[N];
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                noteOne[j] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(noteOne);
            M = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine(), " ");
            for (int k = 0; k < M; k++) {
                int num = Integer.parseInt(st.nextToken());
                if (binarySearch(num)) {
                    bw.write("1\n");
                } else {
                    bw.write("0\n");
                }
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }

    static boolean binarySearch(int num) {
        int left = 0;
        int right = N - 1;
        while (left <= right) { // left인덱스가 right인덱스를 넘어가기 전 까지 반복
            int mid = (left + right) / 2;
            if (num > noteOne[mid]) {
                left = mid + 1;
            } else if (num < noteOne[mid]) {
                right = mid - 1;
            } else { // num == noteOne[mid]
                return true;
            }
        }
        return false;
    }
}

[풀이]

가장 기본적인 이분탐색 문제이다. 중요한 점은 출력 시 System.out.println()을 하면 시간초과가 발생한다. 효율이 안좋기 때문에 BufferedWriter를 사용해주자.

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

[난이도]

- Silver 5

[알고리즘]

- 이분탐색

[코드]

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

public class Main {
    static int N, M;
    static int[] sangArr;
    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;

        N = Integer.parseInt(br.readLine());
        sangArr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            sangArr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(sangArr); // 오름차순 정렬

        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st.nextToken());
            if (binarySearch(num)) {
                bw.write("1 ");
            } else {
                bw.write("0 ");
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }

    static boolean binarySearch(int num) {
        int leftIndex = 0;
        int rightIndex = N - 1;
        while (leftIndex <= rightIndex) {
            int midIndex = (leftIndex + rightIndex) / 2;
            int mid = sangArr[midIndex];

            if (num < mid) { // 찾으려는 숫자가 더 작을경우 rightIndex를 mid-1 로 설정
                rightIndex = midIndex - 1;
            } else if (num > mid) { // 찾으려는 숫자가 더 클경우 leftIndex mid+1 로 설정
                leftIndex = midIndex + 1;
            } else { // 숫자가 있을 경우
                return true;
            }
        }
        return false; // 숫자가 없을 경우
    }
}

[풀이]

일반적인 이분탐색 문제이다. midIndex와 mid값이 다르기 때문에 탐색은 인덱스 기준으로하고 찾는 숫자는 arr[midIndex]로 찾는다.

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});

• 메서드 이름을 신중히 짓자.
  • 표준 명명 규칙을 따라야 한다. 이해할 수 있고, 일관되게 지어야 한다.
• 편의 메서드를 너무 많이 만들지 말자.
  • 메서드가 너무 많은 클래스는 익히고, 사용하고 문서화하고, 테스트하고, 유지보수하기 어렵다.
• 매개변수 목록은 짧게 유지하자.
  • 4개 이하가 좋다. 4개가 넘어가면 기억하기 쉽지 않다. 같은 타입의 매개변수 여러 개가 연달아 나오는 경우가 특히 해롭다.
• 매개변수의 타입으로는 클래스보다는 인터페이스가 더 낫다.
  • 매개변수로 적합한 인터페이스가 있다면 그 인터페이스를 직접 사용하자. 예를 들어 메서드에 HashMap을 넘길 일은 전혀 없다면 Map을 사용하자.
• boolean보다는 원소 2개 짜리 열거 타입이 낫다.
  • 열거 타입을 사용하면 코드를 읽고 쓰기가 더 쉬워진다.

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;
            }