골드에그

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. 문제요약

코딩테스트 연습 - 가사 검색 | 프로그래머스 스쿨 (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();
    }
}

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;
    }
    
}