밤 늦게까지 여는 카페

안녕하세요. 오늘은 leetcode의 2516. Take K of Each Character From Left and Right 문제를 풀어봤습니다.https://leetcode.com/problems/take-k-of-each-character-from-left-and-right/description/1. 문제이 문제에서는 "a", "b", "c"로만 이뤄진 문자열과 숫자 k가 주어집니다. 한번에 왼쪽 끝 혹은 오른쪽  끝에 있는 문자를 하나씩 잘라낼 수 있을 때, "a", "b", "c"를 각각 최소 k개 씩 뽑을 수 있는 최소한의 횟수를 구해야 합니다.만약 주어진 문자열이 조건을 만족하지 않는다면 -1을 반환합니다. 예시)"abcccba", k=2왼쪽에서 3개 오른쪽에서 3개, 총 6번 자르는 자르..

안녕하세요. 오늘은 leetcode의 1652. Defuse the Bomb 문제를 풀어봤습니다.https://leetcode.com/problems/defuse-the-bomb/description/ 1. 문제이 문제에서는 수열 code와 하나의 수 k가 주어지고, k의 값에 따라서 수열을 반환해야 합니다.k > 0 일 때, i번째에 code의 i+1, i+2, ..., i+k번째 수들의 합을 가지는 수열을 반환합니다.k k = 0 일 때, 길이가 code와 동일한 0으로 이루어진 수열을 반환합니다.i+k가 code의 길이보다 커지면 처음부터 시작합니다.i+k가 code의 길이보다 작아지면 맨 뒤부터 시작합니다. 예시)code=[1, 2, 3, 4, 5], k=3[2+3+4, 3+4+5, 4+5+1, ..

안녕하세요. 이번에는 전에 풀었던 leetcode에서 2563. Count the Number of Fair Pairs 문제를 다시 풀어보려고 합니다. 부족했던 실행 시간을 이번에 개선해보겠습니다!참고: https://goodahn.tistory.com/246 1. 개선된 문제 풀이아쉽게도 저는 더 나은 풀이 방법을 찾지 못해서 leetcode의 풀이를 참고했습니다.https://leetcode.com/problems/count-the-number-of-fair-pairs/editorial/ 저는 이전에 1) 수열을 오름차순으로 정렬하고, 2) binary search를 이용해서 모든 수에 대해 special 한 수의 개수를 찾았습니다. 하지만 더 좋은 방법이 있었습니다.1) 수열을 오름차순으로 정렬하고..

안녕하세요. 오늘은 leetcode에서 2563. Count the Number of Fair Pairs 문제를 풀어봤습니다.https://leetcode.com/problems/count-the-number-of-fair-pairs/description/ 1. 문제이 문제에서는 주어진 수열에서 합이 lower 이상, upper 이하인 두 수가 몇개 있는지 찾아야 합니다. 예를 들어서 [1, 2, 3, 4, 5] 수열과 lower=4, upper=8이 주어졌다면 [(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5)] 로 8개가 답인 것이죠. 2. 문제 풀이2.1. brute force이 문제도 가장 간단하게는 수열 내의 모든 쌍에 대해서 low..

안녕하세요. 이번에는 어제 풀었던 [leetcode] 3097. Shortest Subarray With OR at Least K II를 다시 풀어보려고 합니다. 다시 풀어보는 이유는 당연하게도 실행 시간의 효율성이 낮기 때문입니다!참고: https://goodahn.tistory.com/2441. 이전 문제 풀이의 비효율적인 연산저는 이전에 문제를 풀 때 OR 연산을 수행하기 위해서 파이썬의 bin 함수를 사용한 것이 걸리더라고요. bin 함수는 주어진 수에 대해서 2진법 문자열을 반환하는 함수입니다. 2진법 문자열을 만들기 위해서는 여러 비트 연산과 메모리를 사용해야 할텐데 이 부분을 해소해보기로 했습니다. bin 함수를 사용해서 2진법 문자열을 얻는 대신 비트 연산인 AND, OR 연산을 이용할 것..

안녕하세요. 오늘은 leetcode에서 3097. Shortest Subarray With OR at Least K II 문제를 풀어봤습니다.https://leetcode.com/problems/shortest-subarray-with-or-at-least-k-ii/description/1. 문제이 문제에서는 음수가 아닌 수로 이루어진 수열 nums와 자연수 k가 주어졌을 때, 길이가 가장 짧은 special한 연속된 부분 수열의 길이를 찾아야 합니다.수열 내의 모든 수를 OR 연산했을 때 k보다 크거나 같으면 special 하다고 합니다.nums의 길이는 최대 2 * 10^51.1. 부분 수열부분 수열이란 주어진 수열에서 일부 숫자들을 원래 순서대로 나열한 수열입니다.주어진 수열에서의 순서를 지켜야만 ..