[プログラマー(Programmers)]ジュエリーショッピング(java,ダブルポインタ)/2020ココア実習

こんにちは!今日解決しなければならない問題はプログラマーのジュエリーショッピングの問題です.この問題は2020年のKACA実習で出たものです.

1）問題リンク

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

2）問題を解く

✔gems配列中の宝石の種類を入手する：setを使用する

まず、gems配列に格納されている宝石の種類を知る必要があります.setは重複しない要素を格納するので、setを宣言してgems配列の値をsetに入れることで取得できます.

✔ダブルポインタ問題：左、右の2つのポインタを使用

これは二重ポインタの問題です.ダブルポインタアルゴリズムは、リスト(または配列)に順次アクセスする必要がある場合に、2つの点の位置を記録するアルゴリズムである.問題では,左,右変数を用いて2点の位置を記録し,左右の結果値が最小となるポインタを出力することが問題である.

✔while論理フロー説明

問題解決コードで、左、右のポインタを使用するロジックは次のとおりです.

○ポインタフローを含むmap宣言

宣言キーはStringで、値はIntegerのマッピングです.値はmapに格納されているString数です.たとえば、右ポインタが下の図で3番目に移動すると、マッピングはDIAが2であるため、RUBY=2}を格納します.

①右ポインタ移動

右ポインタを移動した後、宣言されたマッピングに保存します.ポインタをset size(gems配列で宣言された宝石の種類数)とmap sizeと同じ位置に移動します.

②左ポインタ移動

右ポインタが6に移動するとmapは{DIA=3,RUBY=2,EMERALD=1,SAPHIRE=1}を格納する.(順序が異なる場合があります)mapのsizeは4、setのsizeは4なので左ポインタが移動します.左ポインタは移動するたびにmapのInteger value値を削除します.mapの値が0の場合、mapからキーを削除します.
map sizeとsetsizeが等しい場合は、右から左を計算してdistance変数に保存し、前の距離より小さい場合は右ポインタ値と左ポインタ値を保存します.

③右ポインタを動かす

左ポインタが3に移動すると、mapは{DIA=2、EMERALD=1、SAPHIre=1}を格納します.(順序が異なる可能性があります)マッピングサイズとset sizeが異なるため、今回は正しいポインタを移動します.さっきのように、右ポインタが移動するたびにmapのvalue値が1つ高くなります.

④右ポインタがgems配列末尾に到達

右ポインタがgems配列の末尾に達したため、論理を終了します.②計算して保存した右ポインタと左ポインタの値を出力すればよい.

3）完全コード

import java.util.*;

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

        Set<String> gemSet = new HashSet<>();
        Collections.addAll(gemSet, gems);

        Map<String, Integer> map = new HashMap<>();

        int gemSize = gemSet.size();
        int arrSize = gems.length;

        //움직이는 변수들 길이 저장하는 변수
        int distance = Integer.MAX_VALUE;
        //움직이는 변수(left, right)
        int right = 0;
        int left = 0;

        //정답 위한 변수(start, end)
        int start = 0;
        int end = 0;

        while (true) {
            if (map.size() == gemSize) { //left가 움직일 차례, map에 있는 원소 빼는 역할
                String leftGem = gems[left];

                map.put(leftGem, map.get(leftGem) - 1);
                if (map.get(leftGem) == 0) {
                    map.remove(leftGem);
                }
                left++;
            } else if (right == arrSize) {
                break;
            } else {    //right가 움직임, map에 원소를 더하는 역할
                String rightGem = gems[right];
                map.put(rightGem, map.getOrDefault(rightGem, 0) + 1);
                right++;
            }

            if (map.size() == gemSize) {
                if (right - left < distance) {
                    distance = right - left;
                    start = left + 1;
                    end = right;
                }
            }
        }

        answer[0] = start;
        answer[1] = end;

        return answer;
    }
}

4）感じ

✔map getOrDefaultの使用

map.getOrDefault(a,b)のaビットに入るのは「KEY」そのものです.私は鍵ではなく地図です.get(key)値を入力すべきだと思っていたので、間違えました.この方法はいろいろ使っているようなので、ぜひ!!覚えておきます.

✔2針問題の感想に答える

初めて二重ポインタの問題をやったので、思ったより面白かったです.私のブログでは、bfs/dfs問題の解答は他のアルゴリズムテクニックよりも多く、偏らないで、二重ポインタやバイナリ検索など多くの問題を解決しようとしています.