Problem Solving

문제 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/25/A 풀이 n 개의 원소를 가진 수열이 입력으로 들어오고 입력으로 들어온 숫자 중 홀/짝이 다른 하나의 숫자의 인덱스(1-base 인덱스)를 출력하면 된다. 수열이 들어올 때마다 홀/짝 각각의 마지막 인덱스를 저장하고, 홀수의 개수, 짝수의 개수를 세면된다. 마지막 이렇게 얻어진 개수로 홀/짝인지 판별을 한 뒤에, 홀수면 짝수의, 짝수면 홀수의 마지막 인덱스를 출력하면 된다. 코드 #include <iostream> int main() { int n; std::cin >> n; int oddCount = 0; int evenCount = 0; int oddIndex = 0; int evenIndex = 0; for (int i = 1; i <= n; ++i) { int number; std::cin >> number; if (number % 2 == 0) { evenCount++; evenIndex = i; } else { oddCount++; oddIndex = i; } } std::cout << (oddCount == 1 ? oddIndex : evenIndex) << std::endl; }

문제 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/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://leetcode.com/problems/number-of-unique-xor-triplets-ii 풀이 n 길이의 배열 nums가 주어지고, 여기에서 3개의 인덱스 i, j, k를 (i <= j <= k) 뽑아서 XOR 했을 때, 얻을 수 있는 모든 결과의 수를 리턴하는 문제이다. Leetcode 3513 문제와 다른 점은, nums가 순열이 아니다. 따라서, 자연스럽게 모든 경우의 수를 커버하지 못한다. 다만, 인덱스 제약조건이 저번과 같으므로 ‘값 3개를 무작위’로 뽑는다는 점은 같다. 여전히 n이 최대 1500이기 때문에, $O(n^3)$ 으로 풀기에는 무리가 있다. 우선, 값의 중복을 가리지 않고, 인덱스도 가리지 않으므로 배열의 순서가 중요하지 않다. 따라서 배열에 있는 모든 중복을 제거하는 전처리를 한다. ...

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

문제 https://leetcode.com/problems/number-of-unique-xor-triplets-i 풀이 1에서 n까지의 모든 값이 들어있는 n 크기 배열 nums 배열이 주어지고, 그 배열에서 인덱스 3개 i, j, k (i <= j <= k)를 골라서 XOR 했을 때, 나올 수 있는 모든 값을 리턴하면 되는 문제이다. nums 배열의 크기가 10만이고, 브루트 포스를하면 시간 복잡도가 $O(n^3)$ 이기 때문에 시간 내에 해결할 수 없다. nums가 순열이라는 것과 XOR의 연산 특징을 알면 생각보다 간단한 공식으로 해결할 수 있다. 우선 인덱스 제약조건은 없는 것과 마찬가지인데, 등호를 포함한 대소관계이기 때문에, 인덱스를 중복해서 골라도 된다. ...

문제 https://leetcode.com/problems/maximize-active-section-with-trade-i 풀이 '0'와 '1'로만 이루어진 문자열 s가 존재하고, 문제에서 주어진 연산을 최대 1번 적용하여 문자열에 있는 '1'의 개수를 최대로 만든 뒤 그 개수를 리턴하면 된다. 주어진 연산은 다음과 같다. (순서대로 둘 다 적용해야 한다.) 양 옆이 '0'로 둘러싸인 연속된 '1' 블록 하나를 선택해서 모두 '0'로 바꾼다. 양 옆이 '1'으로 둘러싸인 연속된 '0' 블록 하나를 선택해서 모두 '1'으로 바꾼다. 문제에서 s의 양 옆에 '1'을 붙이라 했는데, 이때 추가된 '1'은 최종 반환값에 포함되지 않는다. ...

문제 https://codeforces.com/problemset/problem/1/A 풀이 Codeforces에서 푼 첫 문제. $n \times m$ 크기의 직사각형 도시가 있고, 그 도시를 $a \times a$ 크기의 타일로 뒤덮는 문제이다. 타일은 도시 경계를 넘어가도 되지만, 잘라선 안되고 겹쳐도 안된다. 즉, 필요한 타일의 개수는 가로/세로 각각을 $a$로 나눈 값을 올림하여 곱하면 된다. 문제에 간단한 함정이 하나 있는데, n, m, a의 범위가 최대 $10^9$이라 곱셈 결과가 int 범위를 넘어갈 수 있으므로 long long을 사용을 사용해야 한다. 코드 #include <iostream> #include <cmath> int main() { long long n, m, a; std::cin >> n >> m >> a; std::cout << ((n + a - 1) / a) * ((m + a - 1) / a) << std::endl; return 0; }