취업 코딩테스트 대비

import java.util.*;

// BFS — 최단 경로
public int bfs(int[][] grid, int r, int c) {
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[]{0, 0, 0}); // row, col, dist
    boolean[][] visited = new boolean[r][c];
    visited[0][0] = true;
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        if (cur[0] == r-1 && cur[1] == c-1) return cur[2];
        for (int[] d : dirs) {
            int nr = cur[0]+d[0], nc = cur[1]+d[1];
            if (nr>=0 && nr<r && nc>=0 && nc<c
                    && !visited[nr][nc] && grid[nr][nc]==1) {
                visited[nr][nc] = true;
                q.offer(new int[]{nr, nc, cur[2]+1});
            }
        }
    }
    return -1;
}

// 이분탐색
public int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// 자주 쓰는 패턴
// 문자열 역순: new StringBuilder(s).reverse().toString()
// 정렬: Arrays.sort(arr, (a,b) -> b-a) // 내림차순
// HashMap 빈도 카운트: map.merge(key, 1, Integer::sum)