Sorting

문제 https://codeforces.com/problemset/problem/276/C 풀이 크기 n인 수열 a와 쿼리 q개가 주어진다. 각 쿼리는 인덱스 $[l, r]$ 범위를 지정하며, 해당 범위의 원소 합을 구한다. 수열 a를 적절히 재배열하여 모든 쿼리의 합의 총합을 최대화 한 수를 출력하면 된다. 쿼리가 여러번 나오고 어떤 원소들은 쿼리 안에 중복되어서 포함되어 있을 수 있다. 쿼리의 범위 안에 가장 많이 포함된 원소의 순서대로, 높은 값을 배치하는 정렬 문제로 환원된다. 어떤 원소 $a_i$가 쿼리 내부에 포함되어 있는지를 일반적으로 판단하게 되면 $O(q \times n)$이 되는데, q, n의 범위가 $1 \leq q 2 \times 10^5$ 이므로, 시간 안에 문제를 해결하기 어려워진다. ...

문제 https://leetcode.com/problems/find-missing-elements 풀이 연속된 정수 구간에 속한 모든 정수가 들어 있’던’ 수열 nums가 주어진다. 일부 원소가 사라진 상태인 상태인데, 이 사라진 원소들을 배열에 오름차순으로 담아 리턴하면 된다. 최대값과 최소값은 사라지지 않았다고 하니까, 정수 구간의 크기를 구할 수 있다. 그 정수 구간을 순회하면서 빠진 원소들을 찾으면 된다. 정렬을 이용해서 풀 수도 있는데, 이러면 시간 복잡도가 평균 $O(n \times \log n)$이 된다. 큰 차이는 안나지만 Hast Set을 이용하면 평균 $O(n)$에 풀 수 있다. ...

문제 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://leetcode.com/problems/maximum-product-of-three-numbers 풀이 정수형 배열 nums 안에서 세 개의 수를 뽑아 곱한 값 중 최대값을 리턴하면 된다. LeetCode 3536 3536번 문제처럼 nums 배열을 정렬하면 된다. 다만 이번에는 3개의 수를 뽑아야 하기에, 음수, 음수, 양수도 정답의 후보가 될 수 있다. 따라서 정답의 후보는 다음과 같다. 가장 작은 값 2개와 가장 큰 값 1개를 곱한 값 가장 큰 값 3개를 곱한 값 이 두 수를 계산한 다음, 대소를 비교해서 리턴하면 된다. 코드 class Solution: def maximumProduct(self, nums: List[int]) -> int: nums.sort() return max(nums[-1] * nums[-2] * nums[-3],nums[0] * nums[1] * nums[-1])

문제 https://leetcode.com/problems/maximum-product-of-two-digits 풀이 10 이상 10억 이하의 정수 n이 주어지고, 각 자리수 중 두 개를 골라서 곱한 값중 가장 큰 수를 리턴하면 되는 문제이다. 문제의 힌트에선 브루트 포스를 사용하라 했는데, 정렬하면 더 쉽게 풀 수 있다. 코드 class Solution: def maxProduct(self, n: int) -> int: digits = sorted(str(n), reverse=True) return int(digits[0]) * int(digits[1])

문제 https://codeforces.com/contest/492/problem/B 풀이 길의 길이 l과 가로등의 위치 배열 a가 주어지고, 모든 가로등이 길 전체를 비춰야 할때, 가로등 하나가 비추는 거리 d를 출력하는 문제이다. 문제 풀이는 단순하다. 가로등 사이의 간격을 계산하고, 그 간격을 모두 채울수만 있으면 된다. 가로등이 길을 비추는 건 3가지 케이스로 생각해볼수 있다. 시작 가로등 (양 옆에 가로등이 있는) 중간 가로등 끝 가로동 1번 3번 케이스가 엣지 케이스인데, 중간 가로등은 가로등 사이의 거리의 절반 만큼만 비추면 되지만, 시작 가로등과 끝 가로등은 시작점과 자신의 위치까지를 모두 스스로 비춰야 해서, 따로 처리해줘야 한다. ...

문제 https://leetcode.com/problems/rank-transform-of-an-array 풀이 배열의 각 원소를 크기 기준으로 순위로 변환해 리턴하는 문제이다. 배열을 정렬한 뒤 각 원소에 순위를 매핑하고, 원본 배열 순서대로 순위를 꺼내 리턴한다. 문제에서 주의점이 하나 있는데, 같은 숫자는 같은 순위를 가진다는 것이다. 따라서 매핑할 때, 중복처리를 해줘야 한다. 코드 class Solution: def arrayRankTransform(self, arr: List[int]) -> List[int]: sortedArr = sorted(arr) rankDict = {} rank = 1 for element in sortedArr: if not element in rankDict: rankDict[element] = rank rank += 1 return list(map(lambda x: rankDict[x], arr))

문제 https://leetcode.com/problems/remove-covered-intervals 풀이 여러 개의 구간이 주어지고, 다른 구간에 완전히 포함되는 구간을 제거한 이후, 남은 구간의 개수를 리턴하면 되는 문제이다. 가장 쉬운 방법은 브루트 포스이다. 구간의 개수가 최대 1000개이기 때문에, O(n^2) 방식을 사용해도 충분히 통과 가능하다. 하지만 정렬을 이용하면 쉽게 O(n * log(n)) 으로 풀 수 있다. 구간 시작 부분을 기준으로 오름차순 정렬한다. 시작 부분이 같은 경우엔 끝 부분을 기준으로 내림차순 정렬한다. 정렬된 배열을 앞에서부터 순회하며, 지금까지 등장한 끝 부분의 최대값(maxEnd)을 추적한다. 현재 구간의 끝이 maxEnd보다 크면, 이전 어떤 구간에도 포함되지 않는 새로운 구간이므로 카운트하고 maxEnd를 갱신한다. 현재 구간의 끝이 maxEnd보다 작거나 같으면, 이전 구간에 완전히 포함되는 구간이므로 제거한다. 1번에서 시작 부분 기준으로 정렬했기 때문에, 시작 조건은 자동으로 만족되어 끝 부분만 비교하면 충분하다. ...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/152995 풀이 정렬 문제다. 두 개의 수를 가진 튜플(혹은 배열)이 있고, 두 수의 합이 아닌, 각 수를 개별적으로 두 값이 모두 작거나 큰지 판단해야 하는 경우에는 첫 번째 기준이 되는 값은 오름차순, 그리고 두 번째 기준이 되는 값은 내림차순으로 정렬하는 것이 일반적이다. 반대도 가능하고, 이 문제에서도 첫 번째 기준이 되는 값을 내림차순, 두 번째 기준이 되는 값을 오름차순으로 정렬하는 것이 더 편하다. 순위를 셀 때도 조금은 최적화할 수 있다. 제거해야할 원소들을 제거하고 새로운 배열을 만드는 것이 아닌, 그냥 배열을 순회하면서, 기준이 되는 원소보다 큰 수를 카운트 하면 된다. ...