자바 문법 및 알고리즘 (hash)

자바 문법 (hash)

• hashMap -> getOrDefault() : 찾는 키가 존재하면 해당 키의 값을 반환하고, 없으면 기본값을 반환함
  ex) hashMap.put(key,hashMap.getOrDefault(key,0)+1);
• String -> String[] 배열로 변환
  ex) String[]strArr=str.split("");
• HashMap에 Value를 기준으로 내림차순
  1. List안에 Map을 넣는다.
  2. Map.Entry는 -> 본래 맵에 key, value값 전체를 가진다. 이 부분을 hashMap.entrySet()을 이용해서 전체를 넣는다.
     Map.Entry를 이용하는 이유는 entrySet()을 받기 위해서 사용
     (hashMap.entrySet()에는 key, value들이 들어가 있다.)
  3. Collections sort를 이용해서 정렬한다.

        List<Map.Entry<String,Integer>> entryList=new ArrayList<Map.Entry<String,Integer>>(hashMap.entrySet());
        Collections.sort(entryList, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue()); // 내림차순
                return o1.getValue().compareTo(o2.getValue()); //오름차순
		}
        });
        // lambda를 이용한 정렬 (람다를 이용한것이 훨씬 편리)
        Collections.sort(entryList,(o1,o2)->(o2.getValue().compareTo(o1.getValue())));

• 람다를 이용한 정렬 표현법을 꼭 익히자

Collections.sort(entryList,(o1,o2)->(o2.getValue().compareTo(o1.getValue())));

• 정렬된 arraylist에 첫번째 인자인 key를 뽑는 방법
  Map.Entry<String, Integer> stringIntegerEntry = entryList.get(0);

문제 1

해결방법

방법 1. Collection.sort를 이용한 정렬
방법 2. 가장 작은 값을 설정해주고 비교 하는 방법

코드 1.

    public String solution(int n,String str) {
        String answer="";

        // HashMap 이용
        HashMap<String,Integer> hashMap=new HashMap<>();

        // str -> string 배열로
        String[]strArr=str.split("");

        for (String key:strArr) {
            hashMap.put(key,hashMap.getOrDefault(key,0)+1);
        }
        // 가장 큰것 찾음
        // hashMap에 value를 기준으로 내림차순
        // List안에 Map을 넣는다.
        // Map.Entry는 -> 본래 맵에 key, value값  전체를 가진다. 이 부분을 hashMap.entrySet()을 이용해서 전체를 넣는다.
        List<Map.Entry<String,Integer>> entryList=new ArrayList<Map.Entry<String,Integer>>(hashMap.entrySet());
        Collections.sort(entryList, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });

        // 첫번째 인덱스를 꺼낸다?
        Map.Entry<String, Integer> stringIntegerEntry = entryList.get(0);
        answer=stringIntegerEntry.getKey();

        return answer;

    }

코드 2.

    public String solution2(int n,String str) {
        String answer="";
        // HashMap 이용
        HashMap<String,Integer> hashMap=new HashMap<>();

        // str -> string 배열로
        String[]strArr=str.split("");

        for (String key:strArr) {
            hashMap.put(key,hashMap.getOrDefault(key,0)+1);
        }
        int maxValue=Integer.MIN_VALUE;
        for (String s:strArr) {
            if (hashMap.get(s)>maxValue) {
                maxValue=hashMap.get(s);
                answer=s;
            }
        }
      
        return answer;
    }

문제 2

이슈

슬라이싱 윈도우 + Hash 사용

• 인덱스 접근을 위해 arrayList 사용
• 슬라이싱 윈도우 안에 for문으로 size 검사시 시간초과 발생했었음
• 해결방법으로는 arrayList사용 및 hashMap에 value 크기를 확인하여 제거

해결방법

• 슬라이싱 윈도우 -> 시간 초과 방지

1. 초기 크기값을 설정한다. (인덱스 접근을 위해 arrayList를 사용)
2. for문에는 다음 값부터 끝까지 돌면서 첫번째 인덱스 값은 빼주고 다음 인덱스 값은 더한다.

코드

public void solution(int n,int m,int []arr) {

        ArrayList<Integer>arrayList=new ArrayList<>();

        // 초기값
        for (int i=0;i<m;i++) {
            arrayList.add(arr[i]);
        }
        // 첫번째 값 확인
        HashMap<Integer,Integer> hashMap=new HashMap<>();
        for (int i=0;i< arrayList.size();i++) {
            hashMap.put(arrayList.get(i),hashMap.getOrDefault(arrayList.get(i),0)+1);
        }

        System.out.print(hashMap.keySet().size()+" ");

        // 슬라이싱 윈도우 for문
        // arraylist를 사용하는 이유는 인덱스 접근이 자유롭기 때문에
        for (int i=m;i<n;i++) {

            // 처음 값 빼주기
            int temp=arrayList.remove(0);
            int value=hashMap.get(temp)-1;
            hashMap.put(temp,value);

            if (value==0) {
                hashMap.remove(temp);
            }

            // 이 부분으로 인해 시간초과 발생 -> 이슈
//            hashMap=new HashMap<>();
//            for (int j=0;j< arrayList.size();j++) {
//                hashMap.put(arrayList.get(j),hashMap.getOrDefault(arrayList.get(j),0)+1);
//            }

            // 다음 값 더해주기
            int key=arr[i];
            hashMap.put(key,hashMap.getOrDefault(key,0)+1);
            arrayList.add(key);
            System.out.print(hashMap.keySet().size()+" ");

        }

    }