C# 코딩테스트 강좌, 나머지 합 구하기

문제 풀이 과정

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. 맺음말

이번 강좌에서는 나머지 합을 구하는 문제를 해결하기 위해 해시셋을 사용하여 공간과 시간을 최적화하는 방법을 학습했습니다.
코딩 테스트에서 나오는 다양한 문제를 풀기 위해서는 이러한 접근 방식이 매우 유용합니다.
더 많은 알고리즘 문제를 풀며 자신감을 쌓아 나가길 바랍니다.