IT LAB

난이도 : Gold 2 문제링크 5*5 격자판이 5개 쌓인 3차원 미로가 존재한다 (5*5*5) 주어진 5개의 격자판을 임의의 순서대로 쌓아 퍼즐을 만든다. 맨 위 격자의 좌측 상단(0, 0)에서 맨 아래 격자의 우측 하단까지(4, 4) 도착하는데 걸리는 최단 이동 횟수를 구하라 격자는 회전가능하며, 벽은 이동할 수 없음 해설 전체코드 보기 1. 퍼즐을 만들 수 있는 모든 경우 탐색하기 private static void dfs(int depth, int[][][] curMaze) { if (depth == height) { if (curMaze[0][0][0] == 1 && curMaze[4][4][4] == 1) { int turn = bfs(curMaze, new boolean[height][row..

난이도 : Level 3 문제링크 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채워야 한다 보드의 빈공간과 조각은 딱 맞아떨어져야 한다 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 리턴하라 조각을 회전시킬 수 있음 조각끼리는 서로 인접할 수 없다 해설 game_board에 있는 빈칸들과 table에 있는 퍼즐들을 각각 List에 담습니다 각각 인접한 빈칸과 퍼즐을 (0, 0)에서 시작하는 리사이징 2차원 배열을 생성하고 list에 담습니다. 빈칸과 퍼즐을 비교하기 위함입니다. 빈칸에 현재 가지고 있는 퍼즐들을 하나씩 맞춰보면서 딱 맞으면 퍼즐의 갯수만큼 누적합을 계산합니다. 퍼즐에 빈칸이 맞지 않으면 시계방향으로 90도 회전해 봅니다 회전해도 맞지 않다면 해당 퍼즐은 빈칸..

난이도 : Level 3 문제링크 캐릭터가 아이템을 줍기 위해 이동함 캐릭터는 지형의 가장 바깥쪽 테두리를 따라 이동함 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 리턴하라 각 지형은 직사각형으로 지형들끼리 서로 겹쳐져있다 서로 다른 두 지형들이 x축 또는 y축 좌표가 같은 경우는 없음 두개 이상 분리된 경우도 없음 한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우도 없음 해설 이동할 수 있는 경계 좌표만 이동할 수 있도록 좌표를 가진 2차원 boolean 배열에 경계좌표를 체크함 이동할 수 없는 사각형 내의 좌표들을 캐릭터가 다음 턴에 내부 좌표에 이동하지 못하도록 방문처리함 import java.util.*; class Solution { int m, n; boolean[][] ..

난이도 : hard 문제링크 두개의 문자열이 주어진다 : beginWord, endWord 한개의 문자열 리스트가 주어진다 : wordList 이웃한 한 단어 차이만 나는 단어의 쌍들끼리 변환될 수 있다 beginWord에서 endWord로 변환할 때, 가장 적은 수의 변환의 수를 리턴하라 1. 접근법 최소 변환수를 구해야 하므로 큐를 사용하여 BFS 탐색으로 모든 경우를 탐색한다 큐에서 꺼낸 단어와 한글자 차이나는 단어들을 큐에 넣고, 큐가 빌때까지 반복한다 한번 탐색한 단어는 다시 탐색하지 않도록 방문단어들을 Set에 저장해둔다 3. 구현 코드 class Node { String word; int turn; Node (String word, int turn) { this.word = word; thi..

난이도 : hard 문제링크 2차원 문자 배열 board와 문자열 배열 words가 주어짐 board에 존재하는 모든 word를 리턴하라 word는 words에 해당하는 문자열을 가리킴 board에 인접한 문자들을 가지고 word를 만들 수 있음 1. 접근법 모든 좌표를 시작점으로 word가 될 수 있는지 확인한다 인접한 문자들로 구성된 문자열이 word라면 결과에 추가한다 3. 구현 코드 int r, c, wordIdx; char ch1; int[] dy, dx; Set answer; public List findWords(char[][] board, String[] words) { r = board.length; c = board[0].length; dy = new int[] {1, 0, -1, 0}..

난이도 : medium 문제링크 정수형 배열 nums가 주어진다 오름차순으로 정렬되기 위한 첫번째 회전 요소를 리턴하라. O(logn) 의 시간복잡도 알고리즘을 작성할 것. 1. 접근법 이진 탐색을 통해 정렬이 뒤바뀌는 인덱스를 찾는다. 이진탐색 범위의 양끝점의 정렬여부를 통해 다음 중간 인덱스를 결정한다. 3. 구현 코드 public int findMin(int[] nums) { if (nums.length == 1) { return nums[0]; } if (nums.length == 2) { return nums[0] < nums[1] ? nums[0] : nums[1]; } int length = nums.length; int left = 0, right = length-1, mid = 0; if..

난이도 : medium 문제링크 정수형 배열 nums이 주어진다 오름차순으로 정렬되었으며 각 요소들은 유일하다 k 번째 인덱스를 기준으로 회전될 수 있다 target의 인덱스를 리턴하라 O(logn)의 시간복잡도를 가지는 알고리즘으로 작성해야 한다 3. 구현 코드 public int search(int[] nums, int target) { if (nums.length == 1) { if (nums[0] == target) return 0; else return -1; } int length = nums.length; int left = 0, right = length-1; while (left left = mid +1; target이 mid ~right 안에 존재하지 않는다면 -> right = mid..

난이도 : Level 3 문제링크 문자열 begin, target과 문자열 배열 words가 주어진다 주어진 변환과정을 사용하여 begin에서 target으로 변환하는 최소한의 단계수를 리턴하라 변환 제약사항 한 번에 한 개의 알파벳만 바꿀 수 있음 words에 있는 단어로만 변환할 수 있음 example "hit" "cog" ["hot", "dot", "dog", "lot", "log", "cog"] "hit" -> "hot" -> "dot" -> "dog" -> "cog" => 4 해설 BFS 탐색을 하여 모든 경우의 수를 찾는다. 큐 자료구조를 사용하므로, 너비 탐색중에 target이 만들어지는 가장 최근의 변환횟수가 가장 최소의 변환횟수이다. 큐에 들어갈 단어가 유효성 검사를 통과해야 큐에 들어갈..

난이도 : Level 3 문제링크 컴퓨터 갯수와 각 컴퓨터의 연결 정보에 대한 2차원 정수형 배열이 주어진다 컴퓨터의 연결 정보에 대한 배열 i번 컴퓨터와 j번 컴퓨터의 연결상태를 나타냄 computers[i][j] == 1 네트워크 갯수를 구하라 해설 네트워크 전체를 탐색하기 위해 dfs 탐색을 시도합니다. (연결된 네트워크의 모든 노드들을 방문할 수 있습니다) dfs 탐색 대상 컴퓨터 연결된 또 다른 컴퓨터가 존재함 (네트워크 탐색을 통해) 방문하지 않은 컴퓨터 혼자 있는 컴퓨터도 네트워크 이므로 네트워크 수에 더해줍니다 (네트워크 탐색 시에) 방문하지 않은 컴퓨터 입니다. class Solution { boolean[] visited; public int solution(int n, int[][] ..

난이도 : Level 2 문제링크 캐릭터가 상대 팀 진영까지 도착하기 위해 지나가야 하는 칸의 최소갯수를 리턴하라 캐릭터는 맨 좌측 상단에 위치한다 상대방 진영은 맨 우측 하단에 위치한다 게임 맵에서 벽은 지나갈 수 없다 해설 최소 비용 경로를 구해야 하기 때문에 BFS 탐색 알고리즘을 사용하여 푼다. 방문한 좌표들을 큐로 넣고 큐가 비어있지 않을 때까지 반복한다. 방문한 좌표에 지나온 칸 수를 같이 저장하고, 목표지에 도착시 그동안 저장했던 칸 수를 리턴한다. import java.util.*; class Solution { int[] dy, dx; boolean[][] visited; public int solution(int[][] maps) { int r_ = maps.length-1, c_ = ..