빵똥

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

오늘의 과제리트코드 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으로 분류된 Iterator for Combination 입니다. 이번 유형은 문자열 입니다.문제https://leetcode.com/problems/iterator-for-combination/description/  먼저 문제 요구사항 요약입니다. 소문자로 정렬된 알파벳 문자열과 조합해야 할 길이가 주어질 때 가능한 모든 조합을 생성하고, 이 조합을 순차적으로 반환하거나 다음 값의 여부를 반환하는 메서드를 작성해야 합니다. 풀이 방법은 최대한 간단히 하기위해 조합 가능한 문자열을 미리 만들어 리스트에 넣어두고 next와 hasNext는 리스트의 값을 이용하는 방식으로 진행하겠습니다. 먼저 초기화입니다. 조합 가능한 문자열을 담을 리스트와 next, hasNext에 사용할..

오늘의 과제리트코드 medium으로 분류된 Group the People Given the Group Size They Belong To 입니다. 이번 유형도 배열 입니다.문제https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/description/  먼저 문제 요구사항 요약입니다. 각 사람의 그룹 크기를 나타내는 배열이 주어질 때 사람들을 각 그룹 크기대로 그룹을 나누면 됩니다. 예제 입력을 따르자면 arr = [3, 3, 3, 3, 3, 1, 3]이면 0~4번째, 6번째 사람은 크기가 3인 그룹이며, 5번째 사람은 크기가 1인 그룹에 속합니다. 먼저 사람들을 각 그룹에 맞게 분류하기 위해 HashMap을 ..

오늘의 과제리트코드 medium으로 분류된 Find The Original Array of Prefix Xor 입니다. 이번 유형도 배열 입니다.문제https://leetcode.com/problems/find-the-original-array-of-prefix-xor/description/  먼저 문제 요구사항 요약입니다. prefixXor 배열이 주어질 때 해당 배열을 원래 배열로 복원하여 반환하면 됩니다. 이 문제를 풀기 위해서는 동일한 값을 두 번 XOR하면 원래의 값으로 돌아온다는 XOR의 특성을 알아야 합니다.주어진 prefixXor은 원래 배열의 각 요소까지의 XOR 누적 값을 나타내는데 XOR 연산은 두 비트가 같으면 0, 다르면 1이 되는 연산입니다. 예를 들면 0번째 인덱스는 원래 배열..

오늘의 과제리트코드 medium으로 분류된 Subrectangle Queries입니다. 이번 유형은 배열 입니다.문제https://leetcode.com/problems/subrectangle-queries/description/  먼저 문제 요구사항 요약입니다. 사각형을 정수형 2차원 배열로 주었을 때 특정 좌표의 값을 반환하는 메서드, x,y => x2,y2 까지의 값을 업데이트 하는 메서드 하나를 구현하면 됩니다. 사실 설명이라고 할 것 없이 구구단 급의 아주 기초적인 문제라 설명할 게 딱히 없습니다. 먼저 초기화입니다. 입력으로 주어진 값을 다른 메서드에 파라미터로 넘기는게 아닌 전역으로 쓰기 위한 초기화를 진행합니다.int[][] rectangle;public SubrectangleQueries..

오늘의 과제프로그래머스 Lv.3으로 분류된 순위입니다. 이번 유형은 BFS(넓이 우선 탐색, 그래프) 입니다.문제https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  먼저 문제 요구사항 요약입니다. 선수의 수 n과 경기 결과를 담은 2차원 배열이 주어질 때 정확하게 순위를 알 수 있는 선수의 수를 반환하는 문제입니다. 문제의 유형처럼 그래프 + BFS이니 기본 공식처럼 셋팅을 시작합니다. 첫 번째 셋팅으로 ArrayList를 통해 서로간의 간선을 표현..