242. 유효한 애너그램 (Valid Anagram)
두 문자열이 서로 애너그램 관계인지 확인하는 문제입니다. 애너그램이란 문자의 순서만 다르고 구성 문자와 그 개수가 동일한 경우를 의미합니다.
최적화된 구현
문자열의 길이가 다르면 애너그램이 될 수 없으므로 조기 반환(Early Return)을 적용합니다. 또한, 소문자 알파벳으로만 구성된다는 제약 조건이 있으므로 해시 테이블(Dictionary) 대신 고정 크기의 배열을 사용하여 메모리 할당 오버헤드와 해시 충돌 가능성을 제거합니다.
public class Solution {
public bool IsAnagram(string s, string t) {
if (s.Length != t.Length) return false;
int[] frequency = new int[26];
for (int i = 0; i < s.Length; i++) {
frequency[s[i] - 'a']++;
frequency[t[i] - 'a']--;
}
return frequency.All(count => count == 0);
}
}핵심 인사이트
- 배열을 해시 테이블로 활용: 키의 범위가 제한적이고 연속적일 때(예: 영소문자 26개, 숫자 10개),
Dictionary대신 배열을 사용하면 인덱싱을 통해 O(1) 시간에 접근할 수 있어 성능이 크게 향상됩니다. - 단일 패스(Single Pass) 최적화: 두 문자열을 동시에 순회하며 하나의 배열에 증감을 기록하면 반복문을 줄일 수 있습니다.
349. 두 배열의 교집합 (Intersection of Two Arrays)
두 배열의 교집합을 구하되, 결과 배열의 각 요소는 고유해야 합니다.
최적화된 구현
중복을 자동으로 제거하고 빠른 조회를 지원하기 위해 HashSet을 활용합니다. 불필요한 불리언 플래그 관리 없이 집합 연산의 특성을 그대로 이용합니다.
public class Solution {
public int[] Intersection(int[] nums1, int[] nums2) {
HashSet<int> uniqueNums = new HashSet<int>(nums1);
HashSet<int> intersection = new HashSet<int>();
foreach (int num in nums2) {
if (uniqueNums.Contains(num)) {
intersection.Add(num);
}
}
return intersection.ToArray();
}
}핵심 인사이트
- 데이터 구조의 적절한 선택: 해시 값이 희소하거나 데이터의 범위(Span)가 매우 커서 배열을 사용하면 메모리 낭비가 발생하는 경우,
HashSet이나Dictionary가 적합합니다. - 자동 중복 제거:
HashSet의Add메서드는 이미 존재하는 요소를 무시하므로, 결과 리스트에 추가하기 전에 중복 여부를 따로 검사할 필요가 없어 코드가 간결해집니다.
202. 행복수 (Happy Number)
주어진 숫자의 각 자릿수를 제곱하여 더하는 과정을 반복할 때, 최종적으로 1이 되는지 아니면 무한 루프에 빠지는지 판별하는 문제입니다.
최적화된 구현
기존에는 HashSet을 사용하여 이전에 등장한 숫자를 기록하고 무한 루프를 감지했습니다. 이를 공간 복잡도 O(1)인 플로이드의 순환 검출 알고리즘(Floyd's Cycle-Finding Algorithm, 일명 토끼와 거북이 알고리즘)으로 대체하여 메모리 사용을 최적화합니다.
public class Solution {
public bool IsHappy(int n) {
int slow = n;
int fast = CalculateNext(n);
while (fast != 1 && slow != fast) {
slow = CalculateNext(slow);
fast = CalculateNext(CalculateNext(fast));
}
return fast == 1;
}
private int CalculateNext(int number) {
int sum = 0;
while (number > 0) {
int digit = number % 10;
sum += digit * digit;
number /= 10;
}
return sum;
}
}핵심 인사이트
- 순환(Cycle) 감지 기법: 상태 전이가 유한한 범위 내에서 이루어질 경우, 해시 테이블로 방문 기록을 남기지 않더라도 포인터의 속도 차이를 이용해 순환 여부를 O(1) 공간으로 판별할 수 있습니다.
- 수학적 연산 로직 분리: 자릿수 제곱 합을 구하는 로직을 별도 메서드로 분리하면, 포인터 이동 로직이 명확해지고 코드 재사용성이 높아집니다.
1. 두 수의 합 (Two Sum)
배열에서 합쳐서 목표값(Target)이 되는 두 숫자의 인덱스를 찾는 문제입니다.
최적화된 구현
이중 반복문을 통한 O(N^2) 접근을 피하고, 해시 맵을 사용하여 탐색 시간을 O(1)로 단축시켜 전체 시간 복잡도를 O(N)으로 만듭니다. C#의 TryGetValue와 인덱서를 활용하여 해시 테이블 탐색 및 삽입 로직을 효율적으로 작성합니다.
public class Solution {
public int[] TwoSum(int[] nums, int target) {
Dictionary<int, int> numToIndex = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++) {
int complement = target - nums[i];
if (numToIndex.TryGetValue(complement, out int complementIndex)) {
return new int[] { complementIndex, i };
}
numToIndex[nums[i]] = i;
}
return Array.Empty<int>();
}
}핵심 인사이트
- 탐색과 삽입의 동시 수행: 배열을 순회하면서 현재 요소의 짝(Complement)이 해시 맵에 있는지 확인하고, 없으면 현재 요소를 해시 맵에 추가합니다. 이 방식을 사용하면 단일 패스로 문제를 해결할 수 있습니다.
- C# 딕셔너리 최적화:
ContainsKey후 인덱서로 값을 가져오면 해시 코드를 두 번 계산하게 됩니다.TryGetValue를 사용하면 한 번의 해시 계산으로 존재 여부와 값을 동시에 얻을 수 있습니다. 또한,dict[key] = value구문은 키가 존재하지 않으면 추가하고, 존재하면 덮어쓰므로Add메서드의 예외 처리나 중복 검사를 생략할 수 있습니다.