개발옹

지난번에 트라이를 공부하고 포스팅으로 정리했는데, 아래 포스팅에서는 Map Interface로 구현을 했었습니다.

그런데 백준 - 전설(19585)을 트라이 자료구조로 풀어도 시간 초과가 나길래 더 찾아보니 Array로 구현하는 방식도 있어서 이번에는 Array 방식으로 구현한 트라이도 추가했습니다.

트라이(Trie)란?

트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조로, 자세한건 지난번 포스팅을 참고해주세요.

트라이(Trie) 구현 방식

트라이(Trie)는 두 가지 방식으로 구현할 수 있습니다.

1. Array를 이용하여 구현
2. Map Interface를 이용하여 구현

Array로 구현할 경우, 빠른 저장과 탐색을 할 수 있다는 장점이 있지만 필요한 메모리의 크기가 너무 크다는 것이 단점입니다.

Map Interface로 구현할 경우, 메모리를 동적으로 할당하여 필요 노드만 메모리를 할당할 수 있다는 장점이 있지만 메모리 제한이 있는 경우 최적화 작업이 꽤 까다롭다는 단점이 있습니다.

1. Array로 구현

Array로 구현할 경우, Trie의 Node별 자식 노드를 Node형 배열로 구현합니다. 

이때, Trie Node에 들어가는 단어는 영어 소문자만 있다고 가정하며, 각 노드는 영어 소문자를 정수형(int)으로 변환하여 인덱스로 사용합니다.

* 자세한 설명은 이전 포스팅을 참고해주세요.

Node 클래스 생성

Map으로 구현한 Trie 의 Node와 다르게 자식 노드를 Node[] 로 초기화합니다.

childNode의 인덱스에 영어 소문자를 정수형(int)로 변환한 값이 들어가게 됩니다.

그리고 자식 노드의 수(childCnt)와 해당 노드의 문자(val)도 저장해줍니다.

static final int SIZE = 26; // 영어 소문자는 26자
private class Node {
    Node[] childNode = new Node[SIZE]; // 자식 노드: 영어 소문자를 인덱스화 하여 저장
    boolean endOfWord; // 단어의 끝인지에 대한 플래그
    int childCnt = 0; // 자식 노드 수
    char val; // 노드의 문자
}

트라이(Trie) 자료구조 클래스 생성

public class TrieArray {
    private Node rootNode;
    public TrieArray() {
    	rootNode = new Node();
    }
}

기본 메서드

1) 노드 추가(insert)

문자열의 문자를 순회하면서 해당 문자가 자식노드로 있는지 확인하여 노드를 추가하는 메서드입니다. 

Map으로 구현했을때와는 다르게 현 노드의 자식 노드가 null 이 아닌지, 즉, 생성되어있는지를 확인하여, 없다면 생성합니다. 

생성시에는 자식 노드를 추가하고, 자식 노드의 문자를 할당해주고, 현 노드의 자식 노드 수를 증가시킵니다.

public void insert(String word) {
    Node node = this.rootNode;
    // 단어의 문자를 순회하면서 자식 노드 확인
    for (int i=0; i < word.length(); i++) {
        char c = word.charAt(i);
        // 단어의 특정 문자를 인덱스(int)로 변환
        int intVal = charToInt(c);
        // 현 노드에 인덱스로 변환한 문자가 자식노드로 있는지 확인
        if (node.childNode[intVal] == null) {
            // 자식 노드에 없는 문자라면 새로 생성
            node.childNode[intVal] = new Node();
            node.childNode[intVal].val = c;
            node.childCnt++;
        }
        // 다음 탐색 노드를 자식노드로 변경
        node = node.childNode[intVal];
    }
    node.endOfWord = true; // 단어(word)의 문자를 모두 순회하면 마지막 노드는 리프 노드(=마지막 문자)이기때문에 endOfWord를 true로 설정
}

2) 포함 여부 확인(contains)

문자열이 트라이에 있는지 확인하는 메서드로, 배열 방식에 맞게 구현해주면 됩니다.

public boolean contains(String word) {
    Node node = this.rootNode;
    char c;
    for (int i=0; i<word.length(); i++) {
        c = word.charAt(i);
        int intVal = charToInt(c); // 문자를 인덱스로 변환
        if (node.childNode[intVal] == null) return false; // 현재 탐색하는 문자가 자식 노드에 없다면 존재하지 않는 단어
        node = node.childNode[intVal];
    }
    return node != null && node.endOfWord; // 마지막 문자 여부를 반환
}

3) 노드 삭제(delete)

트라이에 존재하는 문자열을 삭제하는 메서드로, 삭제 조건에 맞춰 배열 방식에 맞게 구현해주면 됩니다.

public void delete(String word) {
    delete(this.rootNode, word, 0);
}
// 재귀 호출을 위한 함수 오버로딩
public void delete(Node node, String word, int idx) {
    // 단어의 마지막인 경우
    if (idx == word.length()) {
        if (!node.endOfWord) throw new Error(word + " not exist"); // 단어가 존재하지 않음
        node.endOfWord = false; // 단어의 끝 문자 표시를 false로 변경: 해당 문자 노드를 삭제하기 위함
        return; // 리프 노드의 부모 노드로 return
    } else {
        if (node.childCnt == 0) throw new Error(word + " not exist"); // 자식 노드가 없는 경우(=단어가 존재하지 않는 경우)
    }

    char c = word.charAt(idx); // 현재 확인해야하는 문자
    int intVal = charToInt(c); // 문자를 인덱스로 변환

    Node child = node.childNode[intVal]; // 자식 노드 가져오기
    // 자식 노드가 있다면 리프 노드까지 내려가야 하므로 재귀 호출
    delete(child, word, idx+1);
    // 현 노드의 자식 노드가 삭제되었다면, 현 노드의 자식 노드 수 1 차감
    if (node.childNode[intVal] == null) node.childCnt--;
    // 현 노드의 자식 노드가 리프 노드이고(=자식 노드가 없음), 단어의 끝인 문자가 아니라면 삭제
    if (child.childCnt == 0 && !node.endOfWord) node = null;
}

🧪 구현 테스트

구현 테스트는 Map 방식과 동일하니, 해당 포스팅을 참고해주세요 :)

💡 전체 코드(Array로 구현)는 아래 링크에서 확인해주세요.

2. Map Interface로 구현

아래 코드는 Map Interface로 구현한 코드이며, 자세한 설명은 이전 포스팅을 참고해주세요.

💡 Trie를 Map, Array로 구현한 코드는 아래 링크에서 확인해주세요.

Reference

문제 링크

https://www.acmicpc.net/problem/2531

문제 설명

회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.

새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.

1. 원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.
2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.

위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9,7,30,2), (30,2,7,9), (2,7,9,25) 세가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2,7,9,25)를 고르면 5가지 종류의 초밥을 먹을 수 있다.

회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d이다.

두 번째 줄부터 N개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때 초밥의 종류를 나타내는 1 이상 d 이하의 정수가 각 줄마다 하나씩 주어진다.

출력

주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 하나의 정수로 출력한다.

입출력 예

문제 풀이

[고려사항]

단순하게 생각했을땐 벨트에 초밥이 올라가있는 순서를 따져서 N개 중 k개로 조합을 확인하면 될까 싶지만, 그렇게 하면 시간 초과가 된다. N은 최대 30,000개, k는 최대 3,000개인데, 모든 조합을 가져오면 O(N^k)이 걸리기 때문이다. 

[알고리즘, 구현방법]

이 문제는 고정된 범위(k)가 있고, 배열 순서대로 범위만큼씩 확인하는 것이 필요하므로 *슬라이딩 윈도우 알고리즘을 이용한다.

*슬라이딩 윈도우는 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘이다.

✅ 1번째 정답

정답이긴 했으나, 다른 사람의 풀이를 확인했을때 내 코드에 비해 속도가 빨라서, 다른 방식으로 풀어야겠다고 생각했다.

[풀이 과정]

우선 List에 쿠폰 번호의 초밥을 넣고, k개의 초밥(0번 인덱스 ~ k-1번 인덱스)을 넣는다. 이러면 첫번째 윈도우(범위)의 초밥을 넣은것이 된다. 그 후 중복되는 초밥을 제외하고 수를 세기 위해 Set에 List를 그대로 넣고 Set의 size를 최대 초밥 종류수(maxCnt)에 할당한다.

• 7 9 7 30 2 7 9 25 가 벨트에 올라간 초밥이라면 현재 List에는 [30, 7, 9, 7, 30] 이 할당되어 있음

그리고 남은 경우를 확인할때는, (k-1)번만큼 반복하면서 모든 초밥 조합을 확인한다.

윈도우를 한칸씩 뒤로 밀면서 확인해야하므로, List의 1번 인덱스를 지우고 다음 초밥을 넣는다.

• 이때 List의 0번 인덱스에는 쿠폰 번호를 고정으로 넣어두었기에 1번 인덱스부터 k번 인덱스까지가 현재 확인하고 있는 벨트에 올라간 초밥이 된다. 
• '다음 초밥' 인덱스는 (반복문 인덱스 % N) 으로 설정한다. 회전 초밥이므로 배열의 끝까지만 탐색하면 되는것이 아니라, 윈도우(범위)가 마지막 인덱스에서 시작하면 맨 앞 초밥도 해당 경우의 수에 포함되어야 하기 때문이다
  • 7 9 7 30 2 7 9 25 로 초밥이 배치된 벨트에서, 25가 윈도우의 시작이면 현재 윈도우는 25,7,9,7(7 9 7 30 2 7 9 25)이기 때문

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        int[] sushi = new int[N];
        for (int i=0; i<N; i++) {
            sushi[i] = Integer.parseInt(br.readLine());
        }
        List<Integer> list = new ArrayList<>();
        list.add(c); // 쿠폰 번호는 고정으로 추가
        for (int i=0; i<k; i++) {
            list.add(sushi[i]);
        }
        Set<Integer> set = new HashSet<>(list);
        int maxCnt = set.size(); // 최대 종류 수

        for (int i=k; i<N+k; i++) {
            list.remove(1);
            list.add(sushi[i % N]);

            set = new HashSet<>(list);
            if (maxCnt < set.size()) {
                maxCnt = set.size();
            }
        }
        System.out.println(maxCnt);
    }
}

✅ 2번째 정답 (속도 개선)

결론부터 말하면 속도를 2,840ms에서 168ms로 (2,672ms)개선했다.

첫번째 시도에서는 List, Set을 이용해서 문제를 풀었는데, 두번째 풀이방식에서는 초밥을 카운팅하는 배열을 생성해서 풀어서 속도를 개선할 수 있었다. 

[풀이 과정]

윈도우에 포함되는 초밥의 종류별로 카운팅하기 위한 배열(sushi)과 벨트 위에 있는 초밥을 저장하기 위한 배열(plates)을 생성해서 이 두 배열을 가지고 문제를 풀었다. 

첫번째 윈도우를 세팅할 때, 윈도우 내에 있는 초밥의 카운팅을 1씩 추가한다. 이때, 초밥의 종류 수는 새로운 초밥인 경우에만 플러스한다.

그리고 N번만큼 반복하며 모든 초밥 조합을 확인한다.

반복문을 돌기 전에 이미 첫번째 윈도우는 세팅되어있기 때문에 반복문 상단에서 초밥 종류의 최대 가짓수를 계산한다.

• 이때 쿠폰 번호의 초밥이 윈도우 내에 포함되어있지 않다면(=초밥 종류별 카운팅이 0이라면) 초밥 종류 가짓수를 1 더해서 계산한다.

이후에 윈도우를 한칸씩 이동하면서 초밥의 종류수를 계산한다. 이때 아래 두 조건을 고려하여 구현한다.

• 윈도우 내의 첫번째 초밥을 제외할 때 윈도우내에 중복된 초밥이 있었다면 종류 수를 빼면 안된다.
• 다음 초밥 가져올때는 중복된 초밥이라면 카운팅을 하면 안된다. 즉, 새로운 종류인 경우에만 카운팅해야한다.

모든 초밥의 조합을 확인한 후 초밥의 최대 종류 수를 출력하면 된다.

정답 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        int[] sushi = new int[d+1]; // 초밥 모든 종류의 카운팅을 위한 배열
        int[] plates = new int[N]; // 벨트 위 접시에 있는 초밥
        for (int i=0; i<N; i++) {
            plates[i] = Integer.parseInt(br.readLine());
        }

        // 첫번째 윈도우 세팅
        // 첫번째 초밥부터 k번째 초밥까지 윈도우(범위)로 설정
        int cnt = 0; // 현재 윈도우의 종류 수
        for (int i=0; i<k; i++) {
            sushi[plates[i]]++; // 윈도우 내에 있는 초밥 카운트 up
            if (sushi[plates[i]] == 1) cnt++; // 새로운 초밥 종류인 경우에만 카운팅
        }

        int max = 0; // 최대 종류 수
        for (int i=0; i<N; i++) {
            if (sushi[c] == 0) max = Math.max(cnt+1, max); // 현 윈도우에 쿠폰 초밥이 없는 경우
            else max = Math.max(cnt, max);

            // 윈도우(범위) 이동
            // 첫번째 초밥을 제외할 때, 윈도우내에 중복된 초밥이 있었다면 종류 수를 빼면 안됨
            if (--sushi[plates[i]] == 0) cnt--;

            // 다음 초밥 가져올때, 중복된 초밥이라면 카운팅을 하면 안됨. 새로운 종류인 경우에만 카운팅
            if (sushi[plates[k++ % N]]++ == 0) cnt++;
        }
        System.out.println(max);
    }
}

데이터베이스에서 필수로 쓰이는 날짜형 데이터에 대해 정리해두고자 합니다.

4가지 유형의 데이터 타입에 대한 정리와 일자와 시간을 모두 표현하는 DATETIME과 TIMESTAMP의 차이를 알아보겠습니다.

1. DATE, DATETIME, TIMESTAMP, TIME

MySQL에서는 일자와 시간을 표현하기위해 DATE, DATETIME, TIMESTAMP, TIME 타입을 사용할 수 있습니다.

일자와 시간을 모두 표현하는 DATETIME과 TIMESTAMP는 얼핏봐서는 비슷한데, 차이점이 있습니다. 

이 둘의 차이를 알고 있어야 예상치 못한 에러사항을 대비할 수 있기 때문에, 차이점을 한 번 알아보겠습니다.

2. DATETIME vs TIMESTAMP

1) 범위

일자와 시간을 모두 표현하는 두 타입은 일단 표에서 볼 수 있듯 범위에서 차이가 있습니다.

DATETIME의 범위는 '1000-01-01 00:00:00' 부터 '9999-12-31 23:59:59' 로, 시간대에 관계없이 절대적인 일자와 시간을 저장합니다.

TIMESTAMP의 범위는 '1970-01-01 00:00:01' UTC 부터 '2038-01-19 03:14:07' UTC 로, 데이터가 UTC로 변환되어 저장되며 검색시 현재 시간대로 변환이 됩니다. TIMESTAMP의 범위는 Unix 시간과 관련이 있어, 2038년 문제로 인해 최대 범위가 2038년까지로 제한됩니다.

2) Timezone의 적용 여부

두 타입은 Timezone의 적용 여부에 차이가 있습니다.

Timezone은 동일한 시간을 따르는 지역을 의미하고, 해당 국가에 의해 법적으로 지정되는 값입니다.

UTC, Asia/Seoul 등의 표기가 해당 시간이 어떤 로컬을 기준으로 작성한 것인지를 명시하는 것입니다.

MySQL은 TIMESTAMP 값을 현재 시간대에서 *UTC로 변화하여 저장하고, 다시 UTC에서 현재 시간대로 변환하여 검색합니다.

*UTC: 국제 표준시

기본적으로 설정되는 시간대는 서버 시간으로, 시간대 설정이 일정하게 유지된다면 저장한 값과 동일한 값을 반환받습니다.

만약 TIMESTAMP 값을 저장한 후, 시간대를 변경하고 값을 조회하면, 조회 결과는 저장한 값과 다르게 됩니다. 시간대 변환시 동일한 시간대를 사용하지 않았기 때문에 이러한 결과가 발생하는 것입니다.

*현 시간대는 시스템 변수인 time_zone 에 설정된 값으로 확인할 수 있습니다.

예시

실제로 데이터가 어떻게 저장되는지 확인해봅시다.

create table date_example
(
  test_date date,
  test_datetime datetime,
  test_timestamp timestamp,
  test_time time
);

insert into date_example values (now(), now(), now(), now());

테스트 테이블을 만들고 현재 시간으로 데이터를 저장했습니다.

mysql> select * from date_example;
+------------+---------------------+---------------------+-----------+
| test_date  | test_datetime       | test_timestamp      | test_time |
+------------+---------------------+---------------------+-----------+
| 2024-07-09 | 2024-07-09 10:36:17 | 2024-07-09 10:36:17 | 10:36:17  |
+------------+---------------------+---------------------+-----------+
1 row in set (0.00 sec)

왼쪽부터 DATE, DATETIME, TIMESTAMP, TIME 형식의 데이터가 저장된 것을 확인할 수 있습니다.

여기서 time_zone을 수정해보고 다시 같은 데이터를 확인해보겠습니다.

mysql> SET time_zone = '+01:00';
Query OK, 0 rows affected (0.00 sec)

mysql> select * from date_example;
+------------+---------------------+---------------------+-----------+
| test_date  | test_datetime       | test_timestamp      | test_time |
+------------+---------------------+---------------------+-----------+
| 2024-07-09 | 2024-07-09 10:36:17 | 2024-07-09 02:36:17 | 10:36:17  |
+------------+---------------------+---------------------+-----------+
1 row in set (0.00 sec)

time_zone에 변화를 주고 조회해보니 TIMESTAMP 형식의 test_timstamp 값만 변한 것을 알 수 있습니다.

• SET time_zone = '+01:00' : UTC+09:00 보다 8시간 이전으로 설정

이는 위에서 기재했듯 TIMESTAMP 는 시스템 변수인 time_zone을 기준으로 결과를 반환하기 때문입니다.

그렇기때문에 TIMESTAMP를 사용하고, 로컬 시간이 다른 글로벌 서비스를 운영할 때에는 이를 유의해서 관리해야합니다.

TIMESTAMP를 사용하면 로컬 시간에 따라 혼란이 있을 수는 있으나, 글로벌 서비스를 운영할때에는 유용하게 쓰일 수 있습니다.

만약 DATETIME을 사용한다면 로컬 시간이 제대로 반영되지 않아서, 서울에서 오전 11시에 작성한 글을 미국에서 조회하는 경우, 동일하게 오전 11시로 반영되는 등의 문제가 발생합니다. 이렇게 시간이 다른 지역이 있는 경우, TIMESTAMP가 더 적합할 수도 있습니다.

이러한 특징들로 DATETIME은 절대적인 시간 기록에 적합하고 TIMESTAMP는 시간대에 따라 변환이 필요한 경우 유용하게 쓰입니다.

3) DATETIME 과 TIMESTAMP의 자동 초기화

DATETIME와 TIMESTAMP는 현재 일자와 시간을 기본값, 자동 업데이트 값으로 설정할 수 있습니다.

• 자동 초기화: 데이터 삽입시 명시적으로 지정하지 않아도 현재 타임스탬프로 설정
• 자동 업데이트: 데이터 갱신시 자동으로 현재 타임 스탬프로 갱신

설정 방법

자동 초기화와 업데이트를 설정하려면 DATETIME과 TIMESTAMP 열 정의에서 지정해주면 됩니다.

• 자동 초기화를 위한 초기값 설정: DEFAULT ~~
• 자동 업데이트를 위한 설정: ON UPDATE ~~

DATETIME과 TIMESTAMP를 각각 형식으로 가지는 column이 있는 테이블을 아래와 같이 정의하면 자동으로 값이 들어갑니다.

CREATE TABLE t1 (
  ts TIMESTAMP DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  dt DATETIME DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP
);

위 테이블에 아무 값도 지정하지 않고 INSERT를 하고 조회를 하면, 

insert into t1 values();

아무 값도 넣지 않았는데도 현재 시간이 저장된 것을 확인할 수 있습니다.

mysql> select * from t1;
+---------------------+---------------------+
| ts                  | dt                  |
+---------------------+---------------------+
| 2024-07-09 12:13:49 | 2024-07-09 12:13:49 |
+---------------------+---------------------+
1 row in set (0.00 sec)

이번엔 아래와 같은 테이블을 생성해봅시다.

CREATE TABLE t1 (
  ts TIMESTAMP DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP,
  dt DATETIME DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP
);

위에서 정의한 것과 다른점은 DEFAULT NULL 부분입니다.

이는 기본값을 NULL로 두겠다는 것을 의미합니다.

mysql> INSERT INTO t1 VALUES();
Query OK, 1 row affected (0.00 sec)

mysql> SELECT * FROM T1;
+------+------+
| ts   | dt   |
+------+------+
| NULL | NULL |
+------+------+
1 row in set (0.00 sec)

위와 동일하게 아무 값도 넣지 않고 INSERT를 하면, 이번에는 NULL 값이 저장된 것을 확인할 수 있습니다.

마치며,

서비스를 운영하면 필수적으로 포함되는 날짜와 시간 데이터형에 대한 내용을 정리했습니다.

특히 DATETIME과 TIMESTAMP의 차이에서 헷갈리는 부분이 많았는데, 이번에 정리하고 찾아보면서 한번 더 확인할 수 있었던 시간이었습니다. 날짜 데이터와 관련해서는 다음에 문자열로 변환하는 등 실제로 값을 조회하고 처리하는 부분에 대해서 알아보겠습니다.

Reference

문제 링크

https://www.acmicpc.net/problem/5052

문제 설명

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자.

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26 

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

입출력 예

문제 풀이

[고려사항]

전화번호수는 최대 10,000(만)개라서 만약 시간 복잡도가 O(N^2)이 되면 100,000,000(1억) 인데 제한시간이 1초라서, 모든 문자를 돌면서 찾는게 아닌 방법을 찾아야한다.

[알고리즘, 구현방법]

문제에서 전화번호 길이가 길어야 10자리라고 했고, 문자열에 대한 검색을 빠르게 처리해야하기 때문에 트라이(Trie)를 사용해서 구현했다.

트라이는 문자열 추가와 탐색을 O(M)만에 가능하게 하기 때문에 이 문제에 적합하다고 생각했다. (+메모리 크기가 단점이지만, 이 문제에서는 전화번호 길이가 길어야 10자리)

*트라이 관련 포스팅은 아래에서 참고

✅ 정답

입력으로 받은 전화번호 길이가 짧은 순으로 트라이에 문자를 추가하면서, 해당 문자의 자식노드가 있고, 그 자식 노드가 단어의 끝이라면 일관성이 없는 경우에 해당한다.

이때 전화번호 길이가 짧은 순으로 하지 않고 길이가 긴 문자열부터 추가하면서 확인한다면, 위의 조건으로는 제대로 검증할 수 없다. 만약 911234이 먼저 트라이에 추가되고 911이 들어온다면, 911234가 추가는 되어있지만, 911에서 마지막 1에 단어의 마지막이라는 표시가 없기 때문에 위의 조건에 부합하지 않는다.

그래서 전화번호를 먼저 모두 입력받아서 저장하고, 전화번호의 길이가 짧은 순으로 정렬해서 트라이에 전화번호를 추가하면서 확인하였다.

[풀이 과정]

1. 테스트 케이스별로 전화번호를 입력받아 배열에 저장한 후 전화번호 길이가 짧은 순으로 정렬
2. Trie 생성하면서 일관성 여부 판단
   • Trie 생성시, 문자열에 대해 문자(Character)하나씩 노드를 생성하면서 자식 노드를 생성하는데,
     • 이때, 현재 탐색중인 문자(노드)의 자식 노드로 이미 해당 문자가 있고, 그 문자의 endOfWord가 true(=단어의 끝)이면 일관성 없는 목록으로 판단
     • 예시) 911에 대해 이미 "9"→"1"→"1"(endOfWord) 로 생성되어있는 상태에서, 911234에 대해 Trie 생성을 하면 "9"→"1"→"1"에서 마지막 "1"에 endOfWord가 true이므로 일관성이 없다고 판단
3. 테스트 케이스별로 일관성 여부 결과를 담은 배열을 순회하면서 true인 경우 YES, false인 경우 NO를 출력

정답 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int t = Integer.parseInt(st.nextToken());

        boolean[] answers = new boolean[t];
        for (int i=0; i<t; i++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());

            // 한번에 다 받은 후에 길이가 짧은 순으로 정렬
            String[] numbers = new String[n];
            for (int j=0; j<n; j++) {
                st = new StringTokenizer(br.readLine());
                numbers[j] = st.nextToken();
            }
            Arrays.sort(numbers, (o1, o2) -> o1.length() - o2.length());

            // Trie 생성
            // Leaf 노드가 아닌데 endOfWord가 되면, 일관성 없는 목록
            Trie trie = new Trie();
            boolean flag = true;
            for (String number: numbers) {
                // 일관성 없는 목록으로 판단되면 해당 테스트 케이스 반복 종료
                if (flag) flag = trie.insert(number);
            }
            answers[i] = flag;
        }
        // 결과 출력
        for (boolean answer: answers) {
            if (answer) System.out.println("YES");
            else System.out.println("NO");
        }
    }
    public static class Node {
        public HashMap<Character, Node> childNode = new HashMap<>(); // 자식 노드
        public boolean endOfWord = false;
    }
    public static class Trie {
        private Node rootNode;
        public Trie() {
        	rootNode = new Node();
        }
        public boolean insert(String number) {
            Node node = this.rootNode;
            
            for (int i=0; i<number.length(); i++) {
                // 자식 노드에 문자가 있고, 그 자식 노드가 단어의 끝(endOfWord)이면 일관성 없음
                if (node.childNode.containsKey(number.charAt(i))
                    && node.childNode.get(number.charAt(i)).endOfWord) {
                    return false;
                }

                // 자식 노드에 있는 문자라면 자식 노드를 가져오고, 자식 노드에 없다면 새로 생성
                // computeIfAbsent: Map에 Key가 없다면 Value를 새로 만들어줌
                node = node.childNode.computeIfAbsent(number.charAt(i), key -> new Node());
            }
            node.endOfWord = true; // 번호의 문자를 모두 순회하면 마지막 노드는 리프 노드
            return true;
        }
    }
}

문제 링크

https://www.acmicpc.net/problem/22866

문제 설명

일직선으로 다양한 높이의 건물이 총 N개가 존재한다. 각 건물 옥상에서 양 옆에 존재하는 건물의 옆을 몇 개 볼 수 있는지 궁금해졌다.

i번째 건물 기준으로 i - 1, i - 2, ..., 1번째 건물은 왼쪽에, i + 1, i + 2, ..., N번째 건물은 오른쪽에 있다. 각 건물 사이의 거리는 다 동일하다.

현재 있는 건물의 높이가 L이라고 가정하면 높이가 L보다 큰 곳의 건물만 볼 수 있다. 바라보는 방향으로 높이가 L인 건물 뒤에 높이가 L이하인 건물이 있다면 가려져서 보이지 않는다.

각 건물에서 볼 수 있는 건물들이 어떤것이 있는지 구해보자.

입력

첫번째 줄에 건물의 개수 N이 주어진다. 두번째 줄에는 N개의 건물 높이가 공백으로 구분되어 주어진다.

출력

i(1 ≤ i ≤ N)번째 건물에서 볼 수 있는 건물의 개수를 출력한다.

만약 볼 수 있는 건물의 개수가 1개 이상이라면 i번째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ L ≤ 100,000

입출력 예

문제 풀이

[고려사항]

건물의 개수(N)의 최대가 100,000(10만) 이므로 시간 복잡도를 고려해서 구현해야한다.

모든 건물을 하나씩 전부 비교하면 O(N^2)이 나와서 시간이 초과되기 때문이다.

[알고리즘, 구현방법]

Stack을 이용해서 문제를 풀어야 시간 초과가 발생하지 않는다.

✅ 정답

건물을 왼쪽에서 오른쪽으로 한번, 오른쪽에서 왼쪽으로 한번씩 순회하면서 각 건물에서 보이는 건물 번호를 저장한다.

이때, 스택 자료구조를 이용해서 스택의 최상위(top)에는 항상 가장 높은 건물 높이를 저장한다.

건물의 양방향을 순회할때, 현재 건물이 스택의 최상위에 있는 건물의 높이보다 크거나 같으면 스택 요소를 제거한다.

즉, 현재 건물이 스택의 최상위 높이보다 낮을때까지 스택 요소를 제거하여 스택의 최상위에는 항상 가장 높은 건물의 높이가 유지되게끔 하는 것이다.

*이러한 자료구조는 모노톤 스택의 종류 중 하나인 단조 감조 스택이다. 

[풀이 과정]

1. 왼쪽 → 오른쪽: 왼쪽에서 볼 수 있는 건물 수와 가장 가까운 건물 번호를 확인
   
   • 단조 감조 스택으로 구현: 스택의 요소들이 내림차순으로 정렬(스택의 맨 아래에서 최상위 방향)
   • 스택이 비어있지 않고, 스택에 현재 건물보다 작거나 같은 높이가 있다면 제거 (= 현재 건물이 스택의 최상위 높이보다 낮을때까지 스택 요소 제거
   • 현재 건물에서 보이는 건물의 개수 = 스택 사이즈(stack.size()) 
   • 스택이 비어있지 않다면(=보이는 건물이 1개 이상이라면), 가까운 건물(nearest[i])에 저장 
2. 오른쪽 → 왼쪽: 오른쪽에서 볼 수 있는 건물 수와 가장 가까운 건물 번호를 확인
   • 왼쪽 → 오른쪽과 기본 구현사항은 동일
   • 현재 건물에서 보이는 건물의 개수에 스택 사이즈 누적합
   • 스택이 비어있지 않고 && (현재 건물의 가까운 건물(nearest)이 이미 값이 없거나 || 오른쪽에서 보이는 건물의 거리가 왼쪽에서 보이는 건물의 거리보다 작다면), 가까운 건물 정보 저장(nearest[i])
3. 각 건물별로 보이는 건물 수와 가장 가까운 건물 번호 출력
   • 이때, 건물 수에 따라 분기태워서 System.out.prinln으로 바로 출력하는 것보다 StringBuilder로 문자열을 만들어서 한번에 출력하는게 성능이 훨씬 향상됨
     • 약 1,000ms 차이 발생 확인

X 1차 생각

이 문제는 시간이 오래걸린 문제인데, 처음에는 Stack이랑 Queue를 사용해서 오른쪽에 있는 건물은 Queue에 넣고 하나씩 확인, 왼쪽에 있는 건물은 Stack에 넣고 하나씩 확인했다. 이렇게 하면 모든 건물이 양쪽을 모두 확인하는 방식이 되어서 O(N^2)이 나와 시간이 초과된다. 

다른 포스팅을 참고해서 모노톤 스택이라는 자료구조를 알게되어서, 모노톤 스택에 대해 공부한 다음에 이 문제를 풀었다. 모노톤 스택은 블로그에 정리해두었다.

https://coding-vvon.tistory.com/entry/algorithm-stack-1

정답 코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        // 건물 번호는 1부터 시작하므로, n+1로 사이즈 할당
        int[] heights = new int[n+1];
        int[] visibleCnt = new int[n+1];
        int[] nearest = new int[n+1];
        // 초기화
        st = new StringTokenizer(br.readLine(), " ");
        for (int i=1; i<=n; i++) {
        	heights[i] = Integer.parseInt(st.nextToken());
        	nearest[i] = -1;
        }

        Deque<Integer> stack = new ArrayDeque<>();
        // 왼쪽에서 볼 수 있는 건물 수와 가장 가까운 건물 번호
        for (int i=1; i<=n; i++) {
        	// 현재 건물보다 작거나 같은 건물은 제외 = 스택의 최상위 요소보다 클 때까지 기존 요소를 제거
        	// 최상위 값은 항상 작은 값이 들어감 (단조 감소 스택)
        	while (!stack.isEmpty() && heights[stack.peek()] <= heights[i]) {
        		stack.pop();
        	}
        	visibleCnt[i] = stack.size();
        	
        	if (!stack.isEmpty()) { // 보이는 건물이 1개 이상인 경우
        		nearest[i] = stack.peek();
        	}
        	stack.push(i);
        }
        
        // 오른쪽에서 볼 수 있는 건물 수와 가장 가까운 건물 번호
        stack.clear();
        for (int i=n; i>0; i--) { 
        	while (!stack.isEmpty() && heights[stack.peek()] <= heights[i]) {
        		stack.pop();
        	}
        	visibleCnt[i] += stack.size(); // 보이는 건물 개수 갱신
        	
        	// 보이는 건물이 할당이 되어있거나, 오른쪽에서 보이는 건물이 더 가까운 경우, 가까운 건물 갱신
        	if (!stack.isEmpty() && (nearest[i] == -1 || stack.peek() - i < i - nearest[i])) {
        		nearest[i] = stack.peek();
        	}
        	stack.push(i);
        }

        // 분기태워서 System.out.println 하는것보다 StringBuilder로 하는게 성능이 훨씬 향상됨
        StringBuilder sb = new StringBuilder();
        for (int i=1; i<=n; i++) {
        	sb.append(visibleCnt[i]);
        	if (visibleCnt[i] > 0) sb.append(" ").append(nearest[i]);
        	sb.append("\n");
        }
        
        System.out.println(sb);
	}
}

📌요약

윈도우 함수 중 하나인 순위 함수를 사용하면 결과 집합의 각 행에 순위를 할당할 수 있습니다.

1. RANK() 함수

[MySQL Tutorial]
RANK() 함수는 결과 집합의 파티션 내 각 행에 순위를 할당합니다.
행의 순위는 1에 그 앞에 오는 순위 수를 더한 값으로 지정됩니다.

[Oracle Tutorial]
RANK() 함수는 각 집합에서 값의 순위를 계산하는 분석 함수입니다.
RANK() 함수는 동일한 값을 가진 행에 대해 동일한 순위를 반환합니다. 동률 순위에 동률 행 수를 더해 다음 순위를 계산합니다. 따라서 순위는 연속된 숫자가 아닐 수도 있습니다.
RANK() 함수는 상위 N 및 하위 N 쿼리에 유용합니다.

RANK() 함수는 윈도우 함수 중 그룹 내 순위 함수로, 특정 윈도우(부분)내에서 순위를 할당하는 데 사용합니다.

동일한 값을 가진 행에 대해 동일한 순위를 부여하고 그 다음 순위는 동일 순위를 가진 행 수만큼의 시퀀스 간격이 생깁니다.

예를 들어 3위가 3명이라면, 1,2,3,3,3,6,7,8, ... 이렇게 순위가 매겨집니다.

RANK() 문법

MySQL과 Oracle의 RANK() 함수 문법은 각각 아래와 같습니다.

MySQL 

RANK() OVER (
	PARTITION BY <expression>[{,<expression>...}]
	ORDER BY <expression> [ASC|DESC], [{,<expression>...}]
)

Oracle

RANK() OVER ([query_partition_clause] order_by_clause)

• PARTITION BY | query_partition_clause : 결과 집합을 파티션으로 나눕니다.
  • 옵션 값이며, 생략할 경우 조회 결과의 모든 행을 하나의 파티션으로 취급합니다.
• ORDER BY | order_by_clause : 하나 이상의 열이나 표현식을 기준으로 파티션 내의 행을 정렬합니다.
  • 필수 값이며, 함수가 적용되는 각 파티션의 행의 논리적인 정렬 순서를 결정합니다.

2. DENSE_RANK() 함수

[MySQL Tutorial]
DENSE_RANK() 함수는 순위 값에 차이 없이 파티션 또는 결과 집합 내의 각 행에 순위를 할당하는 윈도우 함수입니다.
행의 순위는 행 앞에 오는 고유한 순위 값에서 1씩 증가합니다.

[Oracle Tutorial]
DENSE_RANK() 함수는 정렬된 행 집합에서 행의 순위를 계산하는 분석 함수입니다.
RANK() 함수와 달리 DENSE_RANK() 함수는 순위 값을 연속된 정수로 할당합니다. 동률인 경우에는 순위를 건너뛰지 않습니다.
순위 기준 값이 동일한 행에는 동일한 순위 값이 적용됩니다. 

DENSE_RANK() 함수는 RANK() 함수와 동일하게 동일한 값을 가진 행에 대해 동일한 순위를 부여하지만 그 다음에 나오는 행에는 순위를 건너뛰지 않고 이어서 순위를 부여합니다.

예를 들어 3위가 3명이라면, 1,2,3,3,3,4,5,6, ... 이렇게 순위가 매겨집니다.

DENSE_RANK() 문법

MySQL과 Oracle의 DENSE_RANK() 함수 문법은 각각 아래와 같습니다.

MySQL 

DENSE_RANK() OVER (
    PARTITION BY partition_expression
    ORDER BY sort_expression [ASC|DESC]
)

Oracle

DENSE_RANK( ) OVER([ query_partition_clause ] order_by_clause)

PARTITION BY | query_partition_clause 과 ORDER BY | order_by_clause는 RANK() 함수에서의 설명과 같습니다.

DENSE_RANK()는 파티션에 동일한 순위 값을 가진 두 개 이상의 행이 있는 경우, 각 행에 동일 순위가 부여되고, RANK()함수와는 달리 항상 연속된 순위 값을 할당 합니다. (동일 순위가 있다하더라도)

3. ROW_NUMBER() 함수

[MySQL Tutorial]
ROW_NUMBER() 함수는 결과 집합의 각 행에 일련 번호를 할당하는 윈도우 함수 혹은 분석 함수입니다.
첫번째 숫자는 1로 시작합니다.

[Oracle Tutorial]
ROW_NUMBER() 함수는 적용되는 각 행(파티션의 각 행 또는 결과 집합의 각 행)에 순차적으로 고유한 정수를 할당하는 분석 함수입니다.

ROW_NUMBER() 함수는 결과 집합 내의 각 행에 고유 번호를 할당합니다.

RANK()나 DENSE_RANK() 함수보다 매우 간단합니다.

ROW_NUMBER() 함수는 각 행에 순위를 부여할 때 동일한 값이 있어도 이를 무시하고 연속적인 순위를 부여합니다.

예를 들어 3위가 3명이라해도, 1,2,3,4,5,6, ... 이렇게 순위가 매겨집니다.

ROW_NUMBER() 문법

MySQL과 Oracle의 RANK() 함수 문법은 각각 아래와 같습니다.

MySQL 

ROW_NUMBER() OVER (
    PARTITION BY <expression>,[{,<expression>}...]
    ORDER BY <expression> [ASC|DESC],[{,<expression>}...]
)

Oracle

ROW_NUMBER() OVER (
   [query_partition_clause] 
   order_by_clause
)

PARTITION BY | query_partition_clause 과 ORDER BY | order_by_clause는 RANK() 함수에서의 설명과 같습니다.

4. RANK() vs DENSE_RANK() vs ROW_NUMBER()

지금까지 알아본 3가지 윈도우 함수인 RANK(), DENSE_RANK(), ROW_NUMBER()의 실제 결과값의 차이를 확인해보겠습니다.

학생 정보가 담긴 테이블을 간단하게 만들고, 학생별 평점으로 각 순위 함수의 차이를 확인해보겠습니다.

CREATE TABLE `students` (
  `student_id` int NOT NULL,
  `first_name` varchar(50) DEFAULT NULL,
  `last_name` varchar(50) DEFAULT NULL,
  `major` varchar(100) DEFAULT NULL,
  `gpa` decimal(3,2) DEFAULT NULL, // 평점
  PRIMARY KEY (`student_id`)
)

적당한 데이터를 여러개 INSERT 한 후 아래 쿼리를 실행시켜 보겠습니다.

SELECT student_id , first_name , gpa 
		, RANK() OVER (ORDER BY gpa DESC) AS 'RANK'
		, DENSE_RANK () OVER (ORDER BY gpa DESC) AS 'DENSE_RANK'
		, ROW_NUMBER() OVER (ORDER BY gpa DESC, first_name ASC) AS 'ROW_NUM'
FROM students;

실행시킨 결과는 아래와 같습니다.

3,4번 행을 보면, 3번 행의 지우와 4번 행의 소민이의 순위 값이 각 함수별로 다른 것을 확인할 수 있습니다.

그리고 각 함수별로 순위도 다르게 매겨지는 것을 알 수 있습니다.

• RANK: 1 ⭢ 2 ⭢ 4 ⭢ 6 ⭢ 8 ⭢ 10
• DENSE_RANK: 1 ⭢ 2 ⭢ 3 ⭢ 4 ⭢ 5 ⭢ 6
• ROW_NUM: 1 ⭢ 2 ⭢ 3 ⭢ 4 ⭢ 5 ⭢ 6 ⭢ 7 ⭢ 8 ⭢ 9 ⭢ 10

5. PARTITION BY  문법

추가로 세가지 함수에서 모두 옵션 값으로 사용되는 파티션 구문에 대한 사용법을 알아보겠습니다.

PARTITION BY는 그룹 내 순위 및 그룹별 집계를 구할 때 사용합니다.

SELECT student_id , major , gpa 
	,RANK() OVER (PARTITION BY major ORDER BY gpa DESC) AS 'PARTITION'
FROM STUDENTS;

이 쿼리는 학생들의 전공(major)별로 학생들의 평점(gpa)순위를 매깁니다.

• PARTITION BY major ORDER BY gpa DESC: major 컬럼이 같은 행을 그룹으로 묶어서, 그룹 내 gpa 컬럼의 순위를 내림차순(DESC)으로 정렬

위 쿼리를 실행한 결과는 아래와 같습니다.

마치며,

윈도우 함수 중 하나인 순위 함수에 대해 알아보았습니다.

코딩테스트를 하면서 RANK() 함수를 활용해야하는 쿼리를 제대로 작성하지 못해 다시 공부하면서 정리하니 전에 공부했던 내용이 다시 생각나기도 하고 새롭게 다시 배우기도 했습니다.

관련한 다른 함수들도 많이 있으니, 다음에는 이외 함수들도 정리하는 시간을 가져보아야겠습니다 :)

참고 링크

문제 링크

https://www.acmicpc.net/problem/12865

문제 설명

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 사치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다.

두번째 줄부터  N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

입출력 예

문제 풀이

[고려사항]

1. 시간 복잡도

물품의 조합별 최대 가치 누적값을 구해야하는데, 조합으로 하면 물품 개수(N)가 최대 100개이므로 n개 중 r개로 풀면 시간 복잡도가 O(n^r)이 되기때문에 그냥 조합으로 풀면 안된다.

2. dp 배열의 구성

결론부터 말하면 이 문제는 DP로 구현했는데, 조건을 2개를 두어 다차원 DP로 구현했다.

이때 행과 열을 각각 어떤걸로 정하냐에 따라 시간차이가 (미미하지만) 나길래 기록해둔다.

자세한건 아래 구현방법에 추가하였으니 궁금하다면 참고하면 되겠다!

[알고리즘, 구현방법]

기본적인 개념은 조합으로 생각하면서 최적화시키는 방향으로 해야할 것으로 보여, DP로 구현했다.

✅ 정답

DP로 풀어야겠다는 결론은 나왔는데, DP를 정의하기가 어려웠다.

DP 요소의 기준을 물품의 번호로 두거나(i번째 물품까지 확인했을때 최대 가치), 중량의 기준으로 두거나(i kg까지 확인했을때 최대가치) 라는 조건들을 둬도 이외 조건에 따라 값이 달라질 수 있다. 가방의 무게가 같더라도 물품 조합에 따라 최대 가치가 달라지는 등의 문제가 생긴다.

그래서 무게와 물품, 두 가지로 기준을 두어 2차원 배열의 DP로 구현했다.

행에는 물품, 열에는 배낭의 최대 무게를 두고(dp[물품][무게]), 해당 무게에 해당하는 최대 가치를 계산한다.

즉, dp[i][j] = i번째 물품까지의 배낭의 무게 j를 담았을때의 최대 가치이다.  

*편의상 0번 행, 0번 열은 쓰지 않는다.

문제 예시 1번을 조금 바꿔서 예를 들어보자.

무게가 3kg일때를 보면, 1, 2번 물품까지는 가방에 담을 무게 3kg을 초과하기 때문에 조건에 맞지않아 넣을 수 없어서 가치가 0이 된다. 3번째 물품은 3kg이라서 조건에 부합하여 해당 물품의 가치인 6을 할당한다. 

그리고 (4,3)는 4번째 물품까지 배낭에 3kg을 넣을때, 최대 가치 값을 할당해야한다.

그런데 여기서 (3,3)에서 이미 최대 3kg이 찬 상태이므로 1kg인 4번 물품을 담으면서 최대 가치값을 구하려면 현재 3kg에서 4번 물품의 무게인 1kg을 뺀 (1) 2kg일때 3번 물품까지의 합과 4번 물품의 가치를 더한 값, (2) 3kg일때의 3번 물품까지의 합을 비교해서 최댓값을 넣어야한다.

즉, dp[4][3] = max(dp[3][2] + 물품[4].value, dp[3][3]) 으로 계산해야한다.

같은 무게라 할지라도 물품 조합에 따라 최대 가치가 바뀔 수 있기 때문이다.

그렇게하면 dp[3][2] = 0 , 물품[4].value = 12 의 합은 12, dp[3][3]은 6이므로 최대값 12가 할당된다.

i번째 물품 무게를 weight, 가치를 value라 했을때 일반 점화식은 아래와 같이 나오게된다.

dp[i][j] = max(dp[i - 1][j- weight] + value , dp[i-1][j])

j번째 물품까지 i kg을 넣을 수 있을때 최대 가치 합은 (i-1)번째까지의 (j-(i번째 물품의 무게)) kg일 때의 가치 + i번째 물품의 가치 vs (i-1)번째 물품까지의 j kg의 물품의 가치 중 큰 값이다.

dp 배열을 모두 계산한 후에는 N번 물품까지의 최대 K kg 최대 가치인, dp[N][K]을 반환하면 된다.

💡 배열의 구성 방식

위 dp 배열에서 행과 열을 어떤 기준으로 잡느냐에 따라 코드를 제출했을때, 속도 차이가 있다는 것을 확인했다.

40ms정도의 차이이지만 같은 코드로 수행했는데도 배열의 행, 열 기준에 따라 속도 차이가 발생해서 한번 알아보았다.

2차원 배열은 메모리에서 저장될 때 행 우선(row-major) 방식으로 저장된다.

예를 들어 int[][] arr = new int[3][3] 배열의 해시 코드를 확인해보면 아래와 같다.

Row 0 hash code: 918221580
    arr[0][0] = 0 (hash code: 918221580)
    arr[0][1] = 1 (hash code: 918221580)
    arr[0][2] = 2 (hash code: 918221580)
Row 1 hash code: 603742814
    arr[1][0] = 3 (hash code: 603742814)
    arr[1][1] = 4 (hash code: 603742814)
    arr[1][2] = 5 (hash code: 603742814)
Row 2 hash code: 1067040082
    arr[2][0] = 6 (hash code: 1067040082)
    arr[2][1] = 7 (hash code: 1067040082)
    arr[2][2] = 8 (hash code: 1067040082)

행을 기준으로 Hash Code가 같은 것을 알 수 있다. 

메모리에 행 우선 방식으로 저장되어있기때문에 배열에 접근할 때, 행을 고정하고 열을 이동시키면서 접근하는 방식이 더 효율적이다.

이제 두 방식의 차이를 살펴보자.

1. dp[무게][물품] 으로 했을때, 200ms

for (int i = 1; i <= k; i++) { // 무게 i
    for (int j = 1; j <= n; j++) { // 물품 번호 j
        if (i >= W[j]) dp[i][j] = Math.max(dp[i-W[j]][j-1] + V[j], dp[i][j-1]);
        else dp[i][j] = dp[i][j-1];
    }
}

이 방식은 무게를 행으로 두고있고, 무게 i 가 변화할 때마다 해당 행 전체를 연속적으로 접근하지 않고 열단위로 접근한다.

dp[i][j]에 값을 할당하기 위해 i 가 1부터 k 까지 증가하면서 dp[i-W[j]][j-1]와 dp[i][j-1]을 참조하기 때문에 메모리 접근이 불연속적이다.

즉, dp[1][j], dp[2][j], ... , dp[k][j] 식으로 접근하게 된다.

2. dp[물품][무게] 으로 했을때, 160ms

for (int i = 1; i <= n; i++) { // 물품 번호 i
    for (int j = 1; j <= k; j++) { // 무게 j
        if (W[i] <= j) dp[i][j] = Math.max(dp[i-1][j-W[i]] + V[i], dp[i-1][j]);
        else dp[i][j] = dp[i-1][j];
    }
}

이 방식은 물품을 행으로 두고있고, 물품 i 가 변화할 때마다 해당 행 전체를 연속적으로 접근한다.

dp[i][j]에 값을 할당하기 위해 i 가 1부터 n까지 증가하면서 dp[i-1][j-W[i]]와 dp[i-1][j]를 참조하기 때문에 메모리 접근이 연속적이다.

즉, dp[i][1], dp[i][2], ... , dp[i][k] 식으로 접근하게 된다.

따라서 메모리 접근이 행 기준으로 이루어져서 연속적인 2번째 코드가 캐시 효율이 높아서 더 좋은 성능을 가져 빠르게 실행된다.

X 1차 생각

처음에는 각 물건들의 조합별 가치를 계산해서 최댓값을 갱신하였다.

import java.io.*;
import java.util.*;
public class Main {
    static int k;
    static boolean[] checked;
    static int max = 0;
    static List<Product> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            list.add(new Product(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        checked = new boolean[n];
        for (int i=0; i<=n; i++) {
            combination(0, n, i, 0, 0);
        }
        System.out.println(max);
    }
    public static void combination(int start, int n, int r, int w, int v) {
        if (r == 0) {
            if (w > k) return;
            max = Math.max(max, v);
            return;
        }
        for (int i=start; i<n; i++) {
            int weight = list.get(i).w;
            int value = list.get(i).v;

            if (!checked[i]) {
                checked[i] = true;
                combination(i+1, n, r-1, w + weight, v + value);
                checked[i] = false;
            }
        }
    }
}
class Product {
    int w;
    int v;
    public Product(int w, int v) {
        this.w = w;
        this.v = v;
    }
}

근데 이렇게 하니 시간 초과가 발생했다. 시간 복잡도를 계산해보니 N개중 r개를 선택하는 combination 을 수행하면 O(N^r).. n과 r은 최대 100이므로 시간 초과가 되지 않으면 이상할 정도였다..

그래서 값을 누적하면서 구현해야겠다고 생각했고, DP 로 문제를 다시 풀었다.

[풀이 과정]

1. 물품 무게와 가치를 각 배열에 저장 (W, V)
2. dp[물품][무게] 를 행을 기준으로 순회하면서 점화식으로 값 할당
   • 각 물품의 무게가 현재 무게(j)보다 작거나 같을 경우에만 최댓값 비교
   • 이외 경우엔 이전 값인 dp[i-1][j]를 할당
3. dp 배열의 마지막 값 출력

정답 코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		// 물품 무게, 가치 저장
		int[] W = new int[n+1];
		int[] V = new int[n+1];
		for (int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			W[i] = Integer.parseInt(st.nextToken());
			V[i] = Integer.parseInt(st.nextToken());
		}
		
		// DP로 최대 가치 계산
		int[][] dp = new int[n+1][k+1]; // 0번 행, 0번 열은 사용하지 않음
		for (int i=1; i<=n; i++) { // i: 물품
			for (int j=1; j<=k; j++) { // j: 무게 
				// 각 물품의 무게가 현재 무게(j)보다 작거나 같을 경우에만 최댓값 비교
				if (W[i]<=j) dp[i][j] = Math.max(dp[i-1][j-W[i]] + V[i], dp[i-1][j]);
				else dp[i][j] = dp[i-1][j];
			}
		}
		System.out.println(dp[n][k]);
	}
}

📌인터페이스와 추상클래스의 차이

자바에는 비슷한 듯 다른 인터페이스와 추상 클래스가 있다. 이 둘의 차이점을 정리해보려 한다. 

먼저, 인터페이스와 추상 클래스가 무엇인지 먼저 알아보자.

인터페이스(Interface)

인터페이스는 모든 메서드가 추상 메서드로 구성되어있고, 클래스가 구현해야할 메서드의 집합을 정의한다.

간단하게 무언가 구현해야할 내용을 정의해놓은 것이라고 생각하면 된다.

'구현해야할' 것들을 정의해놓은 것이므로 일반 클래스와 달리 메서드에 코드 블럭이 없다. 즉, 어떤 메서드의 기능을 구현해놓은 내용인 코드 블럭이 없다.

interface 인터페이스명() {
    public static final 상수명 = 값;
    public abstract void 메서드명();
}

인터페이스를 선언할 때는 접근 제어자와 함께 ① interface 키워드를 사용한다.

그리고 ② 인터페이스의 모든 메서드는 암묵적으로 public 이며, 필드(변수)는 public static final 이다.

*인터페이스 필드에 int COUNT = 3;은 public static final을 생략해도 자동으로 public static final이 적용된다.

메서드에 기능을 구현해놓지 않기 때문에, 인터페이스는 혼자서 무언갈 할 수는 없다. 인터페이스를 상속한 클래스(구현체)에서 메서드를 Override 해서 구현해야한다.

interface Computer { }
Computer C = new Computer(); // Error: Cannot instantiate the type Computer

위처럼 인터페이스가 있다고 할때, Computer 객체를 생성하려하면 에러가 발생한다. 

그리고 인터페이스는 ③ 다중 상속이 가능해서, 아래와 같이 한 클래스가 여러 인터페이스를 상속받아 구현할 수 있다.

class 클래스명 implements 인터페이스1, 인터페이스2

④ Java8 부터 인터페이스는 default 메서드와 static 메서드를 사용할 수 있다.

인터페이스의 메서드는 구현체를 가질 수 없지만, default 메서드를 사용하면 실제 구현된 형태의 메서드를 가질 수 있다. 

그리고 인터페이스에 static 메서드를 구현하면 인터페이스명.스태틱메서드명과 같이 사용하여 일반 클래스의 static 메서드를 사용하는 것과 동일하게 사용할 수 있다.

interface TestInterface {
    // default 메서드
    default void printSomething() {
    	System.out.println("default method in interface");
    }
    // static 메서드
    static int getNum() {
    	return 10;
    }
}

아래와 같이 인터페이스명.스태틱메서드명으로 사용할 수 있다.

TestInterface.printSomething();

인터페이스(Interface)를 사용하는 이유?

그렇다면 인터페이스를 왜 사용해야 하는걸까?

보통 중요 클래스를 작성하는 시점에서 클래스의 구현체가 몇 개가 될지 알 수 없으므로 인터페이스를 정의해서 인터페이스를 기준으로 메서드를 만드는 것이 효율적이기 때문이다.

당장 이 문장을 읽었을때는 무슨 소린가 싶다.

예시로 한번 다시 정리해보자.

Animal 클래스를 상속하는 Tiger, Bear 클래스가 있고, 이들을 관리하고 먹이를 주는 ZooKeeper 클래스가 있다고 해보자.

class Animal {
	String name;
	void setName(String name) {
		this.name = name;
	}
}

class Tiger extends Animal { }
class Bear extends Animal { }
class ZooKeeper {
	void feed(Tiger tiger) {
		System.out.println("feed apple to Tiger");
	}
	void feed(Bear bear) {
		System.out.println("feed banana to Bear");
	}
}

ZooKeeper는 feed() 메서드 호출시 인자의 타입에 따라 Tiger나 Bear에게 먹이를 준다.

public static void main(String[] args) {
    ZooKeeper zooKeeper = new ZooKeeper();
    Tiger tiger = new Tiger();
    Bear bear = new Bear();

    zooKeeper.feed(tiger); // feed apple to Tiger
    zooKeeper.feed(bear); // feed banana to Bear
}

근데 이때 동물들이 계속해서 늘어난다면, ZooKeeper에 해당 동물들의 타입을 매개변수로 한 feed() 메서드를 계속 계속 추가해주어야한다. 이렇게 계속 추가하게 되면 ZooKeeper 가 굉장히 복잡해질 것이다.

이럴때 인터페이스를 구현하면 훨씬 효율적으로 코드를 구성할 수 있다.

먹이를 주는 메서드 기능을 가진 인터페이스 Work를 생성해보자.

interface Work {	} // 인터페이스
class Animal { // 부모(상위) 클래스
    String name;
    void setName(String name) {
    	this.name = name;
    }
}
class Tiger extends Animal implements Work { }
class Bear extends Animal implements Work { }

그리고 Tiger, Bear 클래스에서  인터페이스 Work를 상속한다. 

*인터페이스 상속시 키워드는 implements

이렇게하면 ZooKeeper 클래스에 인터페이스 Work 타입을 매개변수로 받아서 먹이를 주는 기능인 feed() 메서드를 구현할 수 있다. 

class ZooKeeper {
    void feed(Work work) {
        System.out.println("feed apple to Animal");
    }
}

원래는 Tiger, Bear 타입에 대해 각각 feed() 메서드를 구현해야했지만, 인터페이스인 Work 타입의하나의 메서드만으로도 feed() 메서드 구현이 가능하다.

실제로 Tiger, Bear 인스턴스를 feed(Work work) 메서드의 인자로 넣어서 호출하면 아래와 같은 결과가 나온다.

public static void main(String[] args) {
    ZooKeeper zooKeeper = new ZooKeeper();
    Tiger tiger = new Tiger();
    Bear bear = new Bear();

    zooKeeper.feed(tiger); // feed apple to Animal
    zooKeeper.feed(bear); // feed apple to Animal
}

이제 어떤 동물 클래스를 추가하든 ZooKeeper 클래스에 feed() 메서드를 추가할 필요가 없다.

다시 위에서 얘기했던 이유를 가져오면,

"중요 클래스를 작성하는 시점에서 클래스의 구현체가 몇 개가 될지 알 수 없으므로 인터페이스를 정의해서 인터페이스를 기준으로 메서드를 만드는 것이 효율적"

이라는 말이 조금은 이해가 될 것이다.

다만, 위 예시는 인터페이스가 왜 필요한가에 대한 부분에 대한 설명을 위한 예시로, Work 인터페이스를 상속하는 모든 클래스에서 같은 출력이 나온다. 이건 Work 인터페이스를 상속받는 하위 클래스, 즉 자식 클래스에서 별도로 메서드를 구현해서 각 동물 클래스마다 다른 결과를 나오게 할 수 있다.

*어떻게 하는건지는 이 포스팅에서는 다루지 않겠다. 추상 클래스랑 비교가 목적이므로..

추상 클래스(Abstract Class)

추상 클래스는 ① 하나 이상의 추상 메서드를 포함하며, 인터페이스의 역할도 하면서 클래스의 기능도 가지고 있는 클래스이다. 

하나 이상의 추상 메서드를 포함한다는 것은, 일반 메서드를 가질 수 있다는 의미도 내포한다.

인터페이스의 경우, 모든 메서드가 추상 메서드인 반면 추상 클래스는 미리 구현된 메서드를 가질 수 있다는 차이가 있다.

abstract class 클래스명() { // 추상 클래스
    abstract 반환타입 메서드명(); // 추상 메서드
}

추상 메서드는 인터페이스의 메서드와 마찬가지로 구현체가 없다.

즉, 추상 클래스를 상속하는 자식 클래스에서 반드시 해당 추상 메서드를 오바라이딩을해야 사용할 수 있다.

추상 메서드는 코드 블럭이 있는 구현체로 작성되지 않고, 선언부만 존재한다. 이 메서드를 자식 클래스에서 오버라이딩하여 구현해서 사용하는 것이다.

다시말해, 추상 클래스는 "내가 이 기능을 정해두지 않을테니, 나를 상속한 자식 클래스들아, 내가 정의한 기능을 구현해봐!" 라고 이야기 하는 것이다. 여기에 추가로, "단 일부는 만들어주고, 일부는 안만들어줄게" 라고 한다고 생각하면 기억하기 쉽다.

추상 클래스는 인터페이스와 마찬가지로 구현부가 없는 추상 메서드가 있기 때문에 일반 클래스와 달리  ② 단독으로 객체, 즉 인스턴스를 생성할 수 없다.

반드시 추상 클래스를 상속한 실제 클래스를 통해서만 객체를 생성할 수 있다.

(추상 클래스를 상속한 자식 클래스에서 해당 추상 클래스의 추상 메서드를 오버라이딩 해야, 자식 클래스의 인스턴스 생성 가능)

abstract class Teacher { }
Teacher t = new Teacher();  // Error: Cannot instantiate the type Teacher

그리고 추상 클래스는 인터페이스와 달리 일반 클래스처럼 ③ 인스턴스 변수, 생성자, private 메서드 등을 가질 수 있다.

즉, 추상 메서드와 일반 메서드, 객체 변수, 생성자까지 가질 수 있는 것이다.

abstract class Teacher {
	private String name; // 멤버 변수
	Teacher() {} // 생성자
    
	abstract void hello(); // 추상 메서드
	void hi() { System.out.println("안녕!"); } // 일반 메서드
}

그리고 Java에서는 클래스의 다중 상속을 막기 때문에 ④ 추상 클래스는 다중 상속을 할 수 없다.

class 클래스명 extends 추상클래스

추상 클래스(Abstract Class)를 사용하는 이유?

추상 메서드도 인터페이스와 비슷하게, 중복되거나 공통되는 부분에 대해 미리 만들어진 것을 사용하고, 이를 사용하는 쪽에서 자신에게 필요한 부분만 재정의해서 사용함으로써 생산성과 효율성이 향상되기 때문에 사용한다.

또한 추상 메서드가 포함된 클래스를 상속받는 하위(자식)클래스가 반드시 그 추상 메서드를 구현하게끔 하기 위함이다.

일반 메서드는 해당 메서드를 구현하지 않을수도 있지만, 추상 메서드가 포함된 추상 클래스를 상속받은 모든 하위(자식)클래스는 추상 메서드를 구현해야만 인스턴스를 생성할 수 있기 때문에 반드시 구현하게 된다.

인터페이스(Interface) vs 추상 클래스(Abstract Class)

그럼 이 둘의 차이가 어디에 있는지 정리해보자.

1. 사용 목적

• 인터페이스는 모든 메서드가 추상 메서드로, 인터페이스를 상속받는 클래스가 구현해야 할 메서드의 집합을 정의한다. 
• 추상 클래스는 1개 이상의 추상 메서드가 있고, 일반 메서드도 포함할 수 있기 때문에, 추상 메서드의 기능을 구현하게 하기 위해서도 있지만, 상속을 통한 공통 기능 공유하도록 하는 것에도 목적이 있다.

2. 구현

• 인터페이스는 모든 메서드가 추상 메서드이다.
• 추상 클래스는 추상 메서드와 일반 메서드를 모두 가질 수 있다.

3. 멤버 변수

• 인터페이스의 멤버 변수는 public static final이다. 즉, 인스턴스 변수를 가질 수 없다.
• 추상 클래스는 인스턴스 변수를 가질 수 있다.

4. 생성자 가능 여부

• 인터페이스는 생성자를 가질 수 없다.
• 추상 클래스는 생성자를 가질 수 있다.

5. 다중 상속 여부

• 인터페이스(키워드: implements)는 다중 상속이 가능하다.
• 추상 클래스(키워드: extends) 는 다중 상속이 불가능하다. 

마치며,

Java의 인터페이스와 추상 클래스에 대해 알아보았다.

알아보면서도 더 알아봐야할 개념들이 많아서, 이후에 하나씩 차근히 정리해보아야겠다. 

참고 포스팅 및 서적

• Do it! 점프 투 자바
• TCP School

문제 링크

문제 설명

빙하가 깨지면서 스노우타우에 떠내려 온 "죠르디"는 인생 2막을 위해 주택 건축사업에 뛰어들기로 결심하였습니다. "죠르디"는 기둥과 보를 이용하여 벽면 구조물을 자동으로 세우는 로봇을 개발할 계획인데, 그에 앞서 로봇의 동작을 시뮬레이션 할 수 있는 프로그램을 만들고 있습니다.

프로그램은 2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치할 수 있는데, 기둥과 보는 길이가 1인 선분으로 표현되며 다음과 같은 규칙을 가지고 있습니다.

• 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
• 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

단, 바닥은 벽면의 맨 아래 지면을 말합니다.

2차원 벽면은 n x n 크기 정사각 격자 형태이며, 각 격자는 1 x 1 크기입니다. 맨 처음 벽면은 비어있는 상태입니다. 기둥과 보는 격자선의 교차점에 걸치지 않고, 격자 칸의 각 변에 정확히 일치하도록 설치할 수 있습니다. 다음은 기둥과 보를 설치해 구조물을 만든 예시입니다.

예를 들어, 위 그림은 다음 순서에 따라 구조물을 만들었습니다.

1. (1,0)에서 위쪽으로 기둥을 하나 설치 후, (1,1)에서 오른쪽으로 보를 하나 만듭니다.
2. (2,1)에서 위쪽으로 기둥을 하나 설치 후, (2,2)에서 오른쪽으로 보를 하나 만듭니다.
3. (5,0)에서 위쪽으로 기둥을 하나 설치 후, (5,1)에서 위쪽으로 기둥을 하나 더 설치합니다.
4. (4,2)에서 오른쪽으로 보를 설치 후, (3,2)에서 오른쪽으로 보를 설치합니다.

만약 (4,2)에서 오른쪽으로 보를 먼저 설치하지 않고, (3,2)에서 오른쪽으로 보를 설치하려 한다면 2번 규칙에 맞지 않으므로 설치가 되지 않습니다. 기둥과 보를 삭제하는 기능도 있는데 기능과 보를 삭제한 후에 남은 기둥과 보들 또한 위 규칙을 만족해야합니다. 만약, 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시됩니다.

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

제한사항

• n은 5 이상 100 이하인 자연수입니다.
• build_frame의 세로(행) 길이는 1 이상 1,000 이하입니다.
• build_frame의 가로(열) 길이는 4입니다.
• build_frame의 원소는 [x, y, a, b]형태입니다
  • x, y는 기둥, 보를 설치 또는 삭제할 교차점의 좌표이며, [가로 좌표, 세로 좌표] 형태입니다.
  • a는 설치 또는 삭제할 구조물의 종류를 나타내며, 0은 기둥, 1은 보를 나타냅니다.
  • b는 구조물을 설치할 지, 혹은 삭제할 지를 나타내며 0은 삭제, 1은 설치를 나타냅니다.
  • 벽면을 벗어나게 기둥, 보를 설치하는 경우는 없습니다.
  • 바닥에 보를 설치 하는 경우는 없습니다.
• 구조물은 교차점 좌표를 기준으로 보는 오른쪽, 기둥은 위쪽 방향으로 설치 또는 삭제합니다.
• 구조물이 겹치도록 설치하는 경우와, 없는 구조물을 삭제하는 경우는 입력으로 주어지지 않습니다.
• 최종 구조물의 상태는 아래 규칙에 맞춰 return 해주세요.
  • return 하는 배열은 가로(열) 길이가 3인 2차원 배열로, 각 구조물의 좌표를 담고있어야 합니다.
  • return 하는 배열의 원소는 [x, y, a] 형식입니다.
  • x, y는 기둥, 보의 교차점 좌표이며, [가로 좌표, 세로 좌표] 형태입니다. 
  • 기둥, 보는 교차점 좌표를 기준으로 오른쪽, 또는 위쪽 방향으로 설치되어 있음을 나타냅니다. 
  • a는 구조물의 종류를 나타내며, 0은 기둥, 1은 보를 나타냅니다. 
  • return 하는 배열은 x좌표 기준으로 오름차순 정렬하며, x좌표가 같을 경우 y좌표 기준으로 오름차순 정렬해주세요. 
  • x, y좌표가 모두 같은 경우 기둥이 보보다 앞에 오면 됩니다.

입출력 예

문제 풀이

[고려사항]

build_frame의 최대 길이가 1,000

[알고리즘, 구현방법]

각 설치물별로 설치와 삭제조건을 따져서 이렇게 저렇게 구현했지만 틀려서, 친절한 분의 설명을 보고 구현했다.

초보자들을 위한 상세한 해설 - 전현서님

✅ 정답

하나의 좌표에 하나의 구조물만 설치할 수 있는게 아니라, 여러개의 구조물을 설치할 수 있기 때문에 하나의 배열로 이를 처리하려하면 복잡해진다. 

하나의 좌표에는 기둥, 보가 모두 설치될 수 있고, 보가 설치되는 경우 그 보가 기둥과 연결되어있는지 혹은 양옆이 보로 연결되어 있는지 여부도 따져야하므로 이 모든 정보를 하나의 배열로 판별하려면 복잡해질 것이다. 그래서 기둥 설치 배열과 보 설치 배열로 2개의 배열을 만들어서 구현한다.

우선 각 구조물은 세워지는 방향이 다르다.

• 기둥은 설치 좌표를 기준으로 위로 세워지고,
• 보는 설치 좌표를 기준으로 오른쪽으로 세워진다.

그리고 각 구조물의 설치 조건은 아래와 같다.

삭제하는 경우에도 하나씩 조건을 따져서 구현할 수 있으나, 따져야하는 게 생각보다 많아서 코딩테스트 문제를 풀때는 빨리 푸는 방식으로 하는게 나을 것 같다.

그래서 삭제의 경우, 해당 구조물을 삭제하고, 이미 설치되어 있던 구조물을 모든 다시 판별해서 위 설치 조건에 부합하는지 확인하는 방식으로 구현한다. 이미 설치되어있는 구조물을 다시 설치하면서 조건에 부합하는지 확인하여 해당 삭제가 가능한지 확인하는 방식이다. 

• 좌표가 바닥인 경우 설치 불가

위 조건을 기준으로 build_frame을 순회하면서 기둥, 보 배열에 각각 설치 및 삭제를 수행한다.

이때 문제에서 주어지는 n은 격자 크기이고 기둥과 보가 설치될 수 있는 범위는 n+1임을 주의한다.

• n = 5라면, 좌표 범위는 0 ~ 5까지이므로 배열 크기는 6이되어야 함

그리고 문제 예시에 나온 것처럼 아래쪽을 바닥으로 생각하고 구조물을 설치하려고 하다보니 y좌표를 뒤집어서 사용했는데, 문제를 다시 보다보니 이 문제는 좌표 변환 없이도 구현할 수 있는 문제였다. 

좌표 변환이랑 삭제 구현방식 때문에 애를 먹었다..

하여튼 문제에서 제시하는 좌표 (x,y)는 실제 배열로는 순서가 뒤집힌 (y,x)이니 이것만 주의해서 구현하면 된다.

X 1차 생각

build_frame을 순회하면서 기둥과 보의 설치 가능 여부를 확인해서 가능한 경우, 정답 배열에 해당 좌표와 기둥(0), 보(1) 정보 저장해서 구현했으나 실패..!

그래서 구조물 설치 정보 저장 info[][][0: 기둥 설치여부|1: 보 설치여부|2: 보만 설치된 경우(보끼리 연결된 보)]로 다시 했으나 실패..! 이 경우는 너무 코드도 복잡해지고 구현하면서도 본인도 헷갈려서 한참 들여다봤다..

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution {
    public int[][] solution(int n, int[][] build_frame) {
        /**
         * 기둥(0): 바닥, 보의 한쪽끝, 다른 기둥 위
         * 보(1): 한쪽 끝부분이 기둥 위, 양쪽 끝이 다른 보와 동시에 연결
         *      - 보와 보 사이에 있는 보라면, 양쪽 보가 모두 설치된 후에야 설치 가능
         * build_frame : [x,y(설치 좌표), (기둥 or 보), (삭제(0) or 설치(1))]
         *
         * <풀이>
         *     build_frame을 순회하면서 기둥과 보의 설치 가능 여부를 확인
         *          - 가능: 정답 배열에 해당 좌표와 기둥(0), 보(1) 정보 저장
         *          - 불가: continue
         * </풀이>
         */
        char[][] map = new char[n+1][n+1]; // 구조물 설치시 map 에 정보 저장 (구분을 위해 기둥: p, 보: b)
        int x, y, structure, command;
        int installCnt = 0; // 최종 설치된 구조물 수
        for (int[] task: build_frame) {
            x = task[0];
            y = n - task[1]; // 바닥면부터 0시작 (역순으로)
            structure = task[2]; // 0: 기둥 | 1: 보
            command = task[3]; // 0: 삭제 | 1: 설치

            if (command == 0) { // 삭제
                if (structure == 0) {
                    // 삭제하려는 기둥 위에 기둥이 있거나, 연결된 보가 있다면 무시
                    // 이때, 위에 있는 보가 끝에 있는 보가 아니라면 제거 가능
                    if (y >= 1) {
                        if (map[y-1][x] == 'b') {
                            if (x >= 2 && map[y-1][x-1] == 'b' && x < n-1 && map[y-1][x+1] =='b') {

                            } else {
                                continue;
                            }
                        } else if (map[y-1][x] == 'p') {
                            continue;
                        }
                    }
                } else{
                    // 어느쪽이든 연결된 보가 있고 && 그 보가 중간에 있는 보 일 경우 무시
                    if (x >= 2 && map[y][x-1] == 'b' && map[y][x-2] =='b') continue;
                    else if (x < n-1 && map[y][x+1] == 'b' && map[y][x+2] =='b') continue;
                }
                map[y][x] = 0; // 삭제
                installCnt--;
            } else { // 설치
                if (structure == 0) {
                    // 바닥이거나 보의 한쪽 끝이거나 다른 기둥 위여야함
                    // 보의 한쪽 끝 확인 : 설치하려는 좌표의 1칸 왼쪽에 있는 칸에 보가 있는지 확인
                    // 기둥의 위인지 확인 : 설치하려는 좌표의 1칸 아래에 있는 칸에 기둥이 있는지 확인
                    if (y == n || (x >= 1 && map[y][x-1] == 'b') || (y < n && map[y+1][x] == 'p')) {
                        map[y][x] = 'p';
                        installCnt++;
                    }
                } else {
                    // 한쪽 끝부분이 기둥 위, 양쪽 끝이 다른 보와 동시에 연결
                    //  보와 보 사이에 있는 보라면, 양쪽 보가 모두 설치된 후에야 설치 가능
                    if ((y < n && map[y+1][x] == 'p') || (y < n && x < n && map[y+1][x+1] == 'p') || // 한쪽 끝부분이 기둥 위
                            ((x < n && map[y][x+1] == 'b') && (x >= 1 && map[y][x-1] == 'b'))) {
                        map[y][x] = 'b';
                        installCnt++;
                    }
                }
            }
        }

        int[][] answer = new int[installCnt][3];
        int idx = 0;
        for (int j=0; j<n+1; j++) {
            for (int i=n; i>=0; i--) {
                if (map[i][j] == 'p') answer[idx++] = new int[]{j, n - i, 0};
                else if (map[i][j] == 'b') answer[idx++] = new int[]{j, n - i, 1};
            }
        }
        return answer;
    }
}

[풀이 과정]

1. build_frame 순회하면서 작업 수행
2. 설치인 경우, 설치 가능 여부를 canInstall 메서드를 통해 확인후 가능한 경우 설치
3. 삭제인 경우, 해당 좌표에 있는 구조물을 일단 삭제한 후, 남아있는 구조물이 모두 유효한지 확인(모든 구조물을 재설치하면서 설치 가능 여부를 확인하여서 유효성 검사)
   • 유효하지 않다면, 해당 좌표를 다시 설치
4. 기둥과 보가 설치되어있는 좌표와 구조물 정보를 리스트에 저장한 후, 정답 조건에 맞게 정렬하여 배열로 반환

정답 코드

static boolean[][] vertical;
static boolean[][] horizontal;
static int N;

public int[][] solution(int n, int[][] build_frame) {
    vertical = new boolean[n + 1][n + 1]; // 기둥
    horizontal = new boolean[n + 1][n + 1]; // 바
    N = n;

    for (int[] task : build_frame) {
        int x = task[0];
        int y = task[1];
        int structure = task[2];
        int command = task[3];

        if (command == 1) { // 설치
            if (canInstall(x, y, structure)) install(x, y, structure);
        } else { // 삭제
            uninstall(x, y, structure);
            if (!isValidStructure()) install(x, y, structure);
        }
    }


    List<int[]> answer = new ArrayList<>();
    for (int y = 0; y <= N; y++) {
        for (int x = 0; x <= N; x++) {
            if (vertical[y][x]) answer.add(new int[]{x, y, 0});
            if (horizontal[y][x]) answer.add(new int[]{x, y, 1});
        }
    }
    // x좌표 기준 오름차순 -> y좌표 기준 오름차순 -> 기둥이 보보다 우선(오름차순)
    answer.sort((o1, o2) -> {
        if (o1[0] != o2[0]) return o1[0] - o2[0];
        if (o1[1] != o2[1]) return o1[1] - o2[1];
        return o1[2] - o2[2];
    });

    return answer.toArray(new int[answer.size()][]);
}

private void install(int x, int y, int structure) {
    if (structure == 0) vertical[y][x] = true; // 기둥
    else horizontal[y][x] = true; // 보
}

private void uninstall(int x, int y, int structure) {
    if (structure == 0) vertical[y][x] = false; // 기둥
    else horizontal[y][x] = false; // 보
}

/**
 * 설치 가능여부 확인
 */
private boolean canInstall(int x, int y, int structure) {
    if (structure == 0) { // 기둥
        // 좌표가 바닥 - x좌표가 0인 경우 (y == 0)
        if (y == 0) return true;
        // 보의 한쪽 끝
        // - 설치하려는 x축 한 칸 왼쪽 좌표에 보가 설치된 경우
        if (x > 0 && horizontal[y][x - 1]) return true;
        // - 설치하려는 좌표에 보가 설치된 경우
        if (horizontal[y][x]) return true;
        // 다른 기둥 위 - 설치하려는 y축 한 칸 아래 좌표에 기둥이 설치된 경우
        if (y > 0 && vertical[y - 1][x]) return true;
    } else { // 보
        // 한쪽 끝 부분이 기둥 위
        // - 설치하려는 y축 한 칸 아래 좌표에 기둥이 설치된 경우
        if (y > 0 && vertical[y - 1][x]) return true;
        // - 설치하려는 x축 한칸 오른쪽 좌표에서 y축 한 칸 아래 좌표에 기둥이 설치된 경우
        if (y > 0 && x < N && vertical[y - 1][x + 1]) return true;
        // 양쪽 끝이 다른 보와 동시에 연결 (이 경우 양쪽 보가 모두 설치된 후에야 설치 가능)
        // - 설치하려는 x축 한칸 왼쪽과 한칸 오른쪽 좌표에 보가 설치된 경우
        if ((x < N && horizontal[y][x + 1]) && (x > 0 && horizontal[y][x - 1])) return true;
    }
    return false;
}

/**
 * 모든 구조물이 유효하게 설치되었는지 확인
 */
private boolean isValidStructure() {
    for (int y = 0; y <= N; y++) {
        for (int x = 0; x <= N; x++) {
            // 구조물이 설치 되어있지만, 유효하지 않은 경우 false
            if (vertical[y][x] && !canInstall(x, y, 0)) return false;
            if (horizontal[y][x] && !canInstall(x, y, 1)) return false;
        }
    }
    return true;
}

단축 평가(Short-circuit Evaluation)란?

단축 평가는 표현식의 결과를 결정하는데에 필요한 최소한의 연산만 수행하는 것을 의미한다.

다르게 말하면, 표현식의 결과를 결정하는 도중에 결과가 확정된 경우, 나머지 연산을 수행하지 않고 생략하는 것을 말한다.

그리고 단축 평가는 논리 연산에서 효율성을 높이는 중요한 개념이다.

💡 표현식(Expression)

표현식은 값을 계산하기 위해 사용하는 코드의 한 조각으로, 결과적으로 하나의 값을 만들어낸다.

예를 들어 10 + 3 은 13이라는 값을 만들어내는 표현식이다.

단축 평가의 적용

논리 연산자인 AND(&&)와 OR(||) 연산은 단축 평가를 수행한다.

논리곱(&&) 연산

논리곱(&&) 연산자는 두 피연산자가 모두 true 일 때, true를 반환한다.

그리고 좌항에서 우항으로 평가가 진행된다. 

(피연산자 1) && (피연산자 2) 가 있으면 피연산자 1이 먼저 평가되고, 피연산자 2가 평가되는 것이다.

피연산자 1이 true라고 해서 표현식 전체를 true로 평가할 수는 없고, 피연산자 2까지 평가를 해보아야한다.

즉, 두번째 피연산자인 피연산자 2가 논리곱 연산의 결과를 결정한다고 볼 수 있다. 

그런데 이때 피연산자 1이 false 라면, 피연산자 2의 결과와는 관계없이 논리곱 연산의 결과가 false가 된다.

논리곱(&&) 연산은 두 피연산자가 모두 true이여야하기 때문이다.

논리합(||) 연산

논리합(||) 연산자는 두 피연산자 중 하나라도 true 일 때, true를 반환한다.

논리곱 연산자와 마찬가지로 좌항에서 우항으로 평가된다.

(피연산자 1) || (피연산자 2) 가 있다고 할 때, 피연산자 1이 true라면 두번째 피연산자인 피연산자 2를 평가하지 않아도 이 표현식이 true라고 평가할 수 있다.

그런데 이때 피연산자 1이 false 라면, 피연산자 2를 평가해야지만 이 표현식의 결과를 확정할 수 있다. 

논리합 연산자는 둘 중 하나라도 true면 true를 반환하기 때문이다.

논리곱(&&) 연산자와 논리합(||) 연산자의 단축 평가

그럼 논리곱, 논리합 연산자의 단축 평가가 어떻게 이뤄지는지 알아보자.

결론을 말하자면,

논리곱(&&) 연산자는 첫번째 피연산자가 false 면, 이후 피연산자에 대해서는 평가를 하지 않고,

논리합(||) 연산자는 첫번째 피연산자가 true 면, 이후 피연산자에 대해서는 평가를 하지 않는다.

다음 예제로 자세히 알아보자.

1 == 0 : false
1 / 0 == 0 : Error

조건이 위와 같이 있다할때, 각 결과는 1 == 0 은 false, 1 / 0 == 0 은 에러가 발생한다.

그럼 두개의 피연산자로 표현식을 구성해서 논리곱 연산을 하면 어떻게 될까?

1 == 0 && 1 / 0 == 0

위 표현식에서 두번째 피연산자에 1 / 0 은 에러가 발생하므로, 에러가 발생하지 않을까하지만, 결과는 false 이다!

논리곱(&&) 연산자는 좌항부터 연산을 하고, 단축 평가를 하기 때문에 첫번째 피연산자가 false 라면, 두번째 피연산자에 대해서는 평가를 하지 않고 (결과가 확정되었기 때문) false 를 반환한다. 

두번째 피연산자에 관련된 코드는 실행하지 않으므로 Dead Code가 된다.

*Dead Code: 실행되지 않는 코드

논리합(||) 연산자도 마찬가지로 다음 예제로 살펴보자.

1 == 0 || 1 / 0 == 0

이때는 첫번째 피연산자가 false 이고, 결과가 확정되지 않았으므로 1 / 0 == 0 까지 연산을 수행하게 되어서 에러가 발생한다.

1 == 1 || 1 / 0 == 0

만약 첫번째 피연산자가 1 == 1로, 결과가 true 라면, 두번째 피연산자를 평가하지 않으므로 결과로 true가 반환된다.

논리합(||) 연산자도 좌항부터 연산을 수행하고 단축 평가를 하기 때문에 앞선 연산이 true 라면 결과가 확정되어 이후 연산을 수행하지 않는다.

마찬가지로 두번째 피연산자에 관련된 코드는 실행하지 않으므로 Dead Code가 된다.

단축 평가 규칙

단축 평가의 규칙은 아래 표와 같다.

단축 평가의 이점

단축 평가의 이점은 효율성 향상에 따른 성능 향상에 있다.

논리 연산 수행시 결과가 이미 결정된 경우 나머지 부분을 수행하지 않기 때문에 불필요한 계산을 생략하여 효율성을 높인다. 이는 특히 연산을 많이 수행하는 메서드나 I/O 작업이 포함된 경우에 이점이 커진다.

boolean result = (condition1 && condition2); // condition1이 false라면 condition2는 평가되지 않음

그리고 단축 평가는 특정 조건에서만 메서드를 호출하거나 연산을 수행하고자 할 때 유용하게 쓰인다.

if (obj != null && obj.someMethod()) {
	// obj가 null이 아닌 경우에만 obj.someMethod()가 호출	
}

또한 특정 연산을 실제로 필요한 경우에만 수행하게끔 한다.

if (condition && someMethod()) {
	// someMethod()는 condition이 true인 경우에만 호출
}

이는 배열이나 리스트 같은 자료 구조를 접근할 때 범위 체크시에도 유용하다.

if (idx < array.length && array[idx] == target) {
	// array[idx]에 안전한 접근 가능
}

마치며,

단축 평가를 모른다면 코드 구현시 의도한대로 결과가 나오지 않거나, 런타임 에러가 발생하는 등의 문제가 발생할 수 있겠다.

이번 기회를 통해 단축 평가를 잘 정리한 것 같다.

그리고 Java 카테고리로 분류하긴 했지만, 단축 평가는 대부분의 주요 프로그래밍 언어에서 지원한다고 한다.

참고 포스팅