Hash Table

문제 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를 쓰는게 더 시간 복잡도가 더 좋다. 다음에 생각한 방식은 트리를 이용하는 방식이었다. ...