문제링크: https://leetcode.com/problems/check-if-the-sentence-is-pangram/description/
1832. Check if the Sentence Is Pangram
Pangram이란 영어 알파벳의 모든 문자가 적어도 한번 나타나는 문장이다.
모두 영어 소문자인 문자열 sentence가 주어질 때, sentence가 pangram이면 true, 아니면 false를 리턴해라.
Ex)
Input: sentence = "thequickbrownfoxjumpsoverthelazydog"
Output: true
Explanation: sentence contains at least one of every letter of the English alphabet.
제약사항
1 <= sentence.length <= 1000
sentence는 영어 소문자로 이루어져있다.
아이디어:
원소의 존재 여부를 O(1)에 확인할 수 있는 hash를 이용하자.
sentence를 돌면서 hashSet에 넣고 a부터 z까지 돌면서 hashSet에 있는지 확인
하나라도 없으면 false 리턴, 끝까지 수행됐다면 true 리턴
그러면 시간 복잡도 O(n)!
import java.util.HashSet;
class Solution {
public boolean checkIfPangram(String sentence) {
Set<Character> set = new HashSet<>();
for(int i = 0; i < sentence.length(); i++){
set.add(sentence.charAt(i));
}
for(char ch = 'a'; ch <= 'z'; ch++){
if (!set.contains(ch)) return false;
}
return true;
}
}
시간이 더 빨리하려면 해시가 아닌 배열을 사용하거나, 아니면 a부터 z까지 해시에 넣고 문장에 있는 아이를 제거해서 set이 empty인지 확인하거나 여러가지 방법이 있을 것 같다.
문제링크: https://leetcode.com/problems/missing-number/description/
268. Missing Number
[0, n] 범위에 해당하는 별개의 숫자 n을 포함하는 배열 array가 주어질 때, 해당 범위에서 배열에서 누락된 유일한 숫자를 return
Ex)
Input: nums = [3,0,1]
Output: 2
Explanation:
n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
제약사항
n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
모든 nums의 원소는 유일하다. 유니크하다.
아이디어:
원소의 존재 여부를 O(1)에 확인할 수 있는 hash를 이용하자.
배열을 돌면서 hashset에 저장하고, n을 찾는다.
0 ~ n까지 돌면서 없는 요소를 찾아 리턴.
// 1번
class Solution {
public int missingNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
int n = nums[0];
for(int i = 0; i < nums.length; i++){
set.add(nums[i]);
if (n < nums[i]) n = nums[i];
}
for(int i = 0; i <= nums.length; i++){
if (!set.contains(i)) return i;
}
return -1;
}
}
// 2번
class Solution {
public int missingNumber(int[] nums) {
int length = nums.length;
int[] arr = new int[length+1];
for(int i = 0; i < length; i++){
arr[nums[i]] = 1;
}
for(int i = 0; i < length+1; i++){
if (arr[i] == 0) return i;
}
return -1;
}
}
2번이 더 빠른 이유:
- 배열의 인덱스 접근은 매우 빠르다. 반면 hashset은 해싱, 충돌 검사, 박싱/언박싱이 일어나기 때문
- 오토박싱 비용: int → Integer
- 연속된 메모리 사용
문제링크: https://leetcode.com/problems/counting-elements/description/
1426. Counting Elements
정수 배열 arr이 주어질 때, x+1이 arr에 있는 x 원소를 count해라. 만약 arr에 중복으로 있다면 따로 count해라.
Ex)
Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.
제약사항
1 <= arr.length <= 1000
0 <= arr[i] <= 1000
아이디어:
배열로 한다면 1001개의 원소를 가지는 배열을 선언해야한다. 그래도 상관없지만 그래도 해시를 사용해보자.
arr를 돌면서 해시에 넣는다. 다시 arr을 돌면서 해당 원소의 +1 값이 존재하는지 보고 존재한다면 count하자.
import java.util.HashSet;
import java.util.Set;
public class HelloWorld {
public static int countElements(int[] arr) {
int length = arr.length;
Set<Integer> set = new HashSet<>();
for(int i = 0; i < length; i++){
set.add(arr[i]);
}
int count = 0;
for(int i = 0; i < length; i++){
if(set.contains(arr[i] + 1)) count++;
}
return count;
}
public static void main(String[] args) {
int[] arr1 = new int[] {1, 2, 3};
int[] arr2 = new int[] {1, 1, 3, 3, 5, 5, 7, 7};
System.out.println(countElements(arr1) == 2);
System.out.println(countElements(arr2) == 0);
}
}문제링크: https://leetcode.com/problems/find-players-with-zero-or-one-losses/description/
2225. Find Players With Zero or One Losses
정수 배열 matches가 주어집니다. 여기서 matches[i] = [winner(i), loser(i)]는 플레이어 winner(i)가 매치에서 플레이어 loser(i)를 이겼다는 것을 나타냅니다. 크기가 2인 answer 리스트를 반환합니다. answer[0]은 한 번도 패배하지 않은 모든 플레이어의 리스트입니다. answer[1]은 정확히 한 번의 패배를 경험한 모든 플레이어의 리스트입니다. 이 값들은 반드시 오름차순으로 정렬되어야합니다.
한 경기라도 뛴 선수들만 고려해야합니다. 테스트 케이스는 두 개의 매치가 동일한 결과를 가져오지 않도록 생성됩니다.
Ex)
Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches.
Thus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].
제약사항
1 <= matches.length <= 10^5
matches[i].length == 2
1 <= winner(i), loser(i) <= 10^5
winner(i) != loser(i)
아이디어:
진 횟수를 카운트하는 해시맵을 만든다.
matches를 돌면서 이긴 사람이 해시맵에 없다면 0을 넣어준다. 진 사람은 횟수를 1 증가시켜준다.
matches를 다 돌면 진 횟수가 다 카운트되었기때문에 해시맵을 돌면서 한 번도 패배하지 않은 플레이어, 한 번만 패배를 경험한 플레이어 리스트를 만들고 정렬 후 반환
matches.length 최대 10^5, 해시맵 요소 최대 10^5, 정렬하면 nlogn 다행히 시간복잡도 O(nlogn), 공간복잡도 O(n)으로 마무리할 수 있다.
import java.util.Map;
import java.util.HashMap;
import java.util.ArrayList;
class Solution {
public List<List<Integer>> findWinners(int[][] matches) {
Map<Integer, Integer> loseCount = new HashMap<>();
for(int i = 0; i < matches.length; i++){
int winner = matches[i][0];
int loser = matches[i][1];
if (!loseCount.containsKey(winner)) loseCount.put(winner, 0);
loseCount.put(loser, loseCount.getOrDefault(loser, 0) + 1);
}
List<Integer> noLoser = new ArrayList<>();
List<Integer> oneLoser = new ArrayList<>();
for(int key : loseCount.keySet()){
if (loseCount.get(key) == 0) noLoser.add(key);
if (loseCount.get(key) == 1) oneLoser.add(key);
}
Collections.sort(noLoser);
Collections.sort(oneLoser);
return List.of(noLoser, oneLoser);
}
}
문제링크: https://leetcode.com/problems/contiguous-array/description/
525. Contiguous Array
binary array인 nums가 주어질 때 0과 1의 개수가 같은 연속된 부분 배열의 최대 길이를 return해라.
Ex)
Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
제약사항
1 <= nums.length <= 10^5
nums[i]는 0 또는 1이다.
아이디어:
nums.length의 최대값이 10^5이기 때문에 시간 복잡도가 O(n^2)인 방식은 사용할 수 없다.
처음에는 슬라이딩 윈도우를 떠올렸지만, 0과 1의 개수가 정확히 같아야 한다는 조건 때문에 적용이 어렵다고 판단했다. 슬라이딩 윈도우는 일반적으로 연속된 구간의 조건이 점진적으로 증가하거나 감소할 때 효과적인데, 이 문제는 정확한 균형을 요구하기 때문이다.
그래서 "정확히 일치해야 하는 조건"일 때 자주 사용하는 방법인 해시맵 + prefix sum 조합을 떠올렸다.
이제 고민은 “prefix sum을 어떻게 활용할 수 있을까?”였다.
0과 1의 개수가 같다는 조건을 합이 0인 서브어레이 조건으로 바꿔보면 어떨까?
이때 0을 -1로 치환하면, 0과 1의 개수가 같은 구간의 합은 무조건 0이 된다.
이렇게 바꾸고 나면, 누적합을 구해가며 같은 누적합이 이전에 나왔는지 해시맵으로 확인할 수 있다.
같은 누적합이 나온 적이 있다면, 그 사이의 구간은 합이 0이라는 의미이고,
그 구간이 조건을 만족하는 서브어레이다.
이 길이 중 가장 긴 값을 찾으면 정답이 된다.
class Solution {
public int findMaxLength(int[] nums) {
Map<Integer, Integer> mp = new HashMap<>();
mp.put(0, -1);
int sum = 0;
int ans = 0;
for (int i = 0; i < nums.length; i++) {
sum += (nums[i] == 0) ? -1 : 1;
if (mp.containsKey(sum)) {
ans = Math.max(ans, i - mp.get(sum));
} else {
mp.put(sum, i);
}
}
return ans;
}
}
문제링크: https://leetcode.com/problems/largest-unique-number/description/
1133. Largest Unique Number
정수 배열 nums가 주어질 때 한 번만 나타나는 정수 중 가장 큰 정수를 return. 만약 하나만 나타나는 정수가 없다면 -1 return.
Ex)
Input: nums = [9, 9, 8, 8]
Output: -1
Explanation:
There is no number that occurs only once.
제약사항
1 <= nums.length <= 2000
0 <= nums[i] <= 1000
아이디어:
nums를 돌면서 나타나는 횟수를 해시맵에 count합니다.
가장 큰 수를 -1로 설정하고 해시맵을 돌면서 1번만 나타난 수를 대상으로 가장 큰 수를 구합니다.
결과를 return합니다.
import java.util.HashMap;
import java.util.Map;
public class HelloWorld {
public static int largestUniqueNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for(int num : nums){
map.put(num, map.getOrDefault(num, 0) + 1);
}
int max = -1;
for(Map.Entry<Integer, Integer> entry : map.entrySet()){
if(entry.getValue() == 1 && entry.getKey() > max){
max = entry.getKey();
}
}
return max;
}
public static void main(String[] args) {
int[] arr1 = new int[] {5, 7, 3, 9, 4, 9, 8, 3, 1};
int[] arr2 = new int[] {9, 9, 8, 8};
System.out.println(largestUniqueNumber(arr1) == 8); // Output: 8
System.out.println(largestUniqueNumber(arr2) == -1); // Output: -1
}
}문제링크: https://leetcode.com/problems/ransom-note/description/
383. Ransom Note
두 문자열 ransomNote and magazine이 주어질 때, ransomNote가 magazine의 문자로 구성될 수 있다면 ture 아니면 false를 리턴.
magazine의 각 문자는 ransomNote에 한번씩만 사용할 수 있다.
Ex)
Input: ransomNote = "aa", magazine = "aab"
Output: true
제약사항
1 <= ransomNote.length, magazine.length <= 10^5
ransomNote와 magazine은 영어 소문자로 이루어져있다.
아이디어:
1. 해시맵으로 magazie의 각 문자의 개수를 센다.
2. ransomNote를 돌면서 그 문자가 hashmap에 없다면 false 있다면 숫자 1을 차감한다. 만약 차감했을 때 값이 0이라면 해시맵에서 삭제한다.
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
Map<Character, Integer> cnt = new HashMap<>();
for(char ch : magazine.toCharArray()){
cnt.put(ch, cnt.getOrDefault(ch, 0) + 1);
}
for(char ch : ransomNote.toCharArray()){
if (!cnt.containsKey(ch)) return false;
cnt.put(ch, cnt.get(ch) - 1);
if (cnt.get(ch) <= 0) cnt.remove(ch);
}
return true;
}
}
문제링크: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
3. Longest Substring Without Repeating Characters
string s가 주어질 때, 중복문자가 없는 substring 중 가장 긴 길이를 return
Ex)
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
제약사항
1 <= s.length <= 5 * 10^5
s는 영어 소문자, 숫자, Symbol, 공백으로 이루어져있다.
아이디어:
substring의 길이 => 투 포인터, 슬라이딩 윈도우가 떠올랐다.
중복 문자가 없도록 슬라이딩 윈도우로 풀자. 중복 문자 체크는 해시 맵으로 한다.
l:왼쪽 포인터, r: 오른쪽 포인터
1. r위치에 있는 문자를 해시맵에 넣는다.
2. 만약 나타난 횟수가 2번 이상 나타났다면 답을 갱신하고 중복문자가 빠질 때까지 l을 올린다.
3. r이 끝까지 가고 나면 마지막 l과 r도 중복문자없는 substring이기에 답 갱신해준다.
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> show = new HashMap<>();
int ans = 0;
int l = 0;
int r = 0;
char[] arr = s.toCharArray();
for(;r < s.length(); r++){
show.put(arr[r], show.getOrDefault(arr[r], 0) + 1);
if (show.get(arr[r]) > 1) {
ans = Math.max(ans, r - l);
while (show.get(arr[r]) > 1) {
show.put(arr[l], show.get(arr[l]) - 1);
l++;
}
}
}
ans = Math.max(ans, r - l);
return ans;
}
}
문제링크: https://leetcode.com/problems/equal-row-and-column-pairs/description/
2352. Equal Row and Column Pairs
0부터 시작하는 인덱스 n x n 정수 행렬 그리드가 주어졌을 때, 행 ri와 열 cj가 같은 쌍 (ri, cj)의 개수를 반환합니다.
Ex)
Input: grid = [[3,2,1],[1,7,6],[2,7,7]]
Output: 1
Explanation: There is 1 equal row and column pair:
- (Row 2, Column 1): [2,7,7]
제약사항
n == grid.length == grid[i].length
1 <= n <= 200
1 <= grid[i][j] <= 10^5
아이디어:
각 row를 문자열로 바꿔서 해시맵에 넣는다.
각 column을 돌면서 해시맵에 같은 문자열이 있는지 확인. 있다면 그 개수를 답에 더해준다.
class Solution {
private String convertToStr(int[] arr){
StringBuilder sb = new StringBuilder();
for(int num : arr){
sb.append(num);
sb.append(", ");
}
return sb.toString();
}
public int equalPairs(int[][] grid) {
Map<String, Integer> mp = new HashMap<>();
for(int[] row : grid){
String key = convertToStr(row);
mp.put(key, mp.getOrDefault(key, 0) + 1);
}
int length = grid.length;
int ans = 0;
for(int j = 0; j < length; j++){
int[] temp = new int[length];
for(int i = 0; i < length; i++){
temp[i] = grid[i][j];
}
String key = convertToStr(temp);
if (mp.containsKey(key)) ans += mp.get(key);
}
return ans;
}
}
'코딩테스트' 카테고리의 다른 글
| 힙 (Heap) (1) | 2025.05.20 |
|---|---|
| 해시 추가문제 (1) | 2025.05.05 |
| Two pointer (0) | 2025.04.05 |
| Prefix sum (0) | 2025.04.02 |
| Sliding Window (0) | 2025.04.01 |