💪🏻 programmers Lv1(24.11.19 -3문제)

71) 대충 만든 자판

HashMap을 사용하여 key, value를 저장하기

import java.util.*;
class Solution {
    public int[] solution(String[] keymap, String[] targets) {
        int[] answer = new int[targets.length];
        Map<Character, Integer> map = new HashMap<>();
        
        for(String s : keymap)
        {
            for(int i=0;i<s.length();i++)
            {
                char key = s.charAt(i);
                int value = map.getOrDefault(key, i+1);
                map.put(key, Math.min(value, i+1));
            }
        }
        
        for(int i=0;i<targets.length;i++)
        {
            for(int j=0;j<targets[i].length();j++)
            {
                char key = targets[i].charAt(j);
                
                if(map.containsKey(key))
                {
                    answer[i] += map.get(key);
                }
                else{
                    answer[i] = -1;
                    break;
                }
            }
        }
        return answer;
    }
}

HashMap을 사용하여 key, value를 저장하는 자료구조, 특정 키에 대한 값을 빠르게 찾거나 업데이트할 수 있음.

• put(key, value): 지정된 키에 대한 값을 저장

• get(key): 지정된 키에 대한 값을 반환. 키가 없다면 null을 반환.
• containsKey(key): 특정 키가 HashMap에 포함되어 있는지 여부를 확인함.
• getOrDefault(key, defaultValue): 특정 키가 있으면 해당 값을 반환하고, 없으면 지정된 기본값을 반환함.

Map<Character, Integer> map = new HashMap<>();
map.put('A', 1); // 'A'라는 키에 1을 저장
map.put('B', 2); // 'B'라는 키에 2를 저장

// 'A'가 있는 경우 그 값을 반환, 없는 경우 기본값 5 반환
int valueA = map.getOrDefault('A', 5); // 결과: 1
int valueC = map.getOrDefault('C', 5); // 결과: 5 ('C'가 없기 때문)

72) 완주하지 못한 선수

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Map<String, Integer> map = new HashMap<>();
        
        for(String s : participant)
        {
            map.put(s, map.getOrDefault(s,0)+1);
        }
        
        for(String s : completion)
        {
            map.put(s, map.get(s)-1);
        }
        
        for(String s : map.keySet())
        {
            if(map.get(s) > 0)
            {
                answer = s;
                break;
            }
        }
        
        return answer;
    }
}

map.getOrDefault(s, 0) + 1 : 해당 이름 s가 이미 map에 저장되어 있으면 그 값(등장 횟수)을 가져오고, 저장되어 있지 않으면 기본값으로 0을 사용함.

즉, 다 0으로 저장된 뒤, 이름에 +1 을 함. 즉, 이름이 2개 나올경우 2로 저장.

map.put(s, map.get(s)-1) : 완주자의 이름을 map에서 찾아서 그 값을 1 감소

map.keySet() : 모든 키를 순회

73) 체육법

그리디 알고리즘은 현재 상황에서 가장 최적인 선택을 반복해서 최종적인 결과를 도출하는 방식을 사용.

1. 빌릴 수 있는 체육복을 바로 빌려주는 최적의 선택을 반복하여 전체 학생 중 가능한 많은 학생이 체육복을 가지도록 하는 것이 목표.

2. 그리디 방식으로 각 학생이 체육복을 최대한 많이 빌려줄 수 있는지 확인. 한 학생이 자신의 체육복을 빌려주면, 그 체육복은 더 이상 다른 학생에게 빌려줄 수 없으므로 바로 리스트에서 제거하여 더 나은 최적의 결과를 유지.

3. 체육복이 필요한 학생을 순서대로 확인하면서 빌릴 수 있는지 확인하는 과정을 통해 최적의 결과를 얻음.

핵심 포인트

• 여분이 있는 학생이 빌려줄 수 있는 경우 가까운 번호부터 빌려주는 것이 가장 최적의 선택.

• 각 잃어버린 학생을 확인하며 빌릴 수 있는 가장 가까운 학생이 있다면 빌려주고, 그렇지 않으면 체육복이 없는 상태로 남기 때문에 그리디 알고리즘의 특성.

import java.util.*;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n;
        
        Set<Integer> lostSet = new HashSet<>();
        Set<Integer> reserveSet = new HashSet<>();
        
        for(int l : lost)
        {
            lostSet.add(l);
        }
        for(int r : reserve)
        {
            if(lostSet.contains(r))
            {
                lostSet.remove(r);
            }
            else{
                reserveSet.add(r);
            }
        }
        
        for(int l : lostSet)
        {
            if(reserveSet.contains(l-1))
            {
                reserveSet.remove(l-1);
            }
            else if(reserveSet.contains(l+1))
            {
                reserveSet.remove(l+1);
            }
            else{
                answer--; 
            }
        }
        
        return answer;
    }
}