프로그래머스 문제풀이(알고리즘) - 보석 쇼핑[카카오 인턴]

시도 1 (오답)

 

보석의 종류가 n 개라면 모든 구간은 최소 n 의 길이 이상이다.

n 부터 n + 1, n + 2 ... 순서대로 탐색하면서 가장 처음 발견한 조건을 리턴하면 된다고 생각했다.

public int[] solution(String[] gems) {
		// 필요한 보석의 최소 수를 구한다.
    Set<String> gemStones = new HashSet<>();

    for (String gem : gems) {
        gemStones.add(gem);
    }

    int target = gemStones.size();
    int start = 0, end = 0;
    while (start == 0) {
        for (int i=0; i<=gems.length - target; i++) {
						// 중복 제거를 위해 set 선택
            Set<String> temp = new HashSet<>();
            for (int j=i; j<i + target; j++) {
                temp.add(gems[j]);
            }

            if (gemStones.size() == temp.size()) {
								// 조건을 만족하는 첫 결과를 반환
                start = i + 1;
                end = i + target;
                break;
            }
        }

        target++;
    }

    return new int[]{start, end};
}

이는 만족하는 최소 보석 종류의 수를 기준 길이로 잡고 해당 길이중 만족하는 범위 구간의 값이 있는지 확인한다.

 

계산 과정

 

Big O

 

이는 최악의 경우, 길이가 1 증가할 때 마다 모든 노드를 한번씩 탐색하기 때문에 O (n^2) 정도로 시간 복잡도를 계산할 수 있다.

 

시도 2 (오답)

 

매번 탐색할 때마다 Set 을 생성하고 다시 값을 넣기 때문에 시간 복잡도는 O (n^2) 이상으로 증가할 것이라고 생각했다.

따라서 다음 범위의 값을 탐색할 때, 기존 계산 결과를 버리지 않고 재사용하기로 마음을 먹었다.

인덱스에 벗어난 값은 버리고, 새로 추가된 값만 넣는 방법으로 계산식을 변경했다.

 

public int[] solution(String[] gems) {
		// 보석 종류수 구함
    Set<String> gemSet = Arrays.stream(gems).collect(Collectors.toSet());

    int stoneSize = gemSet.size(), len = gemSet.size();
    Repository repository = new Repository();

    int[] result = new int[2];
		// 길이가 넘어가기 전까지 계산
    while (len <= gems.length) {

				// 처음 계산 결과 넣기
        for (int i=0; i<len; i++)
            repository.add(gems[i]);
				// 크기를 만족면 break
        if (repository.getSize() == stoneSize) {
            result[0] = 0 + 1;
            result[1] = len;
            break;
        }

        int s = 0, e = s + len;

        // 마지막 것은 추가하고 처음 것은 제거
        for (; e<gems.length; s++, e++) {
            repository.remove(gems[s]);
            repository.add(gems[e]);

            if (repository.getSize() == stoneSize) {
                // 제거한 인덱스 + 1 (번호 + 1)
                result[0] = s + 1 + 1;
                result[1] = s + 1 + len;
                break;
            }
        }

        if (result[1] != 0)
            break;
				
				// 새로운 길이를 탐색할 때 기존 계산 값은 비운다.
        repository.clear();
        len++;
    }

    return result;
}


// 저장소 클래스
static class Repository {
		// 맵에 저장
    private Map<String, Integer> repository = new HashMap<>();

    public void add(String data) {
				// 만약에 값이 있으면 +1 을 하고 없으면 1을 넣어줌
        if (repository.containsKey(data))
            repository.put(data, repository.get(data) + 1);
        else
            repository.put(data, 1);
    }

    public void remove(String data) {
				// 값이 있는데 1이하이면 제거하고 그것보다 크면 -1
        if (repository.containsKey(data)) {
            if (repository.get(data) <= 1)
                repository.remove(data);
            else
                repository.put(data, repository.get(data) - 1);
        }
    }

		// 보석의 종류
    public int getSize() {
        return this.repository.keySet().size();
    }
		// 저장소 비움
    public void clear(){
        this.repository.clear();
    }
}

이를 그림으로 표현하면 다음과 같다

문제점

 

기존 계산 값을 재사용하기 때문에 그 로직만큼 성능의 이점을 가져왔고

덕분에 효율성 테스트 채점에서 0개 맞던 것을 1개 까지 끌어올렸다.

그러나 여전히 O(n^2) 이라는 연산 회수 때문에 속도가 매우 느렸다.

 

시도 3 (정답)

 

만약, 시작 값 start 와 끝 값 end 를 잡고 end 를 +1 해서 범위를 넓히고, 가장 처음 조건을 만족하는 범위를 찾고 그 중에서, 조건을 만족하는 가장 작은 범위를 찾기 위해서 start 를 +1 해서 범위를 줄여 나가는 방식으로 계산을 한다고 가정하자.

조건을 만족하는 가장 작은 범위를 찾았을 때, start 값 이전의 노드는 이후 계산 결과에 다시는 사용하지 않는다.

즉, 이렇게 계산을 하면 노드를 최대 2번만 탐색하기 때문에 시간 복잡도는 O (n) 이 된다.

public int[] solution(String[] gems) {
    int[] result = new int[2];

    Set<String> set = new HashSet<>();

    for (String g : gems)
        set.add(g);

    int kind = set.size();

    Repository repository = new Repository();
    int start = 0, end = 0;
    int minDist = Integer.MAX_VALUE;

    while(true) {

        if (repository.getSize() >= kind) {
            repository.remove(gems[start]);
            start++;
        }
        else if (end == gems.length)
            break;
        else {
            repository.add(gems[end]);
            end++;
        }


        if (repository.getSize() == kind) {
            if (Math.abs(end - start) < minDist) {
                minDist = Math.abs(end - start);
                result[0] = start + 1;
                result[1] = end;
            }
        }
    }

    return result;
}

// 저장소 클래스
static class Repository {
		// 맵에 저장
    private Map<String, Integer> repository = new HashMap<>();

    public void add(String data) {
				// 만약에 값이 있으면 +1 을 하고 없으면 1을 넣어줌
        if (repository.containsKey(data))
            repository.put(data, repository.get(data) + 1);
        else
            repository.put(data, 1);
    }

    public void remove(String data) {
				// 값이 있는데 1이하이면 제거하고 그것보다 크면 -1
        if (repository.containsKey(data)) {
            if (repository.get(data) <= 1)
                repository.remove(data);
            else
                repository.put(data, repository.get(data) - 1);
        }
    }

		// 보석의 종류
    public int getSize() {
        return this.repository.keySet().size();
    }
		// 저장소 비움
    public void clear(){
        this.repository.clear();
    }
}