본문 바로가기
반응형

Star28

[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) 2. p = q : rank(p) = rank(q) 3. 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] 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.
[Programmers] 하노이의 탑 문제 : https://programmers.co.kr/learn/courses/30/lessons/12946 오랜만에 풀어보는 하노이의 탑. 재귀로 풀었다. A -> C로 N개의 원판을 옮긴다고 해보자. 가장 아래에 있는 원판을 제외한 N-1개의 원판은 커다란 덩어리로 보자. 먼저 N-1개의 원판을 하노이의탑 규칙에 어긋나지 않게 A -> B 위치로 옮긴다. 그 뒤, N 번째 원판을 A -> C로 옮긴다. 다시 N-1개의 원판을 N-2번째 원판과 그 외의 원판들로 보자. N-2 개의 원판들을 규칙에 어긋나지 않게 B -> A로 옮긴 후, N-1번째 원판을 B -> C로 옮긴다. 이를 반복하며 다시 N-2개의 원판들을 C로 옮긴다. // n개의 원판을 from -> to로 이동 fun hanoi(int .. 2021. 7. 6.
[leetcode][795] Number of Subarrays with Bounded Maximum 문제 : https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/ 양수 배열 nums, 두 개의 양수 left, right 가 입력으로 주어진다. nums 배열의 하위배열(연속적인 부분배열. 비어있지 않음)의 최대 원소가 left 이상, right 이하인 하위배열들의 수를 구해라. 재미있는 투포인터문제~ nums를 처음부터 탐색하면서 정답이 될 수 있는 범위를 l, r 변수에 저장한다. (l = 왼쪽, r = 오른쪽 인덱스) l 변수는 nums[i]가 부분배열에 포함될 때 정답이 절대 불가능할 때 갱신한다. 최대값만 left, right를 비교하기 때문에 정답이 절대 불가능한 경우는 nums[i]가 right보다 큰 경우이다. r 변.. 2021. 6. 19.
[Leetcode][923] 3Sum With Multiplicity 문제 : leetcode.com/problems/3sum-with-multiplicity/ 0이상 100이하의 정수를 가지는 배열 arr이 주어진다. 서로다른 원소 3개를 더한 값이 target이 되는 조합의 개수를 구하라. 배낭문제로 구할 수 있다. dp[target][cnt] = cnt 개의 원소들을 합해서 target 을 만들 수 있는 경우의 수. i 번째 원소(num)를 기준으로 dp 배열을 갱신해나간다. num + x = target 이라 가정하면 num에 x를 더하면 target을 만들 수 있으므로, x의 경우의 수로 target 인덱스를 갱신할 수 있다. 위의 식에서 num을 우항으로 옮기면 x = target - num이 되므로 dp[target][cnt+1] += dp[target-num.. 2021. 3. 23.
[programmers][2021카카오공채] 순위 검색 문제 : https://programmers.co.kr/learn/courses/30/lessons/72412 query가 100,000 infos가 50,000. query 문자열에 맞게 infos에 맞는 조건을 찾아서 정답을 구하기엔 시간이 부족하다. 개발언어가 3개. 직군 2개. 경력 2개. 소울푸드 2개. 3x2x2x2 = 24개의 조합에 맞는 score들을 저장해두면 시간을 확 줄일 수있다. scores[개발언어][직군][경력][소울푸드] = 점수들 배열. 만약 query에 개발언어가 상관없다면 scores[0~3][직군][경력][소울푸드]의 scores 조건에 맞는 점수들의 수를 정답에 포함시킨다. query에 개발언어가 java라면 scores[java 인덱스][직군][경력][소울푸드]의 s.. 2021. 3. 6.
반응형

티스토리툴바