IT LAB

난이도 : Level 3 문제링크 집에서 학교까지 갈 수 있는 최단 경로의 개수의 1,000,000,007로 나눈 나머지를 리턴하라 물웅덩이가 있는 길은 지나갈 수 없음 집 좌표 : (0,0) 학교 좌표 : (m-1, n-1) 해설 동적계획법을 사용하여 도착지별 최단 경로수를 구해나간다. 도착지의 최단 경로 수는 도착지로부터 위, 왼쪽 도착지의 경로의 합입니다. 물웅덩이를 만나게 될 경우, 해당 경로의 최단경로 수는 0이 됩니다. 첫번째 열 혹은 첫번째 행일경우, 직전에 방문한 도착지의 최단경로만 더해줍니다. public int solution(int m, int n, int[][] puddles) { int[][] dp = new int[n+1][m+1]; for (int[] puddle : puddl..

난이도 : Level 4 문제링크 문자열 배열 arr가 매개변수로 주어짐 : 숫자, 더하기 기호, 뺄셈 기호 arr의 괄호를 사용하여 연산순서가 이전과 다른 연산을 할 수 있다 괄호 사용을 포함한 모든 연산에 대한 결과 중 최댓값을 리턴하라 길이 : 3 이상 201 이하 (항상 홀수) example) 1 - 3 + 5 - 8 (((1 - 3) + 5) - 8) = -5 ((1 - (3 + 5)) - 8) = -15 (1 - ((3 + 5) - 8)) = 1 (1 - (3 + (5 - 8))) = 1 ((1 - 3) + (5 - 8)) = -5 해설 주어진 arr의 부분합들을 조합해서 가장 큰 최댓값을 리턴한다 동적계획법을 활용하여 2부터 arr의 전체길이까지 반복하면서 부분합들을 연산하고 만들어간다 0부..

난이도 : Level 3 문제링크 꼭대기에서 바닥까지 이어지는 경로 중, 가장 경로의 합이 큰 숫자를 리턴하라 대각선 경로만 사용하여 아래로 내려갈 수 있다 높이: 1 이상 500 이하 정수: 0 이상 9,999 이하 해설 꼭대기에서 바닥까지 모든 경로의 합 중, 가장 큰 경로의 합을 리턴해야 한다 이전까지의 합이 크더라도 현재 방문하는 정수가 크다면 가장 큰 경로가 될 수 있기 때문 그러나 모든 경로의 합에서 가장 큰 경로를 매번 구하는 것은 비효율적이므로 동적 계획법을 사용한다 2차원 정수형 배열을 선언하고 꼭대기에서 (r, c)까지의 최대 경로의 합을 저장한다 경로를 하나씩 늘려가면서 이전에 방문한 점의 가장 큰 누적합을 더하면서 만들어간다 모든 삼각형을 방문하여 dp 배열을 완성한다 꼭대기에서 바..

난이도 : Level 3 문제링크 두 정수 N과 number가 주어진다 number : 표현하고자 하는 수 N : 표현하는데 사용되는 수 N을 사칙연산만 사용해서 number를 표현해야 한다 표현할 수 있는 방법 중 N 사용횟수의 최솟값을 리턴하라 최솟값이 8보다 크면 -1을 리턴하라 N : 1이상 9이하 number : 1이상 32000이하 example) N : 5, number : 12 - 12 = 5 + 5 + (5 / 5) + (5 / 5) - 12 = 55 / 5 + 5 / 5 - 12 = (55 + 5) / 5 => 4 해설 N을 1부터 8까지 사용해서 만들수 있는 수 생성 만들수 있는 수들 중, number가 포함되는지 체크 포함되어 있다면, 만드는데 사용된 횟수를 리턴한다 포함되지 않다면..

난이도 : Level 4 문제링크 캠핑장에 여러개의 쐐기를 박아두었다 설치한 쐐기의 좌표값을 가진 2차원 정수형 배열이 주어진다 쐐기들 중 한 쌍을 골라 텐트를 칠 수 있다 텐트는 직사각형이여야 한다 양쪽 쐐기가 대각에 위치하도록 하여 텐트를 친다 텐트가 점유하는 영역 내부에 다른 쐐기를 포함하면 안된다 단, 다른 쐐기가 경계에 위치하는 경우는 허용함 주어진 쐐기들을 이용하여 만들 수 있는 텐트의 최대 수를 리턴하라 쐐기의 개수 : 2 ~ 5000 쐐기의 x좌표 : 0 ~ 2^31-1 쐐기의 y좌표 : 0 ~ 2^31-1 해설 서로 가까이 인접해 있는 쐐기부터 텐트를 칠 수 있는지 체크하기 양쪽 쐐기가 대각선에 위치하는지 확인 양쪽 쐐기 안에 쐐기가 들어있지 않은지 확인 전체 경우를 모두 체크하며, 칠 ..

난이도 : medium 문제링크 정렬되어지지 않은 정수형 배열 nums가 주어진다 가장 긴 연속적인 요소들의 길이를 리턴하라 ex) [100,4,200,1,3,2] => 4 (1, 2, 3, 4) 1. 접근법 해시테이블에 요소별 인덱스 Entry를 저장함 방문용 set을 선언함 요소를 하나하나 순회하면서, 현재 탐색중인 원소보다 1 더 크고 방문하지 않았으면, 길이를 1 늘려 반복한다 현재 탐색중인 원소보다 1 더 작고 방문하지 않았으면, 길이를 1 줄여 반복한다 길이와 최종 답의 max값을 최종 답으로 업데이트한다 3. 구현 코드 public int longestConsecutive(int[] nums) { if (nums.length == 0) { return 0; } // val - idx Map ..

난이도 : easy 문제링크 n이라는 정수가 주어짐 n이 happy number인지 체크하라 happy number 양의 정수로 시작하며, 각각의 digit 제곱의 합으로 교체됨 숫자가 1이 될때까지 반복하며, 1이되면 그 숫자는 happy number 이다. 1. 접근법 각각의 digit 제곱의 합은 10의 멱수가 되어야 한다 n - digit 제곱합을 해시테이블에 저장한다 방문한 n은 다시 방문하지 않는다 3. 구현 코드 class Solution { Map map = new HashMap(); public boolean isHappy(int n) { while (n != 1 && !map.containsKey(n)) { n = process(n); } return n == 1 ? true : fal..

난이도 : medium 문제링크 string 배열이 주어진다 : strs strs 중, 서로 anagram인 문자열들을 그룹핑하고, 2차원 배열로 리턴하라 ex) Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]] anagram은 또 다른 단어의 재구성을 통해원본 단어를똑같이 만들 수 있는 단어를 뜻한다 반드시 모든 문자를 한번씩 사용하여 구성해야 한다 ex) s = "anagram", t= = "nagaram" => true ex) s = "ab", t= = "a" => false (s의 문자 b를 사용하지 않았음) 1. 접근법 해시테이블 사용 anagram 대표문자 -..

난이도 : easy 문제링크 두개의 문자열이 주어진다 : pattern, s s가 pattern 문자열의 패턴을 따르는지 확인하라 ex) pattern = "abba", s = "dog cat cat dog" => true ex) pattern = "abba", s = "dog cat cat fish" => false 1. 접근법 해시테이블 생성 pattern 문자에 대응되는 s 문자열 s 문자열에 대응되는 pattern 문자 한 문자씩 순회하면서, 특정 pattern 문자에 대응되는 s 문자열이 해시테이블에서 가지고있는 값과 동등한지 확인 s 문자열에 대응되는 pattern 문자가 해시테이블에서 가지고있는 값과 동등한지 확인 3. 구현 코드 public boolean wordPattern(String ..

난이도 : easy 문제링크 두개의 문자열이 주어진다 : s, t s와 t가 isomorphic 한지 체크하라 isomorphic은 다르게 표현되지만 같은 구조를 가지고 있을 때 사용한다 s의 문자가 t의 문자로 replace될 수 있으면 isomorphic하다 할 수 있다 ex) s="egg", t="add" => true ex) s="foo", t="bar" => false ex) s="paper", t="title" => true 1. 접근법 해시테이블 생성 s문자에 대응되는 t문자 t문자에 대응되는 s문자 한 문자씩 순회하면서, 특정 s문자에 대응되는 t문자가 해시테이블에서 가지고있는 값과 동등한지 확인 특정 t문자에 대응되는 s문자가 해시테이블에서 가지고있는 값과 동등한지 확인 3. 구현 코드 ..