[프로그래머스][월간 코드 챌린지 시즌1] 스타수열 문제 해결 (Java) Level 3

개발/알고리즘

[프로그래머스][월간 코드 챌린지 시즌1] 스타수열 문제 해결 (Java) Level 3

nova_dev 2021. 1. 10. 16:07

알고리즘
[프로그래머스][월간 코드 챌린지 시즌1] 스타수열 문제 해결 (Java) Level 3

https://programmers.co.kr/learn/courses/30/lessons/70130

코딩테스트 연습 - 스타 수열

programmers.co.kr

문제 설명

스타 수열의 최대 길이 갯수를 구하는 문제입니다.

수열이 {x[0], x[1]}, {x[2], x[3]}, ..., {x[2n-2], x[2n-1]} 라고 가정하자.
이 때 아래 조건을 만족한 수열을 스타 수열이라고 부른다.

스타 수열의 조건1. x의 길이가 2이상의 짝수이다.
스타 수열의 조건2. {x[0], x[1]}, {x[2], x[3]}, ..., {x[2n-2], x[2n-1]}의 교집합의 원소 갯수가 1 이상이다.
스타 수열의 조건3. x[0] != x[1], x[2] != x[3], ..., x[2n-2] != x[2n-1]이다.

문제 해결 방법1

map에 교집합으로 사용할 수 있을만한 key값을 찾기 위해 각 숫자가 호출된 횟수를 저장합니다.
keyset을 순회하면서 스타 수열의 최댓값을 찾습니다.
- a[]를 돌면서 앞과 뒤에 교집합인 값이 있는지, 숫자가 같지는 않은지 확인하고 스타 수열 조건에 해당할 경우 스타수열의 길이인 star값을 2 올립니다.
- start값과 answer를 비교해서 최대 값을 저장합니다.
answer를 반환합니다.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int solution(int[] a) {
        int answer = 0;
        Map<Integer, Integer> map = new HashMap<>(a.length);

        for (int i = 0; i < a.length; i++) {
            if (map.get(a[i]) == null) {
                map.put(a[i], 1);
            } else {
                map.replace(a[i], map.get(a[i]) + 1);
            }
        }

        for (int key : map.keySet()) {
            if (map.get(key) * 2 <= answer) continue;
            int star = 0;
            for (int j = 0; j < a.length - 1; j++) {
                if ((a[j] == key || a[j + 1] == key) && (a[j] != a[j + 1])) {
                    star += 2;
                    j++;
                }
            }
            answer = Math.max(answer, star); // 스타 수열 최대값
        }
        return answer;
    }
}

정답도 맞고, 효율성 테스트도 통과했지만 성능이 그렇게 좋지는 않습니다.
처음에 문제를 풀었을 때에는 map의 캐패시티를 초기화 하지 않았었는데, 그 때는 성능이 1번과 같았고, 초기화를 한 경우는 2번과 같은 성능을 보였습니다. 이 이유는 map을 초기화 할 때, initialCapacity값을 주지 않는다면 초기 용량이 16으로 지정되고, 임계 값에 도달할 때마다 두 배가 되는 식으로 사이즈를 조정하기 때문에 성능에 영향을 미칩니다.

 Map<Integer, Integer> map = new HashMap<>(a.length);

세부 설명

해시맵의 최초 버킷 값(initialCapacity)은 16과 같고, 부하율(loadFactor)은 0.75입니다.
부하율(Load Factor) = 해시 맵의 항목 수 (m) / 해시 맵의 버킷 수(n)이기 때문에 초기값을 지정하지 않았을 경우 해시 값의 항목이 늘어날 때마다 (m이 증가할 때마다) 부하율을 확인하고, 부하율보다 클 경우 버킷을 두배로 늘리는 작업(resize)을 하게 됩니다. (예) 0.75 < m / 16 일 경우, resize

HashMap 코드 상에서 putMapEntries메서드에서 위 작업을 하게 됩니다.

즉, map에 값을 넣을 때마다 이런 값들을 체크해야 하고, 맵의 크기가 일정 사이즈 이상 되면 resize()하는 과정이 추가되기 때문에 상대적으로 성능이 나오지 않을 수밖에 없습니다.

1번 (map initialCapacity초기화 안할 때)

2번 (map initialCapacity 초기화 할 때)

문제 해결 방법2

array에 교집합으로 사용할 수 있을만한 key값을 찾기 위해 각 숫자가 호출된 횟수를 저장합니다.
keyset을 순회하면서 스타 수열의 최댓값을 찾습니다.
- a[]를 돌면서 앞과 뒤에 교집합인 값이 있는지, 숫자가 같지는 않은지 확인하고 스타 수열 조건에 해당할 경우 스타수열의 길이인 star값을 2 올립니다.
- start값과 answer를 비교해서 최대 값을 저장합니다.
answer를 반환합니다.

class Solution {
    public int solution(int[] a) {
        int answer = 0;

        int[] count = new int[a.length + 1]; // a길이 미만의 수
        for (int i = 0; i < a.length; i++) {
            count[a[i]]++;
        }

        for (int i = 0; i<count.length; i++) {
            if (count[i] * 2 <= answer) continue;
            int star = 0;
            for (int j = 0; j < a.length - 1; j++) {
                if ((a[j] == i || a[j + 1] == i) && (a[j] != a[j + 1])) {
                    star += 2;
                    j++;
                }
            }
            answer = Math.max(answer, star); // 스타 수열 최대값
        }
        return answer;
    }
}

방법은 위와 같지만, count 갯수를 저장할 때, array에 저장하고 있습니다.
사실 위 1번 문제 해결 방식과 같이 map을 이용하지 않아도, 1~n까지의 값이 몇번 호출되는지를 확인하면 되기 때문에, 배열에 저장하고 순회를 하는 것이 훨씬 더 빠르게 값에 접근할 수 있습니다.

성능 (count array로 만들 때)

마무리

map의 keyset을 순회하는 속도와, 배열의 값에 접근하는건 역시 성능적으로 크게 차이가 나네요. 순회해야 하는 값이 일정하게 정해져 있고 숫자라면 map을 쓰는 것보단 배열을 쓸 수 있도록 어떤 자료구조가 더 좋은 방법일지 항상 생각하는 습관을 가져야겠습니다.

데이터의 크기가 클 경우 map을 초기화 할 때 테이블의 용량이 커지면 배열 크기를 현재 크기의 2배로 재산정하여 동적 확장하는데 시간이 걸리기 때문에 initialCapacity를 주는 것도 중요하네요.

http://wonwoo.ml/index.php/post/1728
(HashMap의 해시충돌과 해시 동적확장 관련 포스트)

저작자표시

'개발 > 알고리즘' 카테고리의 다른 글

[프로그래머스][2019 KAKAO BLIND RECRUITMENT] 길찾기 게임 Level 3 (Java) (0)	2021.01.11
[프로그래머스][2018 KAKAO BLIND RECRUITMENT] 추석 트래픽 (level 3) (0)	2020.12.11

현재글[프로그래머스][월간 코드 챌린지 시즌1] 스타수열 문제 해결 (Java) Level 3

노바의 개발도서관