Hash Table

오늘 한 내용 LeetCode 2958. Length of Longest Subarray With at Most K Frequency LeetCode 2996. Smallest Missing Integer Greater Than Sequential Prefix Sum StackDay. 엔티티와 계산 책임 분리하기 배운 내용 파생 값을 구현할 때의 책임 분리 StackDay의 HabitEntry와 HabitStreak을 구현했다. 모델링 단계에서 정의한 파생 값을 실제 코드로 옮기면서, 값을 표현하는 타입과 값을 계산하는 로직을 분리했다. AI 에이전트가 작성한 내용중에 별로인 것들을 몇개 직접 수정했는데 리스트로 정리하면 다음과 같다. HabitEntry의 이니셜라이저 전체 Completion 목록을 직접 탐색하고, 생성 실패/성공을 판정했다. HabitStreak의 이니셜라이저 내부에 Streak 계산 로직이 들어있었다. 둘 다 경계가 제대로 구분되지 않았다. HabitEntry 내부에서 전체 Completion을 탐색하면서 조건에 맞는 Completion을 찾아내는건 비효율적이기도 하고, 이건 유즈케이스에서 해야 될 일이다. ...

문제 https://leetcode.com/problems/smallest-missing-integer-greater-than-sequential-prefix-sum 풀이 정수 배열 nums가 주어진다. 배열의 첫 원소부터 연속해서 증가하는 부분의 합을 구한 뒤, 그 합보다 크거나 같으면서 배열에 존재하지 않는 가장 작은 정수를 찾으면 된다. 먼저 첫 번째 원소를 합에 더해두고, 현재 원소가 다음 조건을 만족하는지 확인한다. $$ nums[i] = nums[i - 1] + 1 $$ 조건을 만족하는 동안에는 현재 원소를 합에 더하고, 연속 조건이 깨지면 순회를 종료한다. 이제 구한 합을 후보값으로 두고, 후보값이 배열 안에 있으면 1씩 증가시킨다. 배열에 없는 첫 번째 값이 정답이다. 이 부분은 코드처럼 배열에 후보값이 존재하는 동안 반복하면 된다. ...

문제 https://leetcode.com/problems/smallest-palindromic-rearrangement-i 풀이 팰린드롬 스트링 s가 주어지고, 이 s의 원소들을 재배열 하여 만들 수 있는 팰린드롬중 가장 사전순으로 빠른 문자열을 리턴하는 문제이다. s가 팰린드롬 스트링인것이 보장되니, 팰린드롬의 성질인 대칭을 이용하면 정렬 문제로 바꿀 수 있다. s의 원소 개수가 홀수인지 짝수인지만 주의하면 된다. 만약 홀수면 대칭의 중심이 존재하니, 원소 중 등장 횟수가 홀수인 원소가 존재한다. s에서 등장하는 모든 원소의 등장 횟수를 센다. s의 원소 개수가 홀수라면, 원소들 중 홀수번 등장하는 원소를 center를 찾는다. 이 원소가 팰린드롬의 중간에 들어가는 문자이다. 원소들의 등장 횟수를 절반으로 줄인 다음, 사전 오름차순으로 정렬한 스트링 half를 만든다. half와 center 그리고 half를 뒤집은 스트링을 합쳐서 결과를 만든다. 코드 class Solution { func smallestPalindrome(_ s: String) -> String { var countTable = [Character: Int]() var half = "" var center = "" for element in s { countTable[element, default: 0] += 1 } for (element, count) in countTable.sorted(by: { $0.key < $1.key }) { if count % 2 == 1 { center = String(element) } half += String(repeating: element, count: count / 2) } return half + center + String(half.reversed()) } }

문제 https://codeforces.com/problemset/problem/4/C 풀이 데이터베이스를 흉내내는 문제이다. n 개의 스트링이 입력으로 주어지고(각각의 스트링을 name 이라고 한다), 그 스트링이 만약 등록된 이름이면 이름 + 번호를 붙여서 출력하고 등록되지 않은 이름이면 'OK'를 출력하면 된다. 딕셔너리를 쓰면 가장 쉽게 해결 가능하다. 딕셔너리에 name을 키로, 그리고 등장한 횟수를 값으로 저장하면 쉽게 존재 판별과 번호 붙이기 둘 다 가능하다. 코드 #include <iostream> #include <map> int main() { int n; std::cin >> n; std::map<std::string, int> db; while (n--) { std::string name; std::cin >> name; if (db.find(name) != db.end()) { db[name]++; std::cout << name << db[name] << std::endl; } else { db[name] = 0; std::cout << "OK" << std::endl; } } return 0; }

문제 https://leetcode.com/problems/find-the-maximum-number-of-elements-in-subset/ 풀이 주어진 배열의 원소들로 만들 수 있는 가장 긴 [x, x², x⁴, ..., x^(2^k), ..., x⁴, x², x] 형태의 부분집합 길이를 반환하는 문제다. 이하에서는 이 형태를 피라미드라고 부른다. 어떤 문제든 제약 조건이 중요하지만, 이 문제는 특히 제약 조건이 중요하다. 주어진 꼴에서 원소들은 급격히 증가하는데, 1 <= nums[i] <= 10^9 라는 제약 조건이 있기에, 배열의 최대 크기를 예상할 수 있다. x가 1일 때는 몇 번을 제곱해도 1이므로, nums 배열 내부에 있는 1의 개수에 따라 달려있다. 피라미드 꼴은 항상 홀수이므로, 1의 개수가 홀수일때는 그대로, 짝수일때는 1을 뺀 값을 문제에서 요구하는 최대값의 초기 값으로 정한다. ...

소개 키, 값 쌍으로 데이터를 저장하는 자료구조. 데이터 삽입, 검색, 삭제가 빠르다. (스위프트에서 사용하는 딕셔너리도 해시 테이블이다.) 해시 테이블은 키를 배열의 인덱스로 직접 사용하는 대신, 해시 함수를 통해 키를 일정한 범위의 해시 값으로 변환한다. 이 덕분에 배열 전체를 순회하지 않고도 데이터가 저장된 위치에 빠르게 접근할 수 있다. 구조 해시 테이블은 배열과 해시 함수로 구성된다. 배열: 데이터를 저장할 배열, 배열의 인덱스는 해시 값을 뜻함 해시 함수: 키를 해시 값으로 변환하는 함수 키를 해시 함수에 넣어서 계산된 해시 값을 기반으로, 배열의 인덱스에 값을 저장한다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/72412 풀이 많이 해맨 문제다. 처음에는 다음과 같이 알고리즘을 생각했다. 일단 쿼리의 개수와 info 배열의 크기를 생각해보면 filter를 사용하는 문제는 아님 바이너리 서치, Upper bound와 Lower bound의 차이가 해당하는 원소의 개수가 같음 info 배열을 잘 정렬해서 바이너리 서치만 하면 쉽게 해결될 문제 하지만 조금만 생각해보면 이러한 방식의 알고리즘은 문제를 절대로 해결할 수 없다. 우선 쿼리의 조건들이 독립적이다. 정렬 기준에 따라서 포함되어야 할 값이 포함되지 않게 된다. 그렇다고 바이너리 서치 -> 다시 정렬을 반복하기엔 차라리 filter를 쓰는게 더 시간 복잡도가 더 좋다. 다음에 생각한 방식은 트리를 이용하는 방식이었다. ...