프로그래머스 코딩테스트 고득점 Kit - 해시(폰켓몬, 완주하지 못한 선수, 전화번호 목록, 의상, 베스트 앨범)

1번 문제: 폰켓몬

https://school.programmers.co.kr/learn/courses/30/lessons/1845

프로그래머스

풀이

N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, 가장 많은 종류의 폰켓몬 N/2마리를 선택하는 방법을 찾아 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 메서드를 완성해야 한다.
폰켓몬은 종류에 따라 번호를 붙여 구분하며, 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타낸다.

접근

폰켓몬 종류 번호를 구하는 것이 아니라 번호의 개수를 구하는 문제이기 때문에 Map을 사용하지 않고 Set을 사용했다. 입력받은 nums 배열에 있는 폰켓몬 종류 번호를 모두 Set에 넣으면 선택할 수 있는 폰켓몬 종류의 개수를 구할 수 있고, 여기서 N/2마리보다 많이 선택할 수 없기 때문에 둘 중 더 작은 수를 반환하도록 코드를 작성했다.

코드

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int n = nums.length / 2;
        return Math.min(set.size(), n);
    }
}

---

2번 문제: 완주하지 못한 선수

https://school.programmers.co.kr/learn/courses/30/lessons/42576

프로그래머스

풀이

수많은 마라톤 선수들 중 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주했을 때 주어진 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion에서 완주하지 못한 선수의 이름을 return 하도록 solution 메서드를 작성해야 한다.

접근

문제의 입출력 예시 중 다음과 같은 예시가 있다.

participant	completion	return
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했기 때문에 return 값으로 "mislav"가 나와야 한다. 즉, 중복되는 이름이 있을 수 있기 때문에 Set에 모든 참여한 선수들을 넣고, 완주한 선수들을 빼는 방식으로 문제를 풀 수 없다. 따라서 Set이 아닌 Map을 사용했다.

key 값으로 참여한 선수들의 이름을, value 값으로 해당 이름을 가진 선수들의 수를 갖도록 Map<String, Integer>와 같이 선언하였다.

코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> map = new HashMap<>();
        for (String p : participant) {
            map.put(p, map.getOrDefault(p, 0) + 1);
        }
        for (String c : completion) {
            map.put(c, map.get(c) - 1);
        }
        for (String name : map.keySet()) {
            if (map.get(name) != 0) {
                return name;
            }
        }
        return "";
    }
}

첫 번째 for문에서 map에 참여한 선수들의 이름별 수를 저장한다.

두 번째 for문에서 완주한 선수들에 대해 map에 있는 선수들의 이름별 수에서 1을 뺀다. 이때 Map은 중복되는 key 값을 갖지 않기 때문에 기존의 key 값을 삭제할 필요가 없으므로 바로 put 메서드를 사용한다.

마지막 for문에서 map.get(name)이 0보다 크다면 아직 완주하지 못한 선수라는 뜻이므로 해당 선수의 이름을 반환한다.

---

3번 문제: 전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

풀이

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두어이다.

• 구조대 : 119
• 박준영 : 97674223
• 지영석 : 1195524421

전화번호부에 적힌 전화번호를 담은 배열 phone_book에서 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를, 그렇지 않으면 true를 return 하도록 solution 메서드를 완성해야 한다.

접근 1

입력받은 phone_book 배열은 String[] 타입이기 때문에 해당 배열을 Arrays.sort 메서드로 정렬하면 비슷한 번호끼리 붙을 것이다. 위의 예시 배열(구조대, 박준영, 지영석)을 정렬하면 ["119", " 1195524421", " 97674223"]가 되는 것처럼 더 짧은, 즉 뒤의 번호의 접두어가 될 수 있는 번호가 앞으로 간다. 접두어가 될 수 있는 경우의 수를 구하는 문제가 아니기 때문에 i번째 번호와 i+1번째 번호만 비교하여 문제를 해결할 수 있다.

코드 1

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        boolean answer = true;
        for (int i = 0; i < phone_book.length - 1; i++) {
            int len = phone_book[i].length();
            if (phone_book[i + 1].length() > len) {
                if (phone_book[i].equals(phone_book[i + 1].substring(0, len))) {
                    return !answer;
                }
            }
        }
        return answer;
    }
}

접근 2

위의 코드는 HastSet, 혹은 HashMap과 같은 해시를 전혀 사용하지 않았다. 그래서 이를 사용하는 접근을 생각해보면 다음과 같다.

모든 번호를 Set에 넣고, phone_book 배열에 있는 모든 번호에 대해 앞에서부터 잘라가며 접두어를 만들고 Set에 있는지 여부를 확인하여 해결할 수 있다.

코드 2

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Set<String> set = new HashSet<>();
        for (String phone : phone_book) {
            set.add(phone);
        }
        boolean answer = true;
        for (int i = 0; i < phone_book.length; i++) {
            for (int j = 1; j < phone_book[i].length(); j++) {
                if (set.contains(phone_book[i].substring(0, j))) {
                    return !answer;
                }
            }
        }
        return answer;
    }
}

boolean answer = true; 아래의 이중 for문에서 i는 phone_book 배열에 들어있는 전화번호를 탐색하는 인덱스를 의미하고, j는 전화번호의 앞부터 자르며 접두어를 만들 길이를 의미한다.

해당 문제에 대한 내 생각

테스트 케이스에 따라 다르겠지만, 대부분 아래 2번 코드의 결과가 더 좋다.

1번 코드의 시간 복잡도는 for문이 1개 들어갔으므로 정렬 로직을 제외하면 전화번호의 개수를 n개라고 했을 때 O(n), 2번 코드의 시간 복잡도는 전화번호들의 평균 길이를 m이라고 했을 때 O(nm)이다.

그런데 Arrays.sort 메서드가 O(n^2)이므로 1번 코드의 시간 복잡도는 O(n^2)가 되고, 여기서 n과 m 중 어떤 수가 더 크냐에 따라 성능이 달라지는 것 같다. 그러므로 둘 중 아무 코드나 사용해도 크게 문제가 되지 않을 것 같지만 phone_book의 길이는 1 이상 1,000,000 이하이고, 각 전화번호의 길이는 1 이상 20 이하이기 때문에 아래 코드를 사용하는 것이 더 효율적일 것 같다고 생각한다.

---

4번 문제: 의상

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

예전에 이 문제를 처음 풀었을 때는 문제 이름이 "위장" 이었던 것 같은데 그새 바뀌었나 보다.

 

풀이

의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해야 한다. 하루에 최소 한 개 이상의 의상을 입을 때 각 종류별로 최대 1가지 의상만 착용할 수 있으며, 착용한 의상의 일부가 겹치더라도 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산한다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

예를 들어 의상이 위와 같고, 오늘 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야한다.

접근

문제의 입출력 예시 중 다음과 같은 예시가 있다.

clothes	return
[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]	5

여기서 같은 이름을 가진 의상은 존재하지 않는다고 했으므로, 겹치는 "headgear"가 있는 clothes[?][1]이 의상의 종류이다.

서로 다른 옷의 조합의 경우의 수가 아닌 개수를 구하는 문제이므로 key 값으로 의상의 종류를, value 값으로 해당 종류의 의상들의 수를 갖도록 Map<String, Integer>와 같이 선언하였다.

모든 옷을 안 입는 경우를 포함한 모든 조합 개수는 (종류별 의상 개수 + 1)을 모두 곱하면 된다. 여기서 1은 해당 종류의 옷을 입지 않는 경우의 수이다. 이 값에서 모든 옷을 안 입는 경우의 수인 1을 빼면 된다.

코드

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        Map<String, Integer> map = new HashMap<>();
        for (String[] cloth : clothes) {
            map.put(cloth[1], map.getOrDefault(cloth[1], 0) + 1);
        }
        int answer = 1;
        for (int e : map.values()) {
            answer *= e + 1;
        }
        return answer - 1;
    }
}

다른 사람의 풀이

import java.util.*;
import static java.util.stream.Collectors.*;

class Solution {
    public int solution(String[][] clothes) {
        return Arrays.stream(clothes)
                .collect(groupingBy(p -> p[1], mapping(p -> p[0], counting())))
                .values()
                .stream()
                .collect(reducing(1L, (x, y) -> x * (y + 1))).intValue() - 1;
    }
}

내 풀이와 같지만 코드를 모두 스트림을 이용하여 풀었다. 아직 이 부분은 잘 모르는데 빠른 시일 내로 공부해보고 싶다는 생각이 들었다.

---

5번 문제: 베스트 앨범

https://school.programmers.co.kr/learn/courses/30/lessons/42579

프로그래머스

풀이

스트리밍 사이트에서 장르별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 할 때 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같다.

• 속한 노래가 많이 재생된 장르를 먼저 수록한다.
• 장르 내에서 많이 재생된 노래를 먼저 수록 한다.
• 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록 한다.
• 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성해야 한다.

genres[i]는 고유번호가 i인 노래의 장르이고, plays[i]는 고유번호가 i인 노래가 재생된 횟수이다. 결국 위를 정리해보면 각 장르의 재생 횟수를 기준으로 순서를 찾고, 이 장르별 노래에서 가장 많이 재생된 노래 두 개를 찾아 베스트 앨범에 순서대로 넣어서 완성해야 한다.

접근

먼저 가장 많이 재생된 장르를 찾아야 한다. 이를 위해 key 값으로 장르 이름를, value 값으로 해당 장르의 재생 횟수를 갖도록 Map<String, Integer>와 같이 선언하였다. 해당 Map을 채운 후에 장르 이름과 재생 횟수를 저장할 Genre 클래스를 만들고, List<Genre> genreList에 넣고 내림차순으로 정렬한다.

그리고 각 장르별 노래의 인덱스와 재생 횟수를 저장할 Music 클래스를 만들고, List<Music> musicList에 넣고 내림차순으로 정렬한 뒤 최대 2개까지 앨범에 순서대로 넣는다.

코드

import java.util.*;

class Genre implements Comparable<Genre> {

    private String name;
    private int play;

    public Genre(String name, int play) {
        this.name = name;
        this.play = play;
    }

    public String getName() {
        return name;
    }

    @Override
    public int compareTo(Genre o) {
        return o.play - this.play;
    }

}

class Music implements Comparable<Music> {

    private int idx, play;

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

    public int getIdx() {
        return idx;
    }

    @Override
    public int compareTo(Music o) {
        return o.play - this.play;
    }

}

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < genres.length; i++) {
            map.put(genres[i], map.getOrDefault(genres[i], 0) + plays[i]);
        }
        List<Genre> genreList = new ArrayList<>();
        for (String genre : map.keySet()) {
            genreList.add(new Genre(genre, map.get(genre)));
        }
        Collections.sort(genreList);
        List<Music> album = new ArrayList<>();
        for (Genre genre : genreList) {
            List<Music> musicList = new ArrayList<>();
            for (int i = 0; i < genres.length; i++) {
                if (genre.getName().equals(genres[i])) {
                    musicList.add(new Music(i, plays[i]));
                }
            }
            Collections.sort(musicList);
            album.add(musicList.get(0));
            if (musicList.size() > 1) {
                album.add(musicList.get(1));
            }
        }
        int[] answer = new int[album.size()];
        for (int i = 0; i < album.size(); i++) {
            answer[i] = album.get(i).getIdx();
        }
        return answer;
    }
}

Genre 클래스와 Music 클래스는 모두 내림차순으로 정렬해야 하기 때문에 Comparable<T>를 구현하고, compareTo(T o)를 재생 횟수를 의미하는 play에 맞도록 오버라이딩했다.

---

결론

싸피 떨어지고 나서 모든 학교 일정을 마치고 쭉 쉬다가 카카오테크 부트캠프 2기에 지원하고 나서 굉장히 오랜만에(?) 코딩 테스트 준비를 다시 시작하게 됐다. 이번 프로그래머스의 해시 파트는 설명이 그렇게 길지 않을 것 같아서 하나의 글에 모든 문제를 다 넣었는데, 생각보다 시간이 오래 걸리고 힘들었다. 아마 다음 글부터는 한 문제당 하나의 글을 작성하지 않을까 싶다.