IT LAB

난이도 : Level 2 문제링크 n개의 음이 아닌 정수형 배열이 주어진다 순서를 바꾸지 않고 더하거나 빼서 타겟 넘버를 만드는 방법의 수를 리턴하라 해설 깊이 탐색으로 모든 경우를 조사한다. numbers의 길이만큼의 뎁스로 탐색했을 때의 합이 target과 같은지 확인한다. 현재 뎁스에서 탐색하려는 숫자의 인덱스는 numbers의 인덱스와 같다. 첫번째 수부터 부호를 바꿀 수 있으므로 호출시의 뎁스를 -1로 전달한다 class Solution { public int solution(int[] numbers, int target) { return dfs(-1, numbers, target, 0); } private int dfs(int depth, int[] numbers, int target, int..

난이도 : Level 4 문제링크 마을의 모든 집들은 동그랗게 배치되어 있다. 각 집들은 서로 인접한 집들과 방법장치가 연결되어 있음 인접한 두 집을 털면 경보가 울림 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 구하시오 해설 집들이 원형으로 배치되어 있고 인접한 두 집을 털 수 없으므로 두가지 경우가 발생한다 첫번째 집을 털면 마지막 집을 털지 못하고 마지막 집을 털면 첫번째 집을 털지 못한다 두가지 경우를 비교하고, 가장 큰 값을 리턴한다 첫번째 집부터 마지막에서 이전 집까지 터는 돈의 최대값 두번째 집부터 마지막까지 터는 돈의 최대값 public int solution(int[] money) { int size = money.length; int[] d..

난이도 : 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 대표문자 -..