빵똥

오늘의 과제리트코드 medium으로 분류된 Optimal Partition of String 입니다. 이번 유형은 그리디 입니다.문제https://leetcode.com/problems/optimal-partition-of-string/description/ 먼저 문제 요구사항 요약입니다. 문자열이 주어질 때 각 문자가 하나의 파티션에 최대 한 번씩만 등장하도록 파티션을 나눈 후 파티션의 개수를 반환하는 문제입니다. 먼저 살펴보아야 할 부분은 각 파티션에 문자가 중복되지 않게 어떻게 나누는가? 입니다. 문제의 유형이 그리디인만큼 매번 최선의 선택을 해야 하는데 제약 조건인 "문자가 중복되지 않는다"에 포커스를 맞추면 매우 쉽게 풀 수 있습니다. 문자열이 주어지면 contains를 통해 중복 여부를 확인하..

오늘의 과제리트코드 medium으로 분류된 Reduce Array Size to The Half 입니다. 이번 유형은 힙 입니다.문제https://leetcode.com/problems/reduce-array-size-to-the-half/description/ 먼저 문제 요구사항 요약입니다. 배열이 주어질 때 크기를 절반 이하로 줄이기 위해 제거해야 할 최소 요소 수를 반환하는 문제입니다. 요소를 최소한으로 줄이기 위해 가장 많이 중복되는 요소를 먼저 찾습니다.// 빈도수 계산Map freqMap = new HashMap();for (int num : arr) { freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);} 문제의 예시인 {3, 3, 3, 3, 5..

오늘의 과제리트코드 medium으로 분류된 Seat Reservation Manager 입니다. 이번 유형은 힙 입니다.문제https://leetcode.com/problems/seat-reservation-manager/description/  먼저 문제 요구사항 요약입니다. 좌석 예약 프로그램을 디자인합니다. 초기화 함수, 예약, 예약 취소 함수를 구현하면 되는데 예약시에는 가장 낮은 번호의 좌석 번호 순서대로 숫자를 반환합니다. 자료구조로서 힙은 최소 힙 혹은 최대 힙을 사용할텐데 문제의 요건을 보면 "가장 낮은 번호 순서대로" 좌석을 예약한다라고 나와있으니 최소 힙으로 사용하도록 하겠습니다. 이전 문제에서 사용했던 우선순위 큐를 사용할텐데 초기화시 정렬 순서에 따라 정렬된 값을 반환해주는 특성을 ..

오늘의 과제리트코드 medium으로 분류된 Minimum Add to Make Parentheses Valid 입니다. 이번 유형은 스택/큐 입니다.문제https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/  먼저 문제 요구사항 요약입니다. 짝이 맞거나 맞지 않은 괄호가 주어질 때 삽입이나 이동을 통해 온전한 괄호를 만들 수 있는 최소 이동 횟수를 반환하면 됩니다. 문제의 분류가 스택이고 스택 단골 문제인 괄호가 나왔으니 스무스하게 풀어주면 됩니다. 스택 기초 문제로는 짝이 맞는 문자열이라면 true, 맞지 않는다면 false를 반환하는 문제에서 조~금 심화 문제인데 기존의 공식과 똑같이 진행하면 됩니다. 먼저 (를..

오늘의 과제리트코드 medium으로 분류된 Removing Stars From a String 입니다. 이번 유형은 스택/큐 입니다.문제https://leetcode.com/problems/removing-stars-from-a-string/description/  먼저 문제 요구사항 요약입니다. 문자열이 주어지고 문자중 *를 만나면 왼쪽에서 가장 가까운 문자와 함께 *도 제거 후 반환하면 됩니다. 괄호 짝 맞추기와 같이 전형적인 스택 문제입니다. 후입선출의 자료구조 특성을 이용하여 문자를 계속 담다가 *를 만날때만 pop을 통해 문자를 제거해주면 되는 아주 간단한 문제입니다. 코드입니다.class Solution { public String removeStars(String s) { ..

오늘의 과제리트코드 medium으로 분류된 Flatten Nested List Iterator 입니다. 이번 유형은 스택/큐 입니다.문제https://leetcode.com/problems/flatten-nested-list-iterator/description/  먼저 문제 요구사항 요약입니다. 중첩 가능한 리스트가 주어집니다. 다음 요소를 반환하는 next(), 다음 요소가 있는지를 반한하는 hasNext() 함수를 구현하면 됩니다. 일단 문제의 힌트에 맞게 스택/큐를 사용하여 접근했습니다. 처음 주어지는 nestedList내 요소가 숫자인지, 중첩 List인지 알 수 없기 때문에 일단은 스택에 모두 넣어놓고 숫자면 pop, 아니면 해당 리스트 내 요소를 push하는 방법으로 풀이를 진행했습니다. 먼..

오늘의 과제리트코드 medium으로 분류된 Find the Winner of the Circular Game 입니다. 이번 유형은 스택/큐 입니다.문제https://leetcode.com/problems/find-the-winner-of-the-circular-game/description/  먼저 문제 요구사항 요약입니다. N이 주어질 때 K번째마다 요소를 제거하여 마지막 하나의 요소만 남을 때 까지 반복 후 해당 요소를 반환하면 됩니다. 이 문제는 요세푸스 문제의 변형으로 다음과 같은 수식을 갖고 풀 수 있습니다.f(n, k) = (f(n - 1, k) + k) % n 단순 암기 문제로 코드 또한 위 수식이 전부입니다. 마지막 한 명이 남을 때 까지 재귀적으로 호출해주면 됩니다.class Soluti..

오늘의 과제리트코드 medium으로 분류된 Reordered Power of 2 입니다. 이번 유형도 정렬입니다.문제https://leetcode.com/problems/reordered-power-of-2/description/  먼저 문제 요구사항 요약입니다. 정수가 주어질 때 2의 거듭제곱을 만들 수 있는지 여부를 반환하면 됩니다. 거듭제곱 여부를 쉽게 확인하기 위해 미리 2의 30제곱까지 구해둡니다. 30제곱까지만 구하는 이유는 입력으로 최대 10의 9승(10억)까지만 주어지기 때문입니다. 또한 임의의 정렬이라고 했으나 모두 통일하여 정렬하기 위해 2의 거듭제곱을 오름차순으로 정렬하여 넣어줍니다.List powerOf2Digits = new ArrayList();for (int i = 0; i  ..

오늘의 과제리트코드 medium으로 분류된 Top K Frequent Elements 입니다. 이번 유형은 정렬입니다.문제https://leetcode.com/problems/top-k-frequent-elements/description/  먼저 문제 요구사항 요약입니다. 문자열이과 정수가 주어지면 문자의 빈도에 따라 내림차순으로 정렬 후 정수만큼 반환해주면 됩니다. 어제의 문자와 완전히 동일하게 풀었습니다. 코드입니다.import java.util.*;class Solution { // 1. num을 센다. // 2. 정렬을 한다. // 3. k만큼 배열에 넣는다. public int[] topKFrequent(int[] nums, int k) { var map = ..

오늘의 과제리트코드 medium으로 분류된 Sort Characters By Frequency 입니다. 이번 유형은 문자열 입니다.문제https://leetcode.com/problems/sort-characters-by-frequency/description/  먼저 문제 요구사항 요약입니다. 문자열이 주어지면 문자의 빈도에 따라 내림차순으로 정렬 후 반환하면 됩니다. 입력 제한은 영어 대문자 소문자 숫자로 구성되어 있으며 최대 5 * 10⁵ 길이를 갖고 있으니 O(n²)으로는 풀 수 없습니다. 접근입니다. "문자 빈도"에 따라 문자열을 정렬해야 하니 단순한 생각으로 문자를 먼저 계산합니다. 각 문자에 대한 카운팅은 여러가지 방법이 있겠으나 저는 map을 활용하여 풀이하였습니다. map에서 제공하는 a..