정수 배열 nums가 주어졌을 때, 배열에 값이 두 번 이상 나타나면 true를 반환하고, 모든 요소가 다르면 false를 반환합니다.
제약사항
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> appear = new HashSet<>();
for(int num : nums){
if (!appear.add(num))
return true;
}
return false;
}
}
배열 paths가 주어집니다. 여기서 paths[i] = [cityAi, cityBi]는 cityAi에서 cityBi로 가는 직접 경로가 존재함을 의미합니다. 목적지 도시, 즉 다른 도시로 나가는 경로가 없는 도시를 반환합니다.
경로 그래프는 루프가 없는 직선을 형성하므로 목적지 도시는 정확히 하나라는 것이 보장됩니다.
제약사항
- 1 <= paths.length <= 100
- path[i].length == 2
- 1 <= cityAi.length, cityBi.length <= 10
- cityAi != cityBi
- 모든 문자열은 소문자와 대문자의 영어 문자와 공백 문자로 구성됩니다.
아이디어
hashmap에 출발지에 있었던 횟수를 담는다. 만약 도착지가 Hashmap에 없다면 0으로 담습니다.
최종적으로 value값이 0인 것이 답이 됩니다.
class Solution {
public String destCity(List<List<String>> paths) {
Map<String, Integer> mp = new HashMap<>();
for(List<String> path : paths){
String st = path.get(0);
String dt = path.get(1);
mp.put(st, mp.getOrDefault(st, 0) + 1);
if (mp.getOrDefault(dt, 0) == 0) {
mp.put(dt, 0);
}
}
for(String key : mp.keySet()){
if (mp.get(key) == 0) return key;
}
return "error";
}
}
모범답안
class Solution {
public String destCity(List<List<String>> paths) {
HashMap<String, String> map = new HashMap<>();
for(List<String> path: paths){
map.put(path.get(0), path.get(1));
}
String city = paths.get(0).get(0);
while(map.keySet().contains(city)){
city = map.get(city);
}
return city;
}
}
문자열 경로가 주어지고, path[i] = 'N', 'S', 'E' 또는 'W'는 각각 북쪽, 남쪽, 동쪽, 서쪽으로 한 단위씩 이동함을 나타냅니다. 2D 평면의 원점 (0, 0)에서 출발하여 path로 지정된 경로를 따라 이동합니다. 경로가 임의의 지점에서 교차하는 경우, 즉 이전에 방문한 위치에 있는 경우 true를 반환합니다. 그렇지 않으면 false를 반환합니다.
제약사항
- 1 <= path.length <= 10^4
- path[i]는 'N', 'S', 'E' 또는 'W'입니다.
class Solution {
private int[] diff(char dir){
int[] arr = new int[2];
switch(dir){
case 'N': arr[0] = 1; break;
case 'S': arr[0] = -1; break;
case 'E': arr[1] = 1; break;
case 'W': arr[1] = -1; break;
}
return arr;
}
public boolean isPathCrossing(String path) {
int x = 0;
int y = 0;
Set<String> points = new HashSet<>();
points.add(x + " " + y);
for(char ch : path.toCharArray()){
int[] arr = diff(ch);
y += arr[0];
x += arr[1];
if (!points.add(x + " " + y)){
return true;
}
}
return false;
}
}
정수 배열 nums가 주어집니다. 배열의 고유한 요소는 배열에 정확히 한 번 나타나는 요소입니다.
nums의 모든 고유한 요소의 합계를 반환합니다.
제약사항
- 1 <= nums.length <= 100
- 1 <= nums[i] <= 100
class Solution {
public int sumOfUnique(int[] nums) {
Map<Integer, Integer> cnt = new HashMap<>();
for(int num : nums){
cnt.put(num, cnt.getOrDefault(num, 0) + 1);
}
int sum = 0;
for(int key : cnt.keySet()){
int value = cnt.get(key);
if (value == 1) sum += key;
}
return sum;
}
}
3005. Count Elements With Maximum Frequency
양의 정수로 구성된 nums 배열이 주어집니다. nums 배열에 있는 모든 요소의 총 빈도를 반환하되, 해당 요소가 모두 최대 빈도를 갖도록 합니다. 요소의 빈도는 배열에서 해당 요소가 나타나는 횟수입니다.
제약사항
- 1 <= nums.length <= 100
- 1 <= nums[i] <= 100
class Solution {
public int maxFrequencyElements(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int max = 0;
for(int num : nums){
map.put(num, map.getOrDefault(num, 0) + 1);
max = Math.max(max, map.get(num));
}
int sum = 0;
for(int value : map.values()){
if (value == max) sum += value;
}
return sum;
}
}1394. Find Lucky Integer in an Array
정수 arr 배열이 주어졌을 때, 행운의 정수는 배열에서 해당 값과 같은 빈도를 갖는 정수입니다. 배열에서 가장 큰 행운의 정수를 반환합니다. 행운의 정수가 없으면 -1을 반환합니다.
제약사항
- 1 <= arr.length <= 500
- 1 <= arr[i] <= 500
class Solution {
public int findLucky(int[] arr) {
Map<Integer, Integer> cnt = new HashMap<>();
for(int num : arr){
cnt.put(num, cnt.getOrDefault(num, 0) + 1);
}
int max = -1;
for(int key : cnt.keySet()){
if (key == cnt.get(key)) max = key;
}
return max;
}
}
1207. Unique Number of Occurrences
정수 arr 배열이 주어졌을 때, 배열 내 각 값의 발생 횟수가 고유한 경우 true를 반환하고 그렇지 않으면 false를 반환합니다.
제약사항
- 1 <= arr.length <= 1000
- -1000 <= arr[i] <= 1000
class Solution {
public boolean uniqueOccurrences(int[] arr) {
Map<Integer, Integer> cnt = new HashMap<>();
Set<Integer> occurrences = new HashSet<>();
for(int num : arr){
cnt.put(num, cnt.getOrDefault(num, 0) + 1);
}
for(int key : cnt.keySet()){
if (!occurrences.add(cnt.get(key))) return false;
}
return true;
}
}
451. Sort Characters By Frequency
문자열 s가 주어졌을 때, 문자의 빈도를 기준으로 내림차순으로 정렬합니다. 문자의 빈도는 문자열에 나타나는 횟수입니다. 정렬된 문자열을 반환합니다. 답이 여러 개인 경우, 그중 하나를 반환합니다.
제약사항
- 1 <= s.length <= 5 * 10^5
- s는 대문자, 소문자 영어 문자와 숫자로 구성됩니다.
class Solution {
public class Pair {
char key;
int value;
public Pair(char key, int value){
this.key = key;
this.value = value;
}
}
public String frequencySort(String s) {
Map<Character, Integer> cnt = new HashMap<>();
for(int i = 0; i < s.length(); i++){
char ch = s.charAt(i);
cnt.put(ch, cnt.getOrDefault(ch, 0) + 1);
}
List<Pair> list = new ArrayList<>();
for(Map.Entry<Character, Integer> entry : cnt.entrySet()){
char key = entry.getKey();
int value = entry.getValue();
list.add(new Pair(key, value));
}
Collections.sort(list, (p1, p2) -> Integer.compare(p2.value, p1.value));
StringBuilder sb = new StringBuilder();
for(Pair pair : list){
for(int i = 0; i < pair.value; i++){
sb.append(pair.key);
}
}
return sb.toString();
}
}
굳이 Pair를 쓰지 않아도 될 것 같다. 정렬기준은 value만 쓰기 때문이다. 그리고 필요한건 character이기 떄문에 Pair 사용하지 말자
2958. Length of Longest Subarray With at Most K Frequency
정수 배열 nums와 정수 k가 주어집니다. 요소 x의 빈도는 배열에서 해당 요소가 나타나는 횟수입니다. 각 요소의 빈도가 k보다 작거나 같으면 해당 배열을 good 배열이라고 합니다. nums의 가장 긴 good 부분 배열의 길이를 반환합니다. 부분 배열은 배열 내에서 비어 있지 않고 연속된 요소 시퀀스입니다.
제약사항
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= k <= nums.length
아이디어: substring -> k보다 작거나 같은 조건 -> 윈도우 슬라이딩
class Solution {
public int maxSubarrayLength(int[] nums, int k) {
int n = nums.length;
if (n == 1) return 1;
Map<Integer, Integer> cnt = new HashMap<>();
int l = 0;
int ans = 0;
for(int r = 0; r < n; r++){
cnt.put(nums[r], cnt.getOrDefault(nums[r], 0) + 1);
while(cnt.get(nums[r]) > k) {
cnt.put(nums[l], cnt.get(nums[l]) - 1);
l++;
}
ans = Math.max(ans, r - l + 1);
}
return ans;
}
}
보니까 nums.length를 캐싱하지 않아서 조금 느려진거였다. 풀이는 비슷했다.
정수 nums 배열이 주어졌을 때, 좋은 쌍의 개수를 반환합니다. (i, j) 쌍은 nums[i] == nums[j]이고 i < j일 때 좋은 쌍이라고 합니다.
제약사항
- 1 <= nums.length <= 100
- 1 <= nums[i] <= 100
아이디어
원소값을 키, 나타난 인덱스 리스트를 value로 갖는 해시맵을 만든다.
나중에 nums를 돌면서 해시맵을 채우면 value인 리스트는 오름차순 정렬이 알아서 된다.
그러면 리스트 가지고 조합!
class Solution {
private int countPair(List<Integer> list){
int n = list.size();
int cnt = 0;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
cnt++;
}
}
return cnt;
}
public int numIdenticalPairs(int[] nums) {
int n = nums.length;
Map<Integer, List<Integer>> cnt = new HashMap<>();
for(int i = 0; i < n; i++) {
if (!cnt.containsKey(nums[i])){
cnt.put(nums[i], new ArrayList<>());
}
cnt.get(nums[i]).add(i);
}
int ans = 0;
for(List<Integer> value : cnt.values()){
ans += countPair(value);
}
return ans;
}
}
930. Binary Subarrays With Sum
이진 배열 nums와 정수 goal이 주어졌을 때, 비어 있지 않은 부분 배열의 개수를 합을 구하는 goal과 함께 반환합니다. 부분 배열은 배열의 연속된 부분입니다.
제약조건
- 1 <= nums.length <= 4 * 10^4
- nums[i] is either 0 or 1
- 0 <= goal <= nums.length
아이디어
특정 조건을 만족하는 subarray -> prefix sum과 hashmap 조합으로 가보자
prefix 업데이트
특정 조건 만족하면 +1
prefixsum - k 개수만큼 +
해시맵 업데이트
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
Map<Integer, Integer> cnt = new HashMap<>();
int psum = 0;
int ans = 0;
int n = nums.length;
for(int i = 0; i < n; i++){
psum += nums[i];
if (psum == goal) ans += 1;
if (cnt.containsKey(psum - goal)){
ans += cnt.get(psum - goal);
}
cnt.put(psum, cnt.getOrDefault(psum, 0) + 1);
}
return ans;
}
}
양의 정수 nums로 구성된 배열이 주어지고 고유한 요소를 포함하는 부분 배열을 지우려고 합니다. 부분 배열을 지워서 얻는 점수는 요소의 합과 같습니다. 부분 배열 하나만 지워서 얻을 수 있는 최대 점수를 반환합니다. 배열 b가 a의 연속적인 부분 시퀀스를 형성할 때, 즉 (l, r)에 대해 a[l], a[l 1],..., a[r]과 같을 때, b가 a의 부분 배열이라고 합니다.
제약사항
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4
아이디어
슬라이딩 윈도우
class Solution {
public int maximumUniqueSubarray(int[] nums) {
Set<Integer> set = new HashSet<>();
int l = 0;
int max = 0;
int psum = 0;
int n = nums.length;
for(int r = 0; r < n; r++){
psum += nums[r];
while (!set.add(nums[r])){
set.remove(nums[l]);
psum -= nums[l++];
}
max = Math.max(max, psum);
}
return max;
}
}
두 문자열 s1과 s2가 주어졌을 때, s2가 s1의 순열을 포함하면 true를 반환하고, 그렇지 않으면 false를 반환합니다. 즉, s1의 순열 중 하나가 s2의 부분 문자열이면 true를 반환합니다.
제약사항
- 1 <= s1.length, s2.length <= 10^4
- s1 and s2는 영어 소문자로 이루어져있다.
아이디어
순열을 구해서 대입하는 방식은 n!이라서 시간복잡도 초과
순열인지 확인하는 방법 -> s1의 알파벳이 포함되었는가 (횟수도)
s1의 알파벳과 그 횟수를 정확히 가진 substring이 있는가
고정된 window 크기 = s1의 길이
class Solution {
public boolean checkInclusion(String s1, String s2) {
char[] arr = s2.toCharArray();
int n = arr.length;
int k = s1.length();
if (k > n) return false;
Map<Character, Integer> cnt = new HashMap<>();
for(char ch : s1.toCharArray()){
cnt.put(ch, cnt.getOrDefault(ch, 0) + 1);
}
Map<Character, Integer> temp = new HashMap<>();
for(int i = 0; i < k; i++){
temp.put(arr[i], temp.getOrDefault(arr[i], 0) + 1);
}
if (cnt.equals(temp)) return true;
for(int r = k; r < n; r++){
temp.put(arr[r], temp.getOrDefault(arr[r], 0) + 1);
int l = r - k;
temp.put(arr[l], temp.get(arr[l]) - 1);
if (temp.get(arr[l]) <= 0) temp.remove(arr[l]);
if (cnt.equals(temp)) {
return true;
}
}
return false;
}
}
가장 빠른 답변의 경우 해시맵이 아닌 int[26] 배열로 해결 -> 제약사항 s1, s2가 모두 영어 소문자로 이루어져있음을 이용
윈도우로 오른쪽거 빼주고 왼쪽거 더해준다음 모두 0인지 확인.
두 문자열 s와 t가 주어졌을 때, 두 문자열이 동형인지 판별하십시오. 두 문자열 s와 t는 s의 문자를 t로 바꿀 수 있을 때 동형입니다. 모든 문자는 문자 순서를 유지하면서 다른 문자로 바뀌어야 합니다. 두 문자가 같은 문자에 대응될 수는 없지만, 문자는 자기 자신에 대응될 수 있습니다.
제약사항
- 1 <= s.length <= 5 * 10^4
- t.length == s.length
- s and t는 아스키 문자로 이루어져있다.
아이디어
동형 => 문자 순서를 유지하면서 문자가 바뀐다.
122 == 122
s1을 숫자로 바꾼다. s2도 숫자로 바꿔서 둘이 같은지 비교
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Integer> mp1 = new HashMap<>();
StringBuilder sb1 = new StringBuilder();
int i = 0;
for(char ch : s.toCharArray()){
if (!mp1.containsKey(ch)) mp1.put(ch, i++);
sb1.append(mp1.get(ch) + " ");
}
Map<Character, Integer> mp2 = new HashMap<>();
StringBuilder sb2 = new StringBuilder();
int j = 0;
for(char ch : t.toCharArray()){
if (!mp2.containsKey(ch)) mp2.put(ch, j++);
sb2.append(mp2.get(ch) + " ");
}
return sb1.toString().equals(sb2.toString());
}
}
시간을 줄여보자
아이디어
s를 숫자로 매칭하고 t를 볼 때 s와 같은 숫자를 매칭하는지 확인
예를 들어 s = "egg", t = "add"일 때
e: 0 g: 1일테니까 a: 0이고 d: 1일테니까 지금 보고 있는 문자의 value가 s의 Value와 같은지
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Integer> mp1 = new HashMap<>();
Map<Character, Integer> mp2 = new HashMap<>();
int num = 0;
for(int i = 0; i < s.length(); i++){
char s_ch = s.charAt(i);
char t_ch = t.charAt(i);
if (!mp1.containsKey(s_ch)) mp1.put(s_ch, num);
if (!mp2.containsKey(t_ch)) mp2.put(t_ch, num);
if (mp1.get(s_ch) != mp2.get(t_ch)) return false;
num++;
}
return true;
}
}
패턴과 문자열 s가 주어졌을 때, s가 같은 패턴을 따르는지 확인하세요. 여기서 follow는 pattern의 글자와 s의 비어 있지 않은 단어 사이에 단사 관계가 존재하는 완전 일치를 의미합니다. 구체적으로는
- pattern의 각 글자는 s의 고유한 단어 하나에 정확히 매핑됩니다.
- s의 고유한 단어는 pattern의 글자 하나에 정확히 매핑됩니다.
- 두 글자가 같은 단어에 매핑되지 않고, 두 단어가 같은 글자에 매핑되지 않습니다.
제약사항
- 1 <= pattern.length <= 300
- pattern은 오직 영어 소문자로 이루어져있다.
- 1 <= s.length <= 3000
- s는 영어 소문자랑 공백으로만 이루어져있다.
- s는 처음과 맨 끝에 공백을 포함하지 않는다.
- s의 모든 단어들은 한 칸 공백으로 분리되어있다.
아이디어
s를 공백으로 나누고 포인터로 같이 이동하면서 확인한다.
class Solution {
public boolean wordPattern(String pattern, String s) {
Map<Character, String> map = new HashMap<>();
Set<String> already = new HashSet<>();
String[] tokens = s.split(" ");
int n1 = pattern.length();
int n2 = tokens.length;
if (n1 != n2) return false;
for(int i = 0; i < n1; i++){
char ch = pattern.charAt(i);
String token = tokens[i];
if (!map.containsKey(ch)){
if (!already.add(token)) return false;
map.put(ch, token);
} else {
if (!map.get(ch).equals(token)) return false;
}
}
return true;
}
}
두 문자열 order와 s가 주어집니다. order의 모든 문자는 고유하며 이전에 사용자 지정 순서로 정렬되었습니다.
s의 문자를 order가 정렬된 순서와 일치하도록 순열합니다. 더 구체적으로, 문자 x가 order에서 문자 y보다 앞에 오면 순열된 문자열에서 x는 y보다 앞에 와야 합니다. 이 속성을 만족하는 s의 모든 순열을 반환합니다.
제약사항
- 1 <= order.length <= 26
- 1 <= s.length <= 200
- order and s는 영어 소문자로 이루어져있다.
- order의 모든 문자는 unique하다.
아이디어
문자열 재배치
문자열 분해 -> 다시 이어붙이기(기준:order)
1. s를 hashmap으로 어떤 문자가 몇 개 있는지 분해
2. order를 돌면서 hashmap에 있으면 그 갯수만큼 이어붙이기 그리고 map에서 삭제하기
3. order를 다 돌면 hashmap에 나머지 문자가 있을테니 순서대로 이어붙이기
class Solution {
public String customSortString(String order, String s) {
Map<Character, Integer> map = new HashMap<>();
for(char ch : s.toCharArray()){
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
StringBuilder sb = new StringBuilder();
for(char ch : order.toCharArray()){
if (map.containsKey(ch)){
for(int i = 0; i < map.get(ch); i++){
sb.append(ch);
}
map.remove(ch);
}
}
for(char key : map.keySet()){
for(int i = 0; i < map.get(key); i++){
sb.append(key);
}
}
return sb.toString();
}
}
Another Questions
class Solution {
public String customSortString(String order, String s) {
Map<Character, Integer> orderMap = new HashMap<>();
for (int i = 0; i < order.length(); i++) {
orderMap.put(order.charAt(i), i); // (order 문자, 순서)
}
List<Character> S = new ArrayList<>();
for (char c : s.toCharArray()) {
S.add(c);
}
return S.stream()
.sorted((o1, o2) -> { // Null의 의미는 order 순서에 구애받지 않는 친구
Integer index1 = orderMap.get(o1);
Integer index2 = orderMap.get(o2);
if (index1 == null && index2 == null) {
return 0; // no order (don't care)
} else if (index1 == null) {
return 1; // o1 to the end
} else if (index2 == null) {
return -1; // o2 to the end
} else {
return index1.compareTo(index2);
}
})
.map(Object::toString)
.collect(Collectors.joining());
}
}1657. Determine if Two Strings Are Close
다음 연산을 사용하여 한 문자열에서 다른 문자열을 찾을 수 있으면 두 문자열이 가까운 것으로 간주됩니다.
- 연산 1: 기존 문자 두 개를 바꿉니다. 예: abcde -> aecdb
- 연산 2: 기존 문자 하나를 다른 문자로 변환하고, 나머지 문자에도 동일한 연산을 수행합니다. 예: aacabb -> bbcbaa (모든 a는 b로, 모든 b는 a로 변환)
각 문자열에 필요한 만큼 연산을 사용할 수 있습니다. 두 문자열 word1과 word2가 주어졌을 때, word1과 word2가 가까우면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
제약사항
- 1 <= word1.length, word2.length <= 10^5
- word1 and word2는 영어 소문자로 이루어져있다.
아이디어
연산 1은 위치 바꾸기
연산 2는 문자 개수 바꾸기
일단 word1과 word2의 길이가 같아야한다.
사용한 문자 종류와 개수 분포가 같아야한다.
class Solution {
public boolean closeStrings(String word1, String word2) {
int n = word1.length();
int m = word2.length();
if (n != m) return false;
Map<Character, Integer> mp1 = new HashMap<>();
Map<Character, Integer> mp2 = new HashMap<>();
for(char ch : word1.toCharArray()){
mp1.put(ch, mp1.getOrDefault(ch, 0) + 1);
}
for(char ch : word2.toCharArray()){
mp2.put(ch, mp2.getOrDefault(ch, 0) + 1);
}
if (!mp1.keySet().equals(mp2.keySet())) return false;
List<Integer> list1 = new ArrayList<>(mp1.values());
List<Integer> list2 = new ArrayList<>(mp2.values());
Collections.sort(list1);
Collections.sort(list2);
return list1.equals(list2);
}
}
해시 문제를 보면서 느낀 점
영어 소문자로 이루어진 것들을 다룰 때는 hashMap보다 26개의 배열을 쓰는 것이 훨씬 빠를 수 있다는 점
'코딩테스트' 카테고리의 다른 글
| Binary Trees (1) | 2025.05.21 |
|---|---|
| 힙 (Heap) (1) | 2025.05.20 |
| 해시 (Hash) (1) | 2025.04.15 |
| Two pointer (0) | 2025.04.05 |
| Prefix sum (0) | 2025.04.02 |