문제 설명
주어진 정수 배열 numbers와 정수 target이 있다.
numbers 배열의 원소 중에서 어떤 두 원소를 합하여 나머지가 target이 되도록 할 수 있는지를 확인해야 한다.
가능한 경우에는 그 두 원소의 인덱스를 반환하고, 그렇지 않으면 -1을 반환하시오.
단, 각 원소는 한 번만 사용해야 하며, 같은 원소를 두 번 선택할 수 없다.
입력 형식
numbers: 정수 배열 (0 ≤ numbers.length ≤ 105, -109 ≤ numbers[i] ≤ 109)target: 정수 (0 ≤ target ≤ 109)
출력 형식
두 원소의 인덱스 또는 -1
문제 풀이 과정
1. 문제 분석
이 문제는 특이하게 두 원소를 더한 후 나머지 연산을 통해 target을 얻는 문제입니다. 즉,
우리가 찾고자 하는 두 수 x와 y가 있을 때,
(x + y) % target == target이어야 합니다. 여기서 더하기와 나머지 조건이 가지는 의미를 잘 이해해야 합니다.
2. 알고리즘 설계
이 문제를 해결하기 위해 배열을 한 번만 순회하면서, 각 원소를 목표 식에 맞추어 나머지를 계산하겠습니다.
한 가지 방법으로는 해시셋을 사용하여 과거의 값들을 저장하고, 현재 값과 함께 나머지를 계산하여 조건을 확인하는 방법입니다.
해시셋을 사용하는 이유는 평균적인 시간복잡도를 O(1)로 유지할 수 있기 때문입니다.
3. 코드 작성
이제 이러한 알고리즘을 C#로 구현해 보겠습니다. 아래는 해결책 코드입니다.
using System;
using System.Collections.Generic;
public class Solution
{
public int[] FindTwoElementsWithTargetModulo(int[] numbers, int target)
{
// 원소의 위치를 저장하기 위한 딕셔너리
Dictionary valueToIndex = new Dictionary();
for (int i = 0; i < numbers.Length; i++)
{
// 현재 원소에 대해 나머지 값을 계산
int requiredValue = (target - numbers[i]) % target;
// 이미 나머지 값이 딕셔너리에 존재하는지 확인
if (valueToIndex.ContainsKey(requiredValue))
{
return new int[] { valueToIndex[requiredValue], i };
}
// 현재 원소를 딕셔너리에 기록
if (!valueToIndex.ContainsKey(numbers[i]))
{
valueToIndex[numbers[i]] = i;
}
}
// 조건을 만족하는 두 원소가 없는 경우
return new int[] { -1 };
}
}
4. 시간 복잡도
이 알고리즘의 시간 복잡도는 O(n)입니다. 한 번의 배열 순회로 결과를 찾을 수 있습니다.
또한 추가적인 공간 복잡도는 O(n)으로, 해시셋을 사용하여 값을 저장하기 때문입니다.
5. 테스트 케이스
다양한 테스트 케이스를 작성하여 작동 여부를 확인해보겠습니다.
public class Program
{
public static void Main()
{
Solution solution = new Solution();
// 테스트 케이스 1
int[] numbers1 = { 1, 2, 3, 4, 5 };
int target1 = 5;
int[] result1 = solution.FindTwoElementsWithTargetModulo(numbers1, target1);
Console.WriteLine(string.Join(", ", result1)); // 예상 출력: 0, 4
// 테스트 케이스 2
int[] numbers2 = { 1, 2, 3, 7 };
int target2 = 5;
int[] result2 = solution.FindTwoElementsWithTargetModulo(numbers2, target2);
Console.WriteLine(string.Join(", ", result2)); // 예상 출력: 0, 2
// 테스트 케이스 3
int[] numbers3 = { 3, 8, 12, 5 };
int target3 = 10;
int[] result3 = solution.FindTwoElementsWithTargetModulo(numbers3, target3);
Console.WriteLine(string.Join(", ", result3)); // 예상 출력: -1
}
}
6. 맺음말
이번 강좌에서는 나머지 합을 구하는 문제를 해결하기 위해 해시셋을 사용하여 공간과 시간을 최적화하는 방법을 학습했습니다.
코딩 테스트에서 나오는 다양한 문제를 풀기 위해서는 이러한 접근 방식이 매우 유용합니다.
더 많은 알고리즘 문제를 풀며 자신감을 쌓아 나가길 바랍니다.