https://leetcode.com/problems/word-subsets/description/?envType=daily-question&envId=2025-01-10 You are given two string arrays words1 and words2.A string b is a subset of string a if every letter in b occurs in a including multiplicity.For example, "wrr" is a subset of "warrior" but is not a subset of "world".A string a from words1 is universal if for every string b in words2, b is a subset of ..

https://leetcode.com/problems/01-matrix/description/?envType=problem-list-v2&envId=breadth-first-search    Input: mat = [[0,0,0],[0,1,0],[1,1,1]]Output: [[0,0,0],[0,1,0],[1,2,1]]  1에서부터 가장 가까운 0의 값을 배열에 저장해주면 되는 문제였다. 배열이 0이라면 큐에 삽입1이라면, -1로 초기화를 해준다 (거리 값 초기화)배열이 0인 곳에서부터 탐색을 하면서 거리가 -1인 곳을 계속해서 갱신해나가면 되는 문제였다.  정답 코드class Solution { int n, m; int [] dx = {1,0,-1,0}; int [] dy = {0,1,0..

https://leetcode.com/problems/subsets/description/ Given an integer array nums of unique elements, return all possible subsets (the power set).The solution set must not contain duplicate subsets. Return the solution in any order. 배열이 주어질 때, 해당 배열의 모든 부분집합을 리턴하는 문제였다. (공집합 포함)해당 문제를 풀면서 느꼈던 것은 자바의 List 인터페이스 메서드에 대해서 잘 모르고 쓰고있구나 하는 생각이 들었다. 문제를 풀다가 List 형태에 Integer 값인 nums[i]를 추가했더니 error: incomp..

https://leetcode.com/problems/target-sum/description/?envType=daily-question&envId=2025-01-04 You are given an integer array nums and an integer target.You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate th..

https://leetcode.com/problems/unique-length-3-palindromic-subsequences/description/?envType=daily-question&envId=2025-01-04 주어진 문자열 s에서 길이가 3이고 중복되지 않은 팰린드롬의 갯수를 구하는 문제였다. 나는 백트래킹을 통해서 길이가 3인 모든 문자열을 찾아 Set에 넣어 중복되지 않은 문자열들을 구했다. 그 다음에, Set을 순회하며 해당 문자열이 팰린드롬인지 판단해주었다. 예제는 통과했지만, s의 길이가 10만이기 때문에 백트래킹을 시도했을 때 당연히 시초가 터졌다. 시간복잡도를 O(nlogn), 혹은 O(n) 이하로 줄일 방법을 찾아야 했다. 정답 풀이)class Solution { publ..

https://leetcode.com/problems/find-a-safe-walk-through-a-grid/description/ You are given an m x n binary matrix grid and an integer health.You start on the upper-left corner (0, 0) and would like to get to the lower-right corner (m - 1, n - 1).You can move up, down, left, or right from one cell to another adjacent cell as long as your health remains positive.Cells (i, j) with grid[i][j] = 1 are ..

Contains Duplicate배열에 중복된 값이 있는지 체크하는 문제로, 간단하게 Set을 사용하여 배열의 길이와 비교해주었다.Valid Anagram단어의 등장 횟수를 비교하여 같다면 valid인 문제였다. 맵을 두개를 사용하여 풀었으나, 한개를 사용하여 한 문자열의 등장횟수를 더하고, 다른 문자열에선 등장횟수를 빼준다면 충분히 맵을 한개만 사용하여 풀이할 수 있었다.Two Sum리트코드 국민 문제. 관건은 O(n^2) 시간보다 어떻게 줄일 수 있느냐였다.맵을 사용하여 현재 값과 인덱스를 넣어주고, 만약에 (target - 현재값)이 맵에 존재한다면, 인덱스를 리턴해줬다.Group Anagrams이 문제를 풀면서 String을 어떻게 정렬하는지 까먹어서 인터넷을 참고했다.char [] chars =..

Redundant Connectionhttps://neetcode.io/problems/redundant-connection NeetCode neetcode.io 이 문제와 비슷한 느낌을 받았다.https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 실제로, 비슷하게 풀이하여 정답을 맞출 수 있었다.처음부터 각 노드의 연결된 간선을 끊어주며, 끊어졌을 때 모든 노드를 방문할 수 있다면 정답으로, 아니라면 skip을 해주었다. 모든 노드를 방문했을 때, 가장 뒤에 등장한 노드를 리턴해줘야 했으므로 값..

Graph Valid Treehttps://neetcode.io/problems/valid-tree NeetCode neetcode.io해당 무방향 그래프가 올바른 트리 형태인지 판단하는 문제였다.올바른 트리이기 위한 조건은간선의 갯수가 노드 - 1개일 것.모든 노드가 서로 연결되어 있을 것사이클 x무방향 그래프인 경우에 유니온 파인드를 사용해서 두 노드가 같은 집합에 속하는지 판단하고, 같은 집합에 속하는 경우 사이클이 있다고 판단하여 트리 조건에 부합하지 않도록 구현했다. 방향이 있는 그래프에선 위상 정렬을 사용하여 사이클 여부를 판단했지만, 위상 정렬은 무방향 그래프에선 잘 사용하지 않는다고 한다.Number of Connected Components in an Undirected Graphhttp..

Course Schedule Ihttps://neetcode.io/problems/course-schedule NeetCode neetcode.io 위상정렬을 사용하여 사이클이 존재하는지 여부를 판단하는 문제다.차수가 0인 지점을 큐에 넣어 BFS를 돌리고, 다른 지점을 방문할 때마다 차수를 하나씩 빼주고 0이 될때마다 다시 큐에 넣는다. Course Schedule IIhttps://neetcode.io/problems/course-schedule-ii NeetCode neetcode.io 마찬가지로 위상정렬을 이용하는 문제다. 다른점이 있다면, Input: numCourses = 3, prerequisites = [[1,0]]Output: [0,1,2]이런식으로 주어질 때, 0은 1의 선행과목이 되지..