카운팅
예제 - LeetCode 383. Ransom Note
https://leetcode.com/problems/ransom-note/description/?envType=study-plan-v2&envId=top-interview-150
1. 문제 이해
- magazine 알파벳을 이용하여 ransomNote를 만들 수 있는지 확인
- magazine의 각 문자는 한 번만 사용할 수 있음
2. 요구사항 분석
- 입력
- 1 <= ransomNote.length, magazine.length <= 100,000
- 모든 문자는 소문자 알파벳
- 출력
- 가능하면 true, 불가능하면 false
3. 해결 아이디어
- magazine의 알파벳 갯수를 배열에 저장
- ransomNote 알파벳을 하나씩 확인하면 갯수를 줄여 나가기
- 중간에 사용가능한 알파벳이 없다면 false 반환
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- magazine, ransomNote를 한번씩 반복하므로 O(n + m)
- 공간 복잡도
- 고정된 크기의 배열만 사용하므로 O(1)
5. 구현
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
// 1. 주어진 알파벳을 저장할 배열 할당
int[] count = new int[26];
// 2. 주어진 알파벳의 갯수를 계산
for (char c : magazine.toCharArray()) {
count[c - 'a']++;
}
// 3. 알파벳을 하나씩 사용
for (char c : ransomNote.toCharArray()) {
// 사용 가능한 알파벳이 없다면 false 반환
if (count[c - 'a'] <= 0) {
return false;
}
count[c - 'a']--;
}
return true;
}
}
예제 - LeetCode 242. Valid Anagram
1. 문제 이해
- 두 문자열이 아나그램(문자 구성은 같고 순서만 다름)인지 확인
2. 요구사항 분석
- 입력
- 1 <= s.length, t.length <= 50,000
- Follow up 조건에 맞춰 s,t는 유니코드 문자가 포함
- 출력
- 아나그램이면 true, 아니면 false
3. 해결 아이디어
- s 문자열의 문자 갯수만큼 맵을 활용해 카운팅
- t 문자열의 문자 갯수만큼 빼기
- 남은 문자 갯수가 있는 경우 아나그램이 아님
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 문자열을 하나씩 순회하므로 O(n)
- 공간 복잡도
- 문자열 크기의 맵을 사용하므로 O(n)
5. 구현
class Solution {
public boolean isAnagram(String s, String t) {
// 두 문자열의 길이가 다르면 불가능
if (s.length() != t.length()) return false;
// 1. 카운팅 맵 할당
Map<Character, Integer> count = new HashMap<>();
// 2. 문자열을 순회하며 s문자열의 문자는 1 더하고 t문자열의 문자는 1 빼기
for (int i = 0; i < s.length(); i++) {
count.put(s.charAt(i), count.getOrDefault(s.charAt(i), 0) + 1);
count.put(t.charAt(i), count.getOrDefault(t.charAt(i), 0) - 1);
}
// 3. 값이 0이 아닌 문자가 존재하면 불가능
for (int value : count.values()) {
if (value != 0) return false;
}
return true;
}
}
문자열 패턴 매칭
예제 - LeetCode 205. Isomorphic Strings
1. 문제 이해
- s의 문자들을 다른 문자로 치환하여 t를 만들 수 있는지 확인
- 각 문자는 다른 단일 문자(자기 자신 포함)로만 치환 가능하고 서로 다른 두 문자는 같은 문자로 치환 불가능
- 순서는 유지되어야 함
2. 요구사항 분석
- 입력
- 1 <= s.length <= 50,000
- s.length = t.length
- s, t는 아스키 문자
- 출력
- 가능하면 true, 불가능하면 false
3. 해결 아이디어
- 문자를 순회하며 매핑
- 다른 단어가 같은 문자로 치환될 수 없으므로 양방향 매핑으로 확인
- 이미 매핑된 단어와 다른 문자와 매핑할 필요가 있다면 불가능
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 두 문자열을 동시에 한번 순회하면 되므로 O(n)
- 공간 복잡도
- 최대 아스키코드 크기(256)의 맵을 사용하므로 O(1)
5. 구현
class Solution {
public boolean isIsomorphic(String s, String t) {
// 1. 양방향 매핑에 필요한 맵 할당, 두 문자가 같은 문자로 할당될 수 없으므로 양방향 확인 필요
Map<Character, Character> StoT = new HashMap<>();
Map<Character, Character> TtoS = new HashMap<>();
// 2. 각 문자를 순환하면서 매핑
for (int i = 0; i < s.length(); i++) {
// 2-1) 현재 문자
char c1 = s.charAt(i);
char c2 = t.charAt(i);
// 2-2) c1을 키로 c2를 매핑
if (StoT.containsKey(c1)) {
// 이미 매핑 되어 있는데 값이 다르다면 불가능
if (StoT.get(c1) != c2) return false;
} else {
StoT.put(c1, c2);
}
// 2-3) c2를 키로 c1을 매핑
if (TtoS.containsKey(c2)) {
// 이미 매핑 되어 있는데 값이 다르다면 불가능
if (TtoS.get(c2) != c1) return false;
} else {
TtoS.put(c2, c1);
}
}
return true;
}
}
예제 - LeetCode 290. Word Pattern
1. 문제 이해
- pattern과 문자열 s가 주어졌을 때 문자열이 pattern을 따르는지 확인
- 모든 문자는 하나의 고유 단어와 모든 단어는 하나의 고유 문자와 대응(일대일 대응)
2. 요구사항 분석
- 입력
- 1 <= pattern.length <= 300
- 1 <= s.length <= 3,000
- pattern은 소문자로만 이루어짐
- s는 소문자로와 공백으로만 이루어짐
- 공백으로 시작하거나 끝나지 않고 공백은 하나씩만 존재
- 출력
- pattern과 s가 일대일 대응이면 true, 아니면 false
3. 해결 아이디어
- 문자열을 공백을 기준으로 문자로 나눔
- pattern과 문자 배열을 양방향 매핑하면서 확인
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 문자열을 한번 순회하면 되므로 O(n)
- 공간 복잡도
- 패턴과 문자열 길이만큼의 두가지 맵을 사용하므로 O(n)
5. 구현
class Solution {
public boolean wordPattern(String pattern, String s) {
// 1. 문자열을 공백을 기준으로 나누기
String[] words = s.split(" ");
// 2. 문자열과 패턴의 길이가 다르면 불가능
if (pattern.length() != words.length) return false;
// 3. 패턴의 글자와 문자를 매핑항 맵 할당
Map<Character, String> charToWord = new HashMap<>();
Map<String, Character> wordToChar = new HashMap<>();
// 4. 패턴 및 문자열의 길이만큼 순회하며 양방향 매핑
for (int i = 0; i < pattern.length(); i++) {
// 4-1) 현재 글자 및 문자
char c = pattern.charAt(i);
String word = words[i];
// 4-2) 글자를 문자로 매핑
if (charToWord.containsKey(c)) {
// 이미 매핑되어 있는데 다른 값이라면 불가능
if (!charToWord.get(c).equals(word)) return false;
} else {
charToWord.put(c, word);
}
// 4-3) 문자를 글자로 매핑
if (wordToChar.containsKey(word)) {
// 이미 매핑되어 있는데 다른 값이라면 불가능
if (!wordToChar.get(word).equals(c)) return false;
} else {
wordToChar.put(word, c);
}
}
return true;
}
}
그룹화
예제 - LeetCode 49. Group Anagrams
1. 문제 이해
- 아나그램끼리 그룹화하기
2. 요구사항 분석
- 입력
- 1 <= strs.length <= 10,000
- 0 <= strs[i].length <= 100
- strs[i]는 소문자 알파벳만 포함
- 출력
- 아나그램끼리 묶인 리스트
3. 해결 아이디어
- 각각의 문자열을 정렬하면 같은 아나그램끼리 같은 값이 나옴
- 해당 값을 키로 하는 맵에 문자열들을 저장 후 리스트로 반환
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 문자 갯수만큼 정렬을 진행하므로 O(n * klogk)
- 공간 복잡도
- 문자열의 길이만큼의 맵과 그 값으로 리스트를 사용하므로 O(n * k)
5. 구현
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 1. 그룹화 할 맵 할당
Map<String, List<String>> map = new HashMap<>();
// 2. 문자열을 순회하면서 맵에 그룹화
for (String s : strs) {
// 2-1) 문자를 정렬하여 키 찾기
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
// 2-2) 키에 문자를 값으로 넣기
map.putIfAbsent(key, new ArrayList<>());
map.get(key).add(s);
}
// 3. 맵에 값들을 리스트로 반환
return new ArrayList<>(map.values());
}
}
인덱스 매핑
예제 - LeetCode 1. Two Sum
https://leetcode.com/problems/two-sum/description/?envType=study-plan-v2&envId=top-interview-150
1. 문제 이해
- 배열에서 두 수를 합해 target이 되는 두 인덱스 구하기
- 같은 요소를 두 번 사용할 수 없으며, 정확히 하나의 해만 존재
2. 요구사항 분석
- 입력
- 2 <= nums.length <= 10,000
- -1,000,000,000 <= nums[i], target <= 1,000,000,000
- 출력
- 인덱스 배열
3. 해결 아이디어
- 배열의 값을 키로 인덱스를 값으로 맵에 해싱
- target - 현재값이 맵에 키로 있으면 두 인덱스를 출력
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 배열을 한번 순회하므로 O(n)
- 공간 복잡도
- 배열 길이의 맵을 사용하므로 O(n)
5. 구현
class Solution {
public int[] twoSum(int[] nums, int target) {
// 1. 인덱스를 매핑할 맵 할당
Map<Integer, Integer> map = new HashMap<>();
// 2. 배열을 순회하며 인덱스 매핑 + 답 찾기
for (int i = 0; i < nums.length; i++) {
// 2-1) target을 만들기 위해 필요한 값
int complement = target - nums[i];
// 2-2) 맵에 해당 값이 있다면 두 인덱스를 출력
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
// 2-3) 현재 값 인덱스 매핑
map.put(nums[i], i);
}
// 정답이 없는 경우 -> 현재 문제에는 답이 존재
return new int[]{-1, -1};
}
}
특정 값 조회
예제 - LeetCode 202. Happy Number
1. 문제 이해
- 행복한 수 찾기
- 행복한 수는 양의 정수에서 시작해서 각 자릿수의 제곱합을 구해가며 결과가 1인 수
2. 요구사항 분석
- 입력
- 1 <= n <= int의 양의 범위
- 출력
- 행복한 수이면 true, 아니면 false
3. 해결 아이디어
- 제곱합을 하면서 각 수를 저장
- 중복된 수(이미 제곱합을 구했던)가 다시 나오면 사이클이므로 불가능
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 반복되는 수가 일정 크기(약 243) 이하이므로 O(1)
- 공간 복잡도
- Set의 최대 크기(약 243)가 제한적이므로 O(1)
5. 구현
class Solution {
public boolean isHappy(int n) {
// 1. 중복을 확인할 셋 할당
Set<Integer> seen = new HashSet<>();
// 2. n이 1이 될때까지 확인
while (n != 1) {
// 2-1) 이미 확인한 값이 다시 나오면(사이클) 행복한 수가 아님
if (seen.contains(n)) return false;
// 2-2) 현재 값을 셋에 넣고 제곱합 구하기
seen.add(n);
n = getDigitSquareSum(n);
}
// 3. n이 1이 됐으므로 행복한 수
return true;
}
// 제곱합
private int getDigitSquareSum(int n) {
// 1. 합을 저장할 변수 할당
int sum = 0;
// 2. 각 자릿수를 하나씩 제곱하면서 더하기
while (n > 0) {
// 2-1) 현재 자릿수(오른쪽 끝)
int digit = n % 10;
// 2-2) 자릿수를 제곱해서 더하기
sum += digit * digit;
// 2-3) 현재 자릿수 제거
n /= 10;
}
return sum;
}
}
예제 - LeetCode 219. Contains Duplicate 2
1. 문제 이해
- 배열 내에서 nums[i] == nums[j] 이면서 abs(i - j) <= k인 두 인덱스 찾기
2. 요구사항 분석
- 입력
- 1 <= nums.length <= 100,000
- -1,000,000,000 <= nums[i], target <= 1,000,000,000
- 0 <= k <= 100,000
- 출력
- 조건을 만족하는 두 인덱스가 있으면 true, 없으면 false
3. 해결 아이디어
- 배열의 일정 범위(윈도우) 내에서 중복된 값을 HashSet을 사용하여 찾기
- 범위를 초과하면 이전 값들을 하나씩 줄여가며 범위 유지하기
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 배열을 한 번 순회하므로 O(n)
- 공간 복잡도
- 최대 k 크기로 set을 유지하므로 O(k)
5. 구현
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
// 1. 중복된 값이 존재하는지 확인할 set 할당
Set<Integer> window = new HashSet<>();
// 2. 배열을 순회하면서 중복인 값 찾기
for (int i = 0; i < nums.length; i++) {
// 2-1) 중복된 값이 존재하면 true 반환
if (window.contains(nums[i])) {
return true;
}
// 2-2) 현재 값 셋에 넣기
window.add(nums[i]);
// 2-3 윈도우 크기 유지
if (window.size() > k) {
window.remove(nums[i - k]);
}
}
return false;
}
}
예제 - LeetCode 128. Longest Consecutive Sequence
1. 문제 이해
- 주어진 배열에서 연속된 정수로 이루어진 최장 수열 구하기
- 시간복잡도 O(n)으로 해결해야 함 -> 정렬 불가
2. 요구사항 분석
- 입력
- 0 <= nums.length <= 100,000
- -1,000,000,000 <= nums[i] <= 1,000,000,000
- 출력
- 최장 수열의 길이
3. 해결 아이디어
- 모든 값을 HashSet에 넣기
- x - 1이 있는지 확인하여 시작점 체크
- 시작점부터 x + 1이 있는지 확인하며 길이 계산
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 배열을 한 번 순회하므로 O(n)
- 공간 복잡도
- n크기의 HashSet이 필요하므로 O(k)
5. 구현
class Solution {
public int longestConsecutive(int[] nums) {
// 1. 배열의 수들을 저장할 HashSet 할당
Set<Integer> set = new HashSet<>();
// 2. 배열의 수를 저장
for (int num : nums) {
set.add(num);
}
int longest = 0; // 최장 수열 길이
// 3. set을 순회하며 최장 길이 구하기
for (int num : set) {
// 3-1) 시작 지점인 경우만 수열 길이 계산
if (!set.contains(num - 1)) {
int currentNum = num; // 현재 수
int length = 1; // 현재 길이
// 3-2) 1씩 큰 수가 있는지 확인
while (set.contains(currentNum + 1)) {
currentNum++;
length++;
}
// 3-3) 최장 길이 갱신
longest = Math.max(longest, length);
}
}
return longest;
}
}'코딩테스트 > 알고리즘' 카테고리의 다른 글
| 예제로 배우는 알고리즘 - 슬라이딩 윈도우 (0) | 2025.05.02 |
|---|---|
| 예제로 배우는 알고리즘 - 문자열 (0) | 2025.04.28 |
| 예제로 배우는 알고리즘 - 배열 (0) | 2025.04.13 |
| 예제로 배우는 알고리즘 - 비트 마스킹 (0) | 2025.04.04 |
| 예제로 배우는 알고리즘 - 수학 (0) | 2025.03.29 |