본문 바로가기

HARD56

[leetcode] 76. Minimum Window Substring 문제 : https://leetcode.com/problems/minimum-window-substring/ 길이가 m, n인 문자열 s, t가 입력으로 주어진다. t의 모든 문자가 포함되는 s의 부분 문자열들 중 최소 길이를 가지는 연속 부분 문자열을 구해라. 정답이 없다면 빈 문자열 반환. 투포인터로 풀었다. t문자열의 모든 문자들의 갯수를 저장하는 cnt 배열을 만들어 세팅한다. right 인덱스를 증가시키며 cnt 배열의 등장갯수를 모두 충족시킨다면 해당 right 인덱스를 부분문자열 끝으로 할 때, 해당 부분문자열을 최소 길이로 만들기 위해 left인덱스를 조정한다. left 인덱스는 0부터 증가시키며 현재 탐색중인 문자가 부분문자열에서 제외된다면 cnt 배열의 문자 갯수를 충족시킬 수 없을때까.. 2021. 8. 16.
[leetcode] 1632. Rank Transform of a Matrix 문제 : https://leetcode.com/problems/rank-transform-of-a-matrix/ m x n 크기의 배열이 있을 때, 이들의 랭크를 매긴 배열을 반환하라. 순위는 1부터 시작하며 두 개의 요소 p, q가 같은 행 혹은 같은 열에 있으면 아래와 같은 규칙에 따라 순위를 매긴다. 1. p q : rank(p) > rank(q) 랭크는 가능한한 작게 매겨져야 한다. 예시 4를 보자. 7 3 6 1 4 5 9 8 2 만약 배열의 모든 수가 유니크한 수를 가진다면 정답을 구하기는 생각보다 간단하다. 요소 값을 기준으로 오름차순 정렬한다. 요소값(x, y) 1 (1,0) -> 2.. 2021. 8. 12.
[leetcode] 132. Palindrome Partitioning II 문제 : https://leetcode.com/problems/palindrome-partitioning-ii/ 문자열 s가 주어지면 s를 잘라 부분문자열들을 만들었을 때 모든 부분문자열들이 펠린드롬이 되는 최소 절단횟수를 구하여라. 먼저 DP로 2차원 배열을 만들어 펠린드롬[i][e] = 문자열[i,e]가 펠린드롬인지를 구한다. 펠린드롬[i][j] = 펠린드롬[i+1][j-1] (s[i] == s[j]) = false (s[i] != s[j]) 문자열[i~j]은 문자열의 첫문자와 끝 문자가 다르면 false, 첫문자와 끝문자가 같다면 문자열[i+1, e-1]이 펠린드롬인 경우는 펠린드롬, 아니면 펠린드롬이 아니다. 위 점화식으로 펠린드롬 여부를 구하면 이번엔 1차원 배열을 만든다. dp[i] = s[0.. 2021. 8. 7.
[leetcode] 827. Making A Large Island 문제 : https://leetcode.com/problems/making-a-large-island/ n x n 크기의 0과 1로 이루어진 grid 배열이 입력으로 주어질 때, 1로 이루어진 섬의 최대 크기를 구하여라. 이 때, 최대 한 번 0을 1로 바꿀 수 있다. dfs를 한 번 돌리면서 연결된 1들을 하나의 섬으로 보고 섬의 번호와 해당 섬의 크기를 map에 저장한다. grid 배열을 한 번 더 탐색하면서 탐색하는 셸이 0인 경우 해당 셸의 상하좌우에 있는 섬의 번호들을 가져온다. 상하좌우에 있는 섬들의 합 + 1 (탐색중인 0 셸이 1로 바뀌면서 증가된 섬의크기)들이 하나의 0을 1로 바꿨을 때 구할 수 있는 섬의 크기이다. 구할 수 있는 섬들의 크기들 중 최대값이 정답이 된다. 시간/공간 복잡.. 2021. 8. 2.
[leetcode] 126. Word Ladder II 문제 : https://leetcode.com/problems/word-ladder-ii/ 문자들 리스트인 wordList가 주어질 때, beginWord에서 한 글자씩만 바꿔서 wordList에 있는 문자열로 변환해가면서 endWord로 변환가능한 최소 변환횟수 문자열 변경 리스트들을 구하라. beginWord는 wordList에 없어도 되지만 endWord는 wordList에 있어야만 변경 가능한다. ex) // input beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] // output [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog.. 2021. 7. 25.
[leetcode] 85. Maximal Rectangle 문제 : https://leetcode.com/problems/maximal-rectangle/ 0과 1로 이루어진 배열이 주어질 때, 1로만 이루어진 직사각형의 최대 크기를 구하라. 배열 크기가 row x cols 인데 row, cols 모두 최대 200이다. row, cols 의 최대크기가 동일하니까 해당 크기를 N이라 봤을 때, 직사각형의 크기를 구하려면 직사각형의 왼쪽 위 지점을 구하기 위해 O(N^2), 이때, 오른쪽 아래 지점을 구하기 위한 O(N^2)가 드므로 완탐으로 구하면 총 O(N^4)이 소요된다. N의 최대 크기는 200이므로 TLE가 발생할 것이다. 시간을 좀 더 줄 일 수 있는 방법을 찾아야한다. 배열을 탐색하면서 오른쪽 아래 지점을 고정시키고 왼쪽 위 지점을 탐색해가면서 만들 수.. 2021. 7. 24.

티스토리툴바