프로그래머스 알고리즘 문제 풀이 Hash

zio도미닉·2022년 1월 4일
0

1. 완주하지 못한 선수

알게 된 점

// 1. getOrDefault 
hashMap.put(key,hashMap.getOrDefault(key,0)+1)
// 2. JavaMap 출력
// 2-1. Iterator 이용
Iterator<String> iterators=hashMap.keySet().iterator();
while (iterators.hasNext()) {
	String key=iterators.next();
    String value=hashMap.get(key);
}
// 2-2. entrySet()을 이용
for (Map.Entry<String,String> entry:hashMap.entrySet()) {
	String key=entry.getKey();
    String value=entry.getValue();
}
// 2-3. for Each
for (String strKey:hashMap.keySet()) {
	String value=hashMap.get(strKey);
}
  • 첫번째 방법
    // 문제점 있음
    public String solution1(String[] participant, String[] completion) {
        String answer = "";

        HashMap<String,Integer>parti=new HashMap<String, Integer>();
        HashMap<String,Integer>comple=new HashMap<String, Integer>();

        // Default
        for (String par:participant) {
            parti.put(par,parti.getOrDefault(par,0)+1);
        }

        for (String com:completion) {
            comple.put(com,comple.getOrDefault(com,0)+1);
        }

        // System.out.println(parti.toString());
        // System.out.println(comple.toString());

        // particiapnt>completion
        
        Iterator<String>iterators=parti.keySet().iterator();
        while (iterators.hasNext()) {
            String key=iterators.next();

            // 완주자가 있음
            if (comple.containsKey(key)) {
                // 빼줌
                parti.put(key,parti.get(key)-1);

            }
            else {
                // 완주자 목록에 없음 comple을 제거
                return key;
            }
        }

        // System.out.println(parti.toString());
        // value가 1이상인 것은 아직 동명의 미완주자가 있음 -> return
        for (String strKey:parti.keySet()) {
            int value=parti.get(strKey);
            if (value!=0) {
                return strKey;
            }
        }

        return answer;
    }

문제점

  • 이렇게 하면 문제 -> 이유는 parti는 map으로 이루어져있기 때문에 중복 map이 못들어감
  • 반례) participant : a,b,c,d,a,b / completion : a,b,a,b,d
  • 따라서 전체 Map을 돌때는 유의점을 가진다.
  • Map을 하나만 사용하고 빼주면서 사용하자
  • 해결코드
    public String solution2(String[] participant, String[] completion) {
        String answer = "";

        HashMap<String,Integer>parti=new HashMap<String, Integer>();

        // Default
        for (String par:participant) {
            parti.put(par,parti.getOrDefault(par,0)+1);
        }

        for (String comple:completion) {
            parti.put(comple,parti.get(comple)-1);
        }


        // System.out.println(parti.toString());
        // value가 1이상인 것은 아직 동명의 미완주자가 있음 -> return
        for (String strKey:parti.keySet()) {
            int value=parti.get(strKey);
            if (value!=0) {
                return strKey;
            }
        }

        return answer;
    }

2. 전화번호 목록

알게 된 점

  • 배열 정렬
    Arrays.sort(배열)
  • 배열 출력
    Arrays.toString(배열)
  • startsWith( ) : String 특정 문자 또는 문자열로 시작하는지 체크
String text="abcd";
text.startsWith("ab"); // true
  • endsWith( ) : String 특정 문자 또는 문자열로 종료하는지 체크
String text="abcd";
text.endsWith("cd"); // true

해결방법

  • String으로 정렬을 한다 -> String 정렬을 하면 숫자의 크기 순이 아니라 앞자리의 수로 정렬된다.
    ex) 19, 1195524421, 97574223 ...
  • 정렬을 하고 바로 앞에꺼와 비교를 하면 된다. (2중 for문 돌 필요 없이) 바로 앞에께 포함되면 false를 return 한다.
  • 포함이 안되면 비교값(str)을 기존 인덱스의 값으로 변경한다.
    ex) 119, 11955524421
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        // 배열 정렬
        Arrays.sort(phone_book);
        
        // 배열 출력 
        // System.out.println(Arrays.toString(phone_book));
        
        String str=phone_book[0];
        for (int i=1;i<phone_book.length;i++) {
            boolean val=phone_book[i].startsWith(str);
            // System.out.println(val);
            
            if (val) {
                return false;
            }
            else {
                str=phone_book[i];
            }
            
        }
        
        return answer;
    }

3. 위장

해결방법

(n+1) * (m+1) -1으로 해결
-1은 공집합을 의미

    public int solution(String[][] clothes) {
        
        
        HashMap<String,Integer>hashmap=new HashMap<>();
        
        for (int i=0;i<clothes.length;i++) {
            
            String key=clothes[i][1];
            // String value=clothes[i][0];
            hashmap.put(key,hashmap.getOrDefault(key,0)+1);
            
        }
        
        System.out.println(hashmap.toString());
        int answer = 1;

        for (String key:hashmap.keySet()) {
            answer*=hashmap.get(key)+1;
        }
        
        answer-=1;
        return answer;
    }

4. 베스트앨범

알게 된 점
1. Map의 Value기준 내림차순 정렬 (Value가 String일때 compareTo를 사용)

List<String>keySetList=new ArrayList<>(genreMap.keySet());
Collections.sort(keySetList,(o1,o2)->genreMap.get(o2).compareTo(genreMap.get(o1)));
  1. Value가 int일때 내림차순 정렬
 Collections.sort(list,(o1,o2)->o2.play-o1.play);
  1. 다중 정렬일때는 class를 만들어서 arraylist안에 class를 넣어서 사용한다.
    static class Music{
        String genre;
        int play;
        int idx;

        public Music(String genre, int play, int idx) {
            this.genre = genre;
            this.play = play;
            this.idx = idx;
        }
    }


    public int[] solution(String[] genres, int[] plays) {

        Map<String, Integer> genreMap=new HashMap<>();
        // 1. 장르 선정 및 내림차순 정렬
        for (int i=0;i<genres.length;i++) {
            String key=genres[i];
            int value=plays[i];

            genreMap.put(key,genreMap.getOrDefault(key,0)+value);

            // ArraList
            ArrayList<Integer>arraylist=new ArrayList<>();
            arraylist.add(i);
            arraylist.add(value);

        }
        // System.out.println(genreMap.toString());
        // value 기준으로 내림차순 정렬
        List<String>keySetList=new ArrayList<>(genreMap.keySet());
        Collections.sort(keySetList,(o1,o2)->genreMap.get(o2).compareTo(genreMap.get(o1)));

        // 2. 장르 내 노래 선정
        ArrayList<Music> result=new ArrayList<>();
        for (String gern:keySetList) {
            ArrayList<Music>list= new ArrayList<>();

            for (int i=0;i< genres.length;i++) {
                if (genres[i].equals(gern)) {
                    list.add(new Music(gern,plays[i],i));
                }
            }

            Collections.sort(list,(o1,o2)->o2.play-o1.play);
            result.add(list.get(0));
            if (list.size()!=1) {
                result.add(list.get(1));
            }
        }

        int answer[]=new int[result.size()];
        for (int i=0;i< result.size();i++) {
            answer[i]=result.get(i).idx;
        }
        return answer;

    }
profile
BackEnd Developer

0개의 댓글