IT LAB

난이도 : 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. 구현 코드 ..

난이도 : easy 문제링크 두개의 문자열이 주어진다 : s, t t가 s의 anagram이라면 true를 리턴하라 anagram은 또 다른 단어의 재구성을 통해 원본 단어를 똑같이 만들 수 있는 단어를 뜻한다 반드시 모든 문자를 한번씩 사용하여 구성해야 한다 ex) s = "anagram", t= = "nagaram" => true ex) s = "ab", t= = "a" => false (s의 문자 b를 사용하지 않았음) 1. 접근법 단어별 갯수를 관리하는 자료구조인 해시테이블을 이용한다 3. 구현 코드 class Solution { public boolean isAnagram(String s, String t) { Map map = new HashMap(); for (char c : s.toChar..

난이도 : easy 문제링크 두개의 문자열이 주어진다 : ransomNote, magazine magazine의 문자를 사용해 ransomNote를 생성할 수 있다면 true를 리턴하라 1. 접근법 magazine이 ransomNote의 모든 문자를 포함해야 함 magazine의 문자 별 갯수를 hashtable을 사용하여 관리한다 ransomNote의 문자들을 각각 순회하면서 megazine의 문자에 포함되어 있는지 확인한다 확인될 경우, 해당 문자를 사용하여 ransomNote를 생성하는데 쓴다 Key의 value값을 내린다 3. 구현 코드 class Solution { public boolean canConstruct(String ransomNote, String magazine) { Map map..