본문 바로가기

Medium174

[leetcode][1657] Determine if Two Strings Are Close 문제 : leetcode.com/problems/determine-if-two-strings-are-close/ 1. 문자열에서 어떤 두 문자의 위치를 바꾼다. ex) abcde -> aecdb (b, e 교환) 2. 문자열에 존재하는 두 문자들을 모두 바꾼다. ex) aacabb -> bbcbaa (a, b 교환) word1 문자열에 위 두 연산을 해서 word2 문자열을 만들 수 있는지 구하라. word1 문자열을 앞에서부터 탐색하면서 두 연산을 실행시켜가면서 word2 문자열을 구해봐야하나 싶지만 더 간단한 방법이 있다. 1번 연산은 문자열의 문자 위치는 변경가능하므로 위치는 무의미하다는 것을 의미한다. 즉, word1, word2의 문자들의 개수(a의 개수, b의 개수 ... )만 맞출 수 있다면.. 2021. 1. 22.
[leetcode][1673] Find the Most Competitive Subsequence 문제 : leetcode.com/problems/find-the-most-competitive-subsequence/ 부분 시퀀스들이 있을 때, 앞의 요소들부터 비교해나갔을 때, 사전 정렬과 비슷하게 가장 작은 수를 가지는 부분 시퀀스가 더 경쟁력 있다고 가정한다. ex) [1,3,4,2], [1,3,5,3]는 앞에 두 요소는 동일한 값이고 세 번째 요소는 첫 번째 배열의 요소가 더 작기 때문에 (4 < 5) 첫 번째 배열이 두 번째 배열보다 더 경쟁력있다. 정수 배열 nums, 양의 정수 k가 주어졌을 때, 크기가 n인 nums 배열의 가장 경쟁적인 부분 시퀀스를 구해라. stack을 사용한다. nums배열의 i번째 요소인 num를 stack에 추가한다고 해보자. 1. num을 stack의 적절한 위치.. 2021. 1. 21.
[leetcode][1010] Pairs of Songs With Total Durations Divisible by 60 문제 : https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/ 시간배열 time이 주어질 때, 이들 중 서로 다른 원소 2개를 더한 값이 60으로 나누어떨어지는 pair들의 수를 구하라. 60 크기의 배열(cnts)을 만들고 0으로 초기화시킨다. 앞에서부터 time 배열을 탐색하면서 탐색 중인 배열 요소를 time이라 하자. cnts[60%time]들과 time을 pair로 하면 정답이 가능하다. ex) time = 20 이면 40, 100, 160 ... 이 가능하고 이들 횟수는 cnts[40]에 저장되어 있기 때문에 정답에 cnts[40] 값을 더한다. 그리고 cnts[60%time]에 time 횟수인 1을.. 2020. 12. 8.
[leetcode][1492] The kth Factor of n 문제 : leetcode.com/problems/the-kth-factor-of-n/ 양수 n, k가 주어질 때, n으로 나누어 떨어지는 정수들을 오름차순 정렬했을 때, k번째로 나오는 수를 구하라. 1부터 루트 n 만큼 반복문을 돌면서 k를 감소시킨다. 만약 n이 탐색 중인 수 i 으로 나누어 떨어졌을 때 배열에 n/i를 저장한다. 탐색 중에 k가 0이 된다면 i가 정답이 된다. 만약 i의 제곱이 n이라면 반복문 중에 k를 한 번 소모하는데 벌써 사용이 되었으므로 배열에 저장하지 않는다. 탐색이 끝났을 때 배열 크기보다 k가 크다면 정답이 없는 경우이므로 -1을 반환한다. 정답이 있는 경우 배열의 뒤에서 k번째에 있는 수가 정답이 된다. 시간복잡도는 O(루트n). 소스코드 : github.com/fpd.. 2020. 12. 5.
[leetcode][416] Partition Equal Subset Sum 문제 : leetcode.com/problems/partition-equal-subset-sum/ 양의 정수로 이루어진 nums 배열이 주어질 때, 동일한 배열 합을 가지는 두 개의 배열로 분리시킬 수 있는지 구하라. nums 배열의 합을 구한다. 동일한 배열 합을 가질 수 있다는 뜻은 배열 합이 짝수라는 뜻이다. 따라서 만약 홀수라면 false를 반환한다. 배열 합 / 2를 nums 배열을 탐색하면서 요소들의 합으로 만들 수 있는지 판단하고 만들 수 있으면 true, 아니면 false를 반환한다. nums 배열 요소들의 합으로 sum/2 를 구할 수 있는지는 배낭 문제로 풀 수 있다. dp[i][j] = nums[0~i]개의 요소들로 부분집합을 만들 때, 그 요소들의 합으로 j를 만들 수 있는지 여부... 2020. 11. 28.
[leetcode][394] Decode String 문제 : leetcode.com/problems/decode-string/ k[encoded_string] 의 룰을 가진 문자열이 주어진다. 이 룰은 encoded_string 문자열을 k번 반복한다는 뜻이다. 룰은 중첩되서 나올 수 있다. k는 반드시 숫자이며 encoded_string에는 숫자가 포함되지 않는다. 위 룰을 적용한 문자열이 주어질 때 decode한 결과를 구하라. 괄호? => 스택. 백퍼는 아니지만 대부분의 문제에 적용된다. k와 encoded_string을 pair로 가지는 스택을 만든다. 이 때 입력 문자열을 "3[a]"라 하였을 때 이는 "1[3[a]]" 와 동일하기 때문에 코드의 일관성을 맞춰주기 위해(예외처리 덜하려고. ex. "ab3[a]" 와 같은 문자열은 초기에 나오는 a.. 2020. 11. 21.

티스토리툴바