골드에그

1. 문제요약

코딩테스트 연습 - 기둥과 보 설치 | 프로그래머스 스쿨 (programmers.co.kr)

n x n 크기의 2차원 벽면에 기둥(세로) 와 보(가로) 를 설치해 구조물을 만들려고 한다.

벽면의 크기 n, 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame 이 매개변수로 주어질 때, 모든 명령어를 수행한 후 구조물의 상태를 return 하도록 solution 함수를 완성하라.

룰은 다음과 같다.

① 기둥과 보는 1 X 1 크기의 격자이다. 격자 칸의 각 변에 정확히 일치하도록 설치하여야 한다.

② 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 한다.

③ 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 한다.

2. 문제예제

3. 팩트추출

Fact 1 : 한 지점에서 기둥과 보를 같이 설치/해제할 수 있으므로, map 2차원 배열에 기둥과 보에 대한 정보를 같이 삽입할 수 없다. 기둥의 설치 여부를 나타내는 map 하나와 보의 설치 여부를 나타내는 map 하나를 각각 준비해야 한다.

Fact 2 : 위 문제예제에서도 살펴보았듯이 명령어를 순서대로 적용할 때 실시간으로 가능 여부를 체크해야 한다.

4. 문제전략

문제전략이라고 할 것이 없다. 명령어를 하나씩 받고 아래 2번 3번 룰에 어긋나지 않는지만 체크하면 된다.

② 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 한다.

③ 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 한다.

5. 소스코드

class Solution {
    static int N;
    static boolean[][] column;
    static boolean[][] row;

    public enum materialType {
        COLUMN(0), ROW(1);
        private final int indexNumber;
        materialType(int i) { this.indexNumber = i; }
        public int getIndex() { return indexNumber; }
    };

    public enum constructType {
        DESTRUCT(0), CONSTRUCT(1);
        private final int indexNumber;
        constructType(int i) { this.indexNumber = i; }
        public int getIndex() { return indexNumber; }
    };
    public int[][] solution(int n, int[][] build_frame) {
        int structureCount = 0;
        N = n;
        column = new boolean[n + 2][n + 2];
        row = new boolean[n + 2][n + 2];

        for(int[] frame : build_frame){
            int x = frame[0] + 1;
            int y = frame[1] + 1;
            int structureType = frame[2];
            int commandType = frame[3];

            if(commandType == constructType.CONSTRUCT.getIndex()){
                if(structureType == materialType.COLUMN.getIndex() && checkColumn(x, y)){
                    column[x][y] = true;
                    structureCount++;
                }
                if(structureType == materialType.ROW.getIndex() && checkRow(x, y)){
                    row[x][y] = true;
                    structureCount++;
                }
            } else if(commandType == constructType.DESTRUCT.getIndex()){
                if(structureType == materialType.COLUMN.getIndex()){
                    column[x][y] = false;
                } else if(structureType == materialType.ROW.getIndex()) {
                    row[x][y] = false;
                }
                if(canDestruct(x, y)) {
                    structureCount--;
                    continue;
                }
                if(structureType == materialType.COLUMN.getIndex()){
                    column[x][y] = true;
                } else if(structureType == materialType.ROW.getIndex()) {
                    row[x][y] = true;
                }
            }
        }

        int index = 0;
        int[][] answer = new int[structureCount][3];

        for(int i = 1 ; i <= n + 1 ; ++i){
            for(int j = 1 ; j <= n + 1 ; ++j){
                if(column[i][j]) answer[index++] = new int[]{i - 1, j - 1, materialType.COLUMN.getIndex()};
                if(row[i][j]) answer[index++] = new int[]{i - 1, j - 1, materialType.ROW.getIndex()};
            }
        }
        return answer;
    }
    private boolean checkColumn(int x, int y) {
        return y == 1 || column[x][y - 1] || row[x - 1][y] || row[x][y];
    }

    private boolean checkRow(int x, int y) {
        return column[x][y - 1] || column[x + 1][y - 1] || (row[x - 1][y] && row[x + 1][y]);
    }

    private boolean canDestruct(int x, int y) {
        for(int i = 1 ; i <= N + 1 ; ++i){
            for(int j = 1 ; j <= N + 1 ; ++j){
                if(column[i][j] && !checkColumn(i, j)){
                    return false;
                }
                if(row[i][j] && !checkRow(i, j)){
                    return false;
                }
            }
        }
        return true;
    }
}

1. 문제요약

2096번: 내려가기 (acmicpc.net)

N 줄에 0~9 숫자가 세 개씩 적혀있다. 첫 줄에서 시작해서 마지막 줄까지 내려오는 놀이이다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 주인공이 다음 줄로 내려갈 수 있는 위치라고 할 때,

얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하라.

2. 문제예제

3. 팩트추출

Fact 1 : 3 X N 표를 그래프에서 첫째 줄부터 마지막 줄까지 선택하는 경우의 수를 그래프로 나타냈을 때 DFS, BFS 로 문제를 풀 수 있겠지만, DFS 및 BFS 로 문제를 풀려면 항상 이전의 값이 고정된 값이어야 한다. 여기서는 최대값, 최소값 문제이므로 줄을 타고 내려올수록 값이 갱신되기 때문에 DFS, BFS 로 문제를 풀 수 없다.

Fact 2 : 부분문제이면서 이전의 결과 값들을 재사용하기 때문에 DP 문제로 풀 수 있다.

Fact 3 : 문제를 DP 점화식으로 풀어보면 아래와 같다.

S[i][j] = i행 j열까지 내려오면서 얻을 수 있는 최대의 점수라 할 때,
S[i][0] = max(S[i-1][0], S[i-1][1]) + map[i][0]
S[i][1] = max(S[i-1][0], S[i-1][1], S[i-1][2]) + map[i][1]
S[i][2] = max(S[i-1][1], S[i-1][2]) + map[i][2]

이 점화식에는 특징이 있다. 현재 값이 이전 행 값만 사용한다. 따라서 DP 테이블을 모두 가지고 있을 필요가 없다.

4. 문제풀이(수동)

예제 입력 1 을 minDP 수동으로 풀어본다. maxDP 는 반대 연산이므로 생략한다.

minDP[i] : i 번째 열까지 계산된 최소 비용, maxDP[i] : i 번째 열까지 계산된 최대 비용이라고 하자.

-> 0번째 행

minDP[0][0] = 1

minDP[0][1] = 2

minDP[0][2] = 3

-> 1번째 행

minDP[1][0] = min(minDP[0][0], minDP[0][1]) + map[1][0] = 1 + 4 = 5

minDP[1][1] = min(minDP[0][0], minDP[0][1], minDP[0][2]) + map[1][1] = 1 + 5 = 6

minDP[1][2] = min(minDP[0][1], minDP[0][2]) + map[1][2] = 2 + 6 = 8

-> 2번째 행

minDP[2][0] = min(minDP[1][0], minDP[1][1]) + map[2][0] = 5 + 4 = 9

minDP[2][1] = min(minDP[1][0], minDP[1][1], minDP[1][2]) + map[2][1] = 5 + 9 = 14

minDP[2][2] = min(minDP[1][1], minDP[1][2]) + map[2][2] = 6 + 0 = 6

따라서 제일 작은 6 이 정답이다.

5. 문제전략

문제 전략은 특별히 없다. 점화식을 단순히 구현하면 된다.

다른 DP 문제와 다른 점은 이전 행 정보만 필요하므로 dp[3] 테이블만 가지고 있으면 된다.

한 단계식 행을 계산할 때마다 테이블을 업데이트하면 된다.

6. 소스코드

import java.io.*;
import java.util.*;
class Main {
    static int[] maxDP;
    static int[] minDP;
    static StringTokenizer st;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        maxDP = new int[3];
        minDP = new int[3];

        int row = Integer.parseInt(br.readLine());

        for (int i=0; i<row; i++) {
            st = new StringTokenizer(br.readLine());

            int left = Integer.parseInt(st.nextToken());
            int center = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            solve(i, left,center,right);
        }
        bw.write(Math.max(maxDP[0], Math.max(maxDP[1], maxDP[2])) + " ");
        bw.write(Math.min(minDP[0], Math.min(minDP[1], minDP[2])) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
    private static void solve(int index, int left, int center, int right){
        if (index == 0) {
            maxDP[0] = minDP[0] = left;
            maxDP[1] = minDP[1] = center;
            maxDP[2] = minDP[2] = right;
        } else {
            int tempMaxDP0 = maxDP[0], tempMaxDP2 = maxDP[2];
            maxDP[0] = Math.max(maxDP[0], maxDP[1]) + left;
            maxDP[2] = Math.max(maxDP[1], maxDP[2]) + right;
            maxDP[1] = Math.max(Math.max(tempMaxDP0, maxDP[1]), tempMaxDP2) + center;

            int tempMinDP0 = minDP[0], tempMinDP2 = minDP[2];
            minDP[0] = Math.min(minDP[0], minDP[1]) + left;
            minDP[2] = Math.min(minDP[1], minDP[2]) + right;
            minDP[1] = Math.min(Math.min(tempMinDP0, minDP[1]), tempMinDP2) + center;
        }
    }
}

1. 문제요약

코딩테스트 연습 - 가사 검색 | 프로그래머스 스쿨 (programmers.co.kr)

가사에 사용된 단어들이 담긴 배열 words 와 찾고자 하는 키워드가 담긴 배열 queries 가 주어질 때, 각 키워드 별로 매칭된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성하라.

룰은 다음과 같다.

① 검색 키워드(queries)는 와일드카드 문자인 '?' 가 하나 이상 포함되어 있으며, '?' 는 각 검색 키워드의 접두사 아니면 접미사 중 하나로 표현될 수 있다. 중간에도 '?' 가 들어갈 수 없다. 예를 들어 "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음), "frodo"('?'가 없음) 쿼리들은 불가능하다.

② 검색 키워드(queries)는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있다.

③ 검색 키워드는 중복이 될 수 있다.

2. 문제예제

3. 팩트추출

Fact 1 : 문제 지문에 따르면, 문자열들의 최대 갯수는 100,000 개이고, 쿼리 최대 갯수는 100,000 개로 총

100,000 * 100,000 번 탐색해야 되기 때문에 단순 탐색 시 시간 초과가 발생할 수 밖에 없다. 새로운 알고리즘이 필요하다.

Fact 2 : "?" 는 중간에 있을 수 없다. 무조건 접두사나 접미사에 존재한다. 그런데 ? 의 갯수가 미정이다.
트라이를 통해 검색을 한다고 하더라도 어느 깊이까지 탐색해야 하는지 알 수 없다. 따라서 문자열을 트라이에 저장할 때, 문자열의 길이를 키로 하는 Map 에 같은 키를 가지고 있는 문자열이 몇 개인지 저장할 필요가 있다. ? 를 만났을 때 일일히 트라이의 26개 노드들을 bfs 처럼 탐색할 필요없이 그 문자열의 길이를 Map 에서 검색해서 바로 꺼낸다.

Fact 3 : 자바의 compareTo 메서드는 특이점을 가지고 있다. A.compareTo(B) 라고 가정할 때,

1) A 와 B 가 숫자라면 아래 표와 같이 명확하다.

2) A 와 B 가 문자열이라면 조금 복잡하다.

(compareTo 메서드는 문자열을 처음부터 비교하기 시작한다.)

예제들을 나열해보면 아래와 같다.

"abcd"(4) - "ab"(2) = 2, "abcd"(4) - "a"(1) = 3, "abcd"(4) - ""(0) = 4,

"abhg"(a=97) - "h"(h=104) = -7, "abcd"(c= 99) - "abfd"(f=102) = -3, "abcd"(a=97) - "c"(c=99) = -2

만약 문자열이 정렬이 되어 있는 상태에서 쿼리들을 compareTo 메서드로 비교할 때 쿼리가 크다면 음수가 나올 것이고, 쿼리가 작다면 양수가 나올 것이다.

4. 문제전략

words 문자열들을 여러 번 탐색하기 때문에 (쿼리 문제는 다 그런 듯...) words 문자열들을 정렬할 필요가 있다.

정렬하는 이유는 역시 탐색 범위를 줄이기 위해서다. 문자열을 빠르게 탐색하기 위해서는 트라이 자료구조와 이분 탐색을 생각할 수 있다.

Solving Strategy Item 1 :

처음부터 '?' 문자를 만나면 알파벳 26 가지 경우의 수를 모두 탐색해야 한다. 그래서 문자열을 뒤집어 자료구조를 준비해둔다면, 빠르게 탐색할 수 있다. ? 이 맨 마지막에 있다면 없는 경우의 수는 없고 갯수만 파악하면 되니깐 말이다.

Solving Strategy Item 2 (트라이) :

트라이 자료구조를 통해 링크드 리스트처럼 문자열들을 O(M) (여기서 M은 문자열의 길이) 복잡도로 탐색한다. 주의할 점은 트라이 자료구조를 사용한다고 하더라도 '?' 를 만나면 그 다음 문자 26 가지 알파벳들을 모두 탐색해야 하므로 비효율적이다. '?' 는 중간에는 사용하지 못 한다는 특징을 이용하여 트라이 자료구조를 '?' 전까지만 탐색하고 '?' 를 만나면 더 이상 트라이를 탐색할 필요없이 문자열의 길이를 가진 또 다른 문자열이 있는지 파악하고 그 갯수를 리턴하면 된다. 그래서 트라이 자료구조와 함께 문자열의 길이를 키로 가지고 갯수를 값으로 가지는 Map 자료구조를 같이 셋팅한다.

Solving Strategy Item 3 (이분탐색) :

트라이 자료구조를 사용할 필요없이 문자열을 정렬해놓고 정렬된 특징을 이용하여 이분탐색으로 풀이할 수도 있다. Fact 3 에서 소개한 자바의 compareTo 메서드를 사용하면 쿼리가 크다면 음수가 나오고, 쿼리가 작다면 양수가 나오기 때문에 일정한 값 분포도에 따라 이분탐색이 가능하다. ? 문자열을 빈 문자열로 치환한다면 쿼리가 적용되는 가장 낮은 위치를 가지고 올 수 있고, ? 문자열을 가장 큰 문자 값으로 치환하면 쿼리가 적용되는 가장 높은 위치를 가지고 올 수 있다. 그 위치들을 서로 빼준다면 갯수를 구할 수 있게 된다.

5. 소스코드

1) 트라이

import java.util.*;
class Solution {
    static class Trie {
        Map<Integer, Integer> lengthMap = new HashMap<>();
        Trie[] child = new Trie[26];
        void insert(String str) {
            Trie node = this;
            int len = str.length();
            lengthMap.put(len, lengthMap.getOrDefault(len, 0) + 1);
            for (char ch : str.toCharArray()) {
                int idx = ch - 'a';
                if (node.child[idx] == null)
                    node.child[idx] = new Trie();
                node = node.child[idx];
                node.lengthMap.put(len, node.lengthMap.getOrDefault(len, 0) + 1);
            }
        }
        int find(String str, int i) {
            if (str.charAt(i) == '?')
                return lengthMap.getOrDefault(str.length(), 0);
            int idx = str.charAt(i) - 'a';
            return child[idx] == null ? 0 : child[idx].find(str, i + 1);
        }
    }
    public static int[] solution(String[] words, String[] queries) {
        Trie front = new Trie();
        Trie back = new Trie();
        for (String word : words) {
            front.insert(word);
            back.insert(reverse(word));
        }
        return Arrays.stream(queries).mapToInt(
                query -> query.charAt(0) == '?' ?
                        back.find(reverse(query), 0) :
                        front.find(query, 0)).toArray();
    }
    private static String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}

2) 이분탐색

import java.util.*;

class Solution {
    public static List<Integer> solution(String[] words, String[] queries) {
        Map<Integer, List<String>> frontMap = new HashMap<>();
        Map<Integer, List<String>> backMap = new HashMap<>();

        // words 리스트를 자료구조에 셋팅한다.
        for (String word : words) {
            int len = word.length();
            frontMap.computeIfAbsent(len, i -> new ArrayList<>()).add(word);
            backMap.computeIfAbsent(len, i -> new ArrayList<>()).add(reverse(word));
        }

        for (int key : frontMap.keySet()) {
            frontMap.get(key).sort(null);
            backMap.get(key).sort(null);
        }

        List<Integer> result = new ArrayList<>();
        for (String query : queries) {
            List<String> list;
            if (query.charAt(0) == '?') {
                list = backMap.get(query.length());
                query = reverse(query);
            } else
                list = frontMap.get(query.length());
            if (list == null) result.add(0);
            else result.add(lowerBound(list, query.replace('?', Character.MAX_VALUE))
                    - lowerBound(list, query.replace("?", "")));
        }
        return result;
    }
    private static int lowerBound(List<String> list, String str) {
        int start = 0, end = list.size();
        while (start < end) {
            int mid = (start + end) / 2;
            if (str.compareTo(list.get(mid)) <= 0)
                end = mid;
            else start = mid + 1;
        }
        return start;
    }
    private static String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}

헥사고날 아키텍처를 보고 난 뒤 내가 느낀 점은

SOLID 에서 I 를 강조한 아키텍처라고 생각했다. (I 는 Inversion of Control 의존성 역전)

헥사고날 아키텍처는 레이어드 아키텍처의 일반적인 의존성 방향을 해결하기 위해 고안된 아키텍처이다.

아래 그림과 같다. 각각의 어댑터 구간이 포트를 통해 유스케이스와 연결되어 최종적으로 엔티티에 결합되는 구조이다.

헥사고날 아키텍처가 포트&어댑터 패턴이라고 불리는 이유가 여기있다.

어플리케이션 코어와 어댑터 간의 통신이 가능하려면 애플리케이션 코어가 각각의 포트를 제공한다. 이 때 driving 어댑터에게는 포트가 코어에 있는 유즈케이스 클래스에 의해 구현되어 호출되는 인터페이스가 되며, driven 어댑터에게는 포트가 어댑터에 의해 구현되고 코어에 의해 호출되는 인터페이스가 된다.

포트라는 인터페이스를 통해 내부와 외부의 경계를 나누는 것을 볼 수 있으며, 의존성 방향을 내부와 외부로 나눈 것도 하나의 특징이다. 이 헥사고날 아키텍처를 현업에서 가장 많이 쓰이는 Spring 에서 살펴보자.

일단 소스코드 구조 상으로는 아래와 같다.

유스케이스 (인터페이스, 구현체는 Service)

- 모델 상태를 조작한다

- 출력을 반환한다

- 비즈니스 규칙을 검증한다

- 웹으로부터 입력을 받는다

인터페이스로 존재하며, 구현체 Service 는 입력 포트와 출력 포트를 가지고 있다.

LoadEventPort, RecordEventPort 라는 웹 어탭터의 출력 포트를 통해 out/persistenceAdapter 와 통신하게 된다.

어댑터

웹 어댑터 (WebAdapter 어노테이션, Controller)

- HTTP 요청을 자바 객체로 매핑하기

- 권한을 검사하기

- 입력 유효성 검증하기

- 입력을 유스케이스의 입력 모델로 매핑하기

- 유즈케이스 호출하기

- 유즈케이스의 출력을 HTTP로 매핑하기

- HTTP 응답을 반환하기

영속성 어댑터

- 입력을 받는다

- 입력을 데이터베이스 포맷으로 매핑한다

- 입력을 데이터베이스로 보낸다

- 데이터베이스 출력을 애플리케이션 포맷으로 매핑한다

- 출력을 반환한다

Spring 에서 헥사고날 아키텍처의 흐름을 정리하면 다음과 같다.

Controller(어댑터) -> UseCase(인터페이스, 설마 Port ?) -> Service(구현) -> Port(인터페이스) -> Adapter(구현) -> Repository

원래 그림대로라면 Controller 와 UseCase 사이에 Port 가 존재해야 되는 것이 맞지 않나라고 생각했다. 아니 호출해야 되는 것이 맞다. 그런데 아래 내가 공부한 출처들에서 모두 생략하고 있다. UseCase 자체가 이미 인터페이스이기 때문에 의존성 역전이 이미 되어 있는 상태이니까 생략한 것이 아닐까라고 추측했다. 결국엔 포트를 둔다는 건 서로 다른 영역을 나누기 위한 경계 즉, 인터페이스로 의존성 역전을 한다는 의미일 것이니 말이다.

그런데, 그림을 보면 실체화하는 위치가 다르다. Driving 어댑터 쪽은 UseCase 가 실체화이고, Driven 어댑터 쪽은 Adapter 가 실체화이다. 이 구조를 Spring 구조와 비교해보면 UseCase 가 Input Port 라는 것을 알 수 있고 Service 가 사실상 저 그림에서 UseCase 가 되는 것이다. 혼동이 될 수 있는 여지가 있지만, Spring 에서는 전통적으로 저 방식으로 설계해왔기 때문에 Input Port 가 사라진 것처럼 보인 것이었다.

출처

Hexagonal Architecture with Java and Spring (reflectoring.io)

백문이불여일타 (tistory.com) 

BFS 알고리즘은 넓이 우선 탐색 알고리즘이며, DFS 알고리즘은 깊이 우선 탐색 알고리즘이다.

<템플릿>

public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        // 현재 노드를 방문 처리
        visited[start] = true;
        // 큐가 빌 때까지 반복
        while(!q.isEmpty()) {
            // 큐에서 하나의 원소를 뽑아 출력
            int x = q.poll();
            // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
            for(int i = 0; i < graph.get(x).size(); i++) {
                int y = graph.get(x).get(i);
			  // if 제어문의 반복
			  // if(visited[y]) continue;
                q.offer(y);
                visited[y] = true;
            }
        }
    }

public static void dfs(int x) {
        // 현재 노드를 방문 처리
        visited[x] = true;
        System.out.print(x + " ");
        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for (int i = 0; i < graph.get(x).size(); i++) {
            int y = graph.get(x).get(i);
            if (!visited[y]) dfs(y);
        }
    }

2020 카카오 인턴십 문제로 투 포인터 알고리즘 문제이다.

[문제 정답]

import java.util.*;

class Solution {

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

        HashSet<String> gemSet = new HashSet<>();
        gemSet.addAll(Arrays.asList(gems));
        int typeNum = gemSet.size();
        
        int start = 0;
        int end = 0;
        
        int gemsNum = gems.length;
        int distance = Integer.MAX_VALUE;
        int distanceIndex = Integer.MAX_VALUE;
        
        HashMap<String, Integer> gemMap = new HashMap<>();
        gemMap.put(gems[0], 1);
        while(start < gemsNum && end < gemsNum) {
            //System.out.println("start : " + start + " end : " + end);
            //System.out.println("gemMap.size() : " + gemMap.size() + " gemSet.size() : " + gemSet.size());
            /* 포인터들의 이동으로 정답 조건이 되었을 경우 */
            if(gemMap.size() == gemSet.size()) { 
                /* 답 갱신 */
                /* 가장 짧은 구간이면서 시작 진열대 번호가 가장 작은 구간이 정답 */
                /* 어차피 작은 인덱스에서 순차적으로 실행되기 때문에 같은 구간이라면 인덱스 검사 안 해도 됨 */
                if (distance > end-start) {
                    distance = end-start;
                    answer[0] = start+1;
                    answer[1] = end+1;
                }
                /* start 포인터 지점과 관련한 변수 계산 부분 초기화 */
                gemMap.put(gems[start], gemMap.getOrDefault(gems[start],0) - 1);
                /* 값을 빼서 언더플로우가 되었을 때를 대비한 예외 처리 */
                if(gemMap.get(gems[start]) <= 0)
                    gemMap.remove(gems[start]);
                /* start 포인터 증가 */
                start++;
            } else {
                /* 포인터들의 이동으로 정답 조건이 되지 않았을 경우 */
                /* end 포인터 증가 */
                end++;
                if (end == gemsNum)
                    break;
                /* end 포인터 지점과 관련한 변수 계산 부분 업데이트 */
                gemMap.put(gems[end], gemMap.getOrDefault(gems[end], 0) + 1);
            }
            //System.out.println("after gemMap size : " + gemMap.size());
        }
        return answer;
    }
    
}

Two Pointer 알고리즘이란,
두 개의 포인터를 조정하면서 정답 조건들을 찾아가는 알고리즘이다.

<템플릿>

def two_pointer (array) {
    start, end = 각 포인터 시작 지점;
    /* 순회 배열에 첫 번째 값 넣기 */

    반복문 ( start < start 방향 한계 and end < end 방향 한계 ) {
        If ( /* 포인터들의 이동으로 정답조건이 되었을 경우 */ ) {
            /* 답 갱신 */
            /* start 포인터 지점과 관련한 변수 계산 부분 초기화 */
            /* start 포인터 증가 */
        } else { /* 포인터들의 이동으로 정답조건이 되지 않았을 경우 */
        	/* end 포인터 증가와 end 포인터 증가로 인해 index 예외처리 */
            /* end 포인터 지점과 관련한 변수 계산 부분 업데이트 */
        }
    }
}

이 템플릿에서 주의할 점은 start 와 end 포인터가 보통 0 부터 시작하기 때문에 항상 else 구문부터 시작한다.

end 가 마지막 포인터에 다 다르면 정답조건이 되었는지 비교해야 하는데 그 때에도 순회 배열에 값을 넣고 있다. 그래서 먼저 순회배열에 첫 번째 아이템을 넣고 else 구문에는 end 포인터를 미리 증가하여 2번째 아이템을 넣기 시작해야 end 포인터가 마지막 차례일 때 정답조건이 되었는지 비교할 수 있다.

이 템플릿 말고 인덱스를 신경쓰기 싫어 무한 반복문 안에서 break 구문을 써 빠져 나오는 템플릿도 있다.

ITEM 32 "제네릭과 가변인수를 함께 쓸 때는 신중하라"

가변인자는 매개변수의 개수가 정해지지 않은 함수의 인자를 말한다. 메서드에 넘기는 인자의 개수를 클라이언트가 조절할 수 있어, 인자의 개수만큼 메서드를 여러 번 오버라이딩하지 않고 원하는 개수만큼 인자를 넘길 수 있게 되었다.

가변인자를 정의할 때는 고정 매개변수가 하나 이상 있어야 하고, 고정 매개변수 뒤에 ... 을 붙여 개수가 정해져 있지 않다는 표시를 해주면 된다.

public static void example(String... args) {
    //....
}

가변인수 메서드를 호출하면 내부적으로 가변인수를 담기 위한 배열이 자동으로 하나 만들어진다. 하지만 내부로 감춰야되는 이 배열이 클라이언트에 노출된다는 문제점이 있다. 이 문제점 때문에 varargs 매개변수에 제네릭이나 매개변수화 타입이 포함되면 컴파일 경고가 발생하게 된다. 결론부터 말하자면, 배열과 제네릭을 같이 쓰기 때문이다.

이전 아이템에서 보았듯이, 제네릭과 같은 실체화 불가 타입은 런타임에 타입 관련 정보가 소거가 된다. 타입에 대한 정보가 없기 때문에 실체화 불가 타입으로 varargs 매개 변수를 선언하면 컴파일러가 아래와 같이 경고를 보내게 된다. 

warning: [unchecked] Possible heap pollution from
    parameterized varargs type List<String>

매개변수화 타입의 변수가 타입이 다른 객체를 참조할 가능성이 있게 되고 이는 힙 오염을 발생시키는 원인이 된다.

제네릭과 가변인수를 혼용하여 사용해서 타입 안전성이 깨진 예제를 살펴보자.

    static void dangerous(List<String>... stringLists) {
        List<Integer> integerList = List.of(42); 
        Object[] objects = stringLists;
        objects[0] = integerList;   // 힙 오염 발생
        String s = stringLists[0].get(0);   // ClassCastException
    }

이전 아이템 28 "배열보다는 리스트를 사용하라" 편에서 나온 예제와 유사하다. 인자형태가 List<String> 타입을 배열의 아이템으로 가지고 있기 때문에 배열의 공변성과 제네릭의 불공변성이 충돌해 ClassCastException 예외가 발생하게 된다.

마지막 부분에서 컴파일러가 생성한 (보이지 않는) 형변환이 숨어 있기 때문이다. 타입 안전성이 깨지니 제네릭 varargs 배열 매개변수에 값을 저장하는 것은 안전하지 않다.

자바 7 이전에는 제네릭 가변인수 메서드의 작성자가 호출자 쪽에서 발생하는 경고에 대해서 해줄 수 있는 일이 없었다. 따라서 사용자는 이 경고들을 그냥 두거나 (더 흔하게는) 호출하는 곳마다 @SuppressWarnings("unchecked") 애너테이션을 달아 경고를 숨겨야 했었다.

하지만 자바 7 이후부터는 @SafeVarargs 애너테이션이 추가되어 제네릭 가변인수 메서드 작성자가 클라이언트 측에서 발생하는 경고를 숨길 수 있게 되었다.

그러나 메서드가 안전한 게 확실하지 않다면 @SafeVarargs 애너테이션을 달아서는 안 된다. varargs 배열에 아무것도 저장하지 않고 (그 매개변수들을 덮어쓰지 않고) 그 배열의 참조가 밖으로 노출되지 않는다면(신뢰할 수 없는 코드가 배열에 접근할 수 없다면) 타입 안전성이 보장될 때만 사용해야 한다. 예를 들어 아래와 같은 코드는 타입 안전하지 않다.

    static <T> T[] toArray(T... args) {
        return args;
    }

이 메서드가 반환하는 배열의 타입은 이 메서드에 인수를 넘기는 컴파일타임에 결정되는데, 그 시점에는 컴파일러에게 충분한 정보가 주어지지 않아 타입을 잘못 판단할 수 있다. T 배열이 Object 배열이고 String 타입과 Integer 타입이 toArray 인자로 전달된다고 가정해보자. Object 배열에 여러 가지 타입이 혼종되어 오염이 발생할 수 있다. 자신의 varargs 매개변수 배열을 그대로 반환하면 힙 오염 이 발생하게 되고, 메서드를 호출한 쪽의 콜스택으로까지 전이가 될 수 있다.

    static <T> T[] pickTwo(T a, T b, T c) {
        switch (ThreadLocalRandom.current().nextInt(3)) {
            case 0: return toArray(a, b);
            case 1: return toArray(a, c);
            case 2: return toArray(b, c);
        }
        throw new AssertionError(); // 도달할 수 없다.
    }

이 코드는 위에서 선언한 toArray() 메서드를 호출하고 있는 로직이다. 컴파일러는 toArray() 에 넘길 T 인스턴스 2 개를 담을 varargs 매개변수 배열이 만드는 코드를 생성한다. 여기서 중요한 점은 pickTwo에 어떤 타입의 객체를 넘기더라도 담을 수 있게 하기 위해 Object[] 배열로 반환된다. toArray() 메서드가 돌려준 Object[] 배열이 그대로 pickTwo()를 호출한 클라이언트까지 전달된다. pickTwo()는 항상 Object[] 타입 배열을 반환하게 된다.

    public static void main(String[] args) {
        String[] attributes = pickTwo("좋은", "빠른", "저렴한");
    }

위에서 작성했던 코드를 사용하면, ClassCastException 예외가 발생한다. pickTwo()의 반환값인 Object[] 배열을 String[] 타입의 attributes 에 저장하기 위해 String[] 로 형변환하는 코드가 컴파일러가 자동 생성하기 때문이다. 여기서 유의해야할 점은 해당 코드가 힙 오염을 발생시킨 진짜 원인인 toArray() 로부터 두 단계나 떨어져 있다는 점이다.

제네릭 varargs 매개변수 배열에 다른 메서드가 접근하도록 허용하면 안전하지 않다는 점을 확실하게 잘 보여주고 있다.

    @SafeVarargs
    static <T> List<T> flatten(List<? extends T>... lists) {
        List<T> result = new ArrayList<>();
        for (List<? extends T> list : lists) {
            result.addAll(list);
        }
        return result;
    }

위 코드가 타입 안전한 코드이다. @SafeVarargs 애너테이션을 사용했기 때문에 사용부에서도 문제없이 컴파일된다.

@SafeVarargs 애너테이션은 제네릭이나 매개변수화 타입의 Varargs 매개변수를 받는 모든 메서드에 추가하는 것이 좋다.

또한 @SafeVarargs 애너테이션은 재정의할 수 없는 메서드에만 달아야 한다. 재정의한 메서드도 안전할지는 보장할 수 없기 때문이다.

이 말인 즉슨, 타입 안전하지 않는 Varargs 메서드는 작성하면 안 된다는 것이기 때문에 개발자가 해당 메서드들이 타입 안전하도록 모두 보장해야 한다는 것이다.

첫 번째, Varargs 매개변수 배열에는 아무것도 저장하지 않는다.

두 번째, 그 배열(혹은 복제본)을 신뢰할 수 없는 코드에 노출하지 않는다.

아니면, varargs 매개변수를 List 매개변수로 바꾸는 것도 하나의 방법이다. 이 방식을 앞에서 살펴 보았던 flatten() 메서드에 적용하면 아래와 같이 작성할 수 있다. 단순히 매개변수 선언만 수정한 코드이다.

    static <T> List<T> flatten(List<List<? extends T>> lists) {
        List<T> result = new ArrayList<>();
        for (List<? extends T> list : lists) {
            result.addAll(list);
        }
        return result;
    }

정적 팩토리 메서드인 List.of() 을 활용하면 다음 코드와 같이 이 메서드에 임의 개수의 인수를 넘길 수 있다. List.of()에도 @SafeVarargs 애너테이션이 달려 있기 때문에 가능하다.

audience = flattern(List.of(frends, romans, countrymen));

이 방식은 컴파일러가 이 메서드의 타입 안전성을 검증할 수 있다는 장점이 있다. @SafeVarargs 애너테이션을 직접 달지 않아도 되며, 실수로 안전하다고 판단할 염려도 없게 된다. 하지만 클라이언트 코드가 길어지고, 속도가 조금 느려질 수 있다.

이 방식을 위 pickTwo 메서드에 적용하면 다음과 같다.

    static <T> List<T> pickTwo(T a, T b, T c) {
        switch (ThreadLocalRandom.current().nextInt(3)) {
            case 0: return List.of(a, b);
            case 1: return List.of(a, c);
            case 2: return List.of(b, c);
        }
        throw new AssertionError(); // 도달할 수 없다.
    }

    public static void main(String[] args) {
        List<String> attributes = pickTwo("좋은", "빠른", "저렴한");
    }

"가변인수는 내부적으로 배열을 사용하기 때문에 제네릭과 같이 사용하면 안 된다.

하지만 자바 언어에서허용하고 있다. 그 메서드가 타입 안전하게 만들고 (가변인자 배열에 저장하지 않고, 신뢰할 수 없는 코드에 노출하지 않는다.) @SafeVarargs 어노테이션을 붙여 불편함을 없애자"