[프로그래머스] 보석쇼핑

이 문제의 경우는 효율성과 정확성이 별도로 채점되는 문제이다.

정확성의 경우 이중 for문을 이용해서 0,0~N,N까지 모든 경우 중에서 모든 보석을 포함하고 있는 모든 경우를 체크해서 정렬을 해주면 맞출 수 있다.

하지만 O(N^2) 의 시간 복잡도를 가지기 때문에 N의 크기 제한이 10만 인것을 생각해보면 효율성은 통과하기 힘들다.

이 문제에서 주목해야 할 부분은 "특정 범위의 보석을 모두 싹쓸이 한다" 이다.

이 부분만 봐도 투포인터를 이용하여 풀어야 할 것 같다는 생각이 드는 문제이다.

투포인터를 이용하여 범위를 조정해 나가며 조건을 만족하는 모든 값을 저장한 후 문제에서 요청하는대로 값을 정렬하여 보내준다.

이때 잊어버리면 안되는 점은 "만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다." 를 유념해야한다.

class Point {
    private final int left;
    private final int right;
    private final int length;

    Point(int left, int right, int length) {
        this.left = left;
        this.right = right;
        this.length = length;
    }

    public int getLeft() {
        return left;
    }

    public int getRight() {
        return right;
    }

    public int getLength() {
        return length;
    }
}


class Solution {
    static int answer;

    public Set<String> makeSet(String[] gems) {
        return new HashSet<>(Arrays.asList(gems));
    }

    public void putToGemMap(Map<String, Integer> map, String gem) {
        map.putIfAbsent(gem, 0);
        map.computeIfPresent(gem, (k, v)-> v+1);
    }

    public void pollFromGemMap(Map<String, Integer> map, String gem) {
        map.computeIfPresent(gem, (k, v)-> v-1);
        if(map.getOrDefault(gem, 0) == 0) map.remove(gem);
    }

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

        Set<String> gemSet = makeSet(gems);
        //Map에 각 gem에 대해서 몇개를 가지고 있는지 집어 넣음
        Map<String, Integer> boughtGem = new HashMap<>();
        List<Point> points = new ArrayList<>();

        int leftPointer = 0;
        int rightPointer = 0;

        boughtGem.put(gems[leftPointer], 1);
        //Array를 탐색
        while(leftPointer <= rightPointer) {
            if(boughtGem.size() == gemSet.size())
                points.add(new Point(leftPointer, rightPointer, rightPointer - leftPointer));

            if(boughtGem.size() < gemSet.size() && rightPointer< gems.length - 1) {
                rightPointer++;
                putToGemMap(boughtGem, gems[rightPointer]);
            }

            else if(leftPointer< gems.length  - 1){
                pollFromGemMap(boughtGem, gems[leftPointer]);
                leftPointer++;
            }

            if(leftPointer == gems.length - 1 && rightPointer == gems.length - 1) break;
        }

        points = points.stream().sorted((a, b) -> {
            if (a.getLength() == b.getLength()) {
                return a.getLeft() - b.getLeft();
            }

            return a.getLength() - b.getLength();
        }).collect(Collectors.toList());

        answer[0] = points.get(0).getLeft() + 1;
        answer[1] = points.get(0).getRight() + 1;

        return answer;
    }
}

---

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/67258