개발옹

문제 링크

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

문제 설명

NxN 크기의 땅이 있고, 땅은 1x1 개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1x1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100) 

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

문제 풀이

[고려사항]

배열 크기는 최대가 50x50 이고, 인구 이동이 발생하는 일수는 최대 2,000번이다. 

모든 배열을 매번 접근한다고 가정했을때, 최대 50 x 50 x 2000 = 5,000,000 (5백만)번의 접근이 있을 수 있다.

* 시간 제한 2초면 자바는 ×2+1 초라서 5초내에 완료해야한다. 그리고 초당 10^7~10^8회 연산을 수행할 수 있다고 가정했을때, 최대 접근 수가 이보다 적기 때문에 정답을 위해 크게 고려하지는 않아도 될 듯 하다. 물론 아예 생각안해도 된다는건 아니지만.

[알고리즘, 구현방법]

인접 국가를 방문하면서 인구 수 차이 조건에 따라 국경선 개방 여부를 결정할 수 있으므로,  BFS 알고리즘을 사용해서 확인했다.

국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면 연합국이 되는데, 연합국은 하루에 여러개가 나올 수 있다.

그래서 연합국을 찾아 인구 이동하는 기준을 하루로 두고, 인접 국가를 탐색하는 방식으로 구현했다.

연합국을 찾아 인구 이동하는 함수인 movePeople을 반복해서, movePeople이 성공하는 경우, 인구 이동 일자를 +1 했다.

인구 이동의 성공 여부(availableFlag)는 movePeople 함수내에서 한번이라도 연합국이 만들어지면 true로 세팅하여 반환하였다.

인구 이동 함수(movePeople)에서는 인접 국가를 방문하면서 조건에 부합하면 연합국으로 묶어서 (연합국 인구 수 / 연합국 개수)명을 재분배하여 인구 이동을 구현했다. (BFS 알고리즘 사용)

상세 사항은 정답 코드의 주석을 따라가면 된다.

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[][] earth;
    static int n, l, r;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());

        // 인구수 입력
        earth = new int[n][n];
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j=0; j<n; j++) {
                earth[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 인구 이동
        int day = 0;
        while (true) {
            if (!movePeople()) break; // 인구 이동이 실패한 경우 반복문 종료
            day++; // 인구 이동 성공한 경우 일 수 증가
        }
        System.out.println(day);
    }

    public static boolean movePeople() {
        int[] dx = {0,1,0,-1};
        int[] dy = {1,0,-1,0};
        boolean[][] visited = new boolean[n][n];
        Queue<Pointer> q = new LinkedList<>();
        boolean availableFlag = false;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) { // 방문하지 않은 땅인 경우
                    q.offer(new Pointer(i, j)); // BFS Queue에 삽입
                    visited[i][j] = true;

                    // BFS Queue에 저장되어 아래 while문을 타면 하나의 연합국으로 계산
                    List<Pointer> pointers = new ArrayList<>(); // 하나의 연합국 정보를 담을 Pointer 리스트
                    int sum = earth[i][j]; // 연합의 인구수
                    int cnt = 1; // 연합을 이루고 있는 칸의 개수

                    while (!q.isEmpty()) {
                        Pointer nowPointer = q.poll();
                        pointers.add(nowPointer);

                        for (int k = 0; k < 4; k++) { // 4방향 탐색
                            int nx = nowPointer.x + dx[k];
                            int ny = nowPointer.y + dy[k];

                            if (nx >= 0 && nx < n && ny >= 0 && ny < n) { // 범위 체크
                                if (!visited[nx][ny]) { // 방문하지 않은 인접 땅인 경우
                                    int diff = Math.abs(earth[nowPointer.x][nowPointer.y] - earth[nx][ny]); // 현재 땅과 인접땅의 인구 차이 계산
                                    if (diff >= l && diff <= r) { // L명 이상 R명 이하인 경우 국경선 열림
                                        visited[nx][ny] = true; // 인접 땅 방문 표시

                                        // 연합국 처리
                                        sum += earth[nx][ny]; // 연합국 인구 수 누적
                                        cnt++; // 연합국 개수 증가

                                        q.add(new Pointer(nx, ny));
                                        pointers.add(new Pointer(nx, ny)); // 현재 연합국에 추가
                                    }
                                }
                            }
                        }
                    }
                    // 인구 이동을 할 수 없는 경우, 다음 땅에서 인접국 확인
                    if (pointers.size() == 1) continue;

                    // 현 연합국 인구 이동
                    int people = sum / cnt; // 연합에 분배될 인구 수
                    for (Pointer p : pointers) {
                        earth[p.x][p.y] = people;
                    }
                    availableFlag = true; // 인구 이동이 한번이라도 있다면 true 반환
                }
            }
        }
        return availableFlag;
    }

    public static class Pointer{
        int x;
        int y;
        public Pointer(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

Spring Boot 프로젝트를 하던중에 Security 관련 공부를 하면서 csrf 설정을 해야한다는 것을 보고, csrf가 궁금해져서 알아보게 되었습니다. 그리고 비슷한 개념인 XSS에 대해서도 살짝 맛보도록 하겠습니다.

1. CSRF(Cross-Site Request Forgery: 크로스 사이트 요청 위조)

CSRF는 Cross-Site Request Forgery의 약자로, 번역하면 사이트 간 요청 위조를 의미합니다.

CSRF는 웹사이트의 취약점을 이용하여 사용자의 의지와 무관하게 공격자가 의도한 행위(데이터 삭제, 수정, 등록 등)을 특정 웹사이트에 요청하게 하는 공격입니다.

생성된 요청이 인증된 사용자의 동의를 받았는지 확인할 수 없는 웹 애플리케이션의 CSRF 취약점을 이용하는 것입니다.

• 사용자가 인증한 세션에서 웹 애플리케이션이 정상적인 요청과 비정상적인 요청을 구분하지 못하는 점을 악용하는 공격 방식

공격자의 요청이 사용자의 요청인 것처럼 속여서 공격하는 방식이기에 '크로스 사이트 요청 위조'라는 명칭이 붙었습니다.

CSRF 공격 시나리오

CSRF 공격의 시나리오는 아래와 같습니다.

1️⃣ 사용자가 웹사이트에 접속해서 로그인하여 권한을 인증하고 세션을 생성합니다.

2️⃣ 공격자는 악성 웹사이트로 사용자를 유인합니다. 사용자가 이 링크를 클릭하면 공격자의 악성 웹사이트로 이동하게 됩니다.

3️⃣ 사용자가 악성 웹사이트에 방문하면, 해당 페이지에 포함된 스크립트나 이미지 태그가 사용자가 로그인한 웹사이트에 요청을 자동으로 전송합니다.

• 예를 들어, 은행 사이트라고 할 때, 공격자가 이미지 태그로 돈을 송금하는 요청을 보낸다고 해봅시다.

< img  src = "http://bank.com/transfer?amount=9999&toAccount=000011112222" />

해당 이미지 태그를 악성 웹사이트에 심어두면 사용자가 접속시 브라우저가 이 이미지를 로드하기 때문에, 해당 은행 웹사이트로 돈 송금 요청이 보내지게 됩니다.

4️⃣ 사용자는 웹사이트에 이미 인증을 한 상태이므로, 해당 요청은 서버에서 사용자의 정상적인 요청으로 판단하고 인증된 요청으로 처리합니다.

5️⃣ 서버는 이 악의적인 요청을 처리하여 사용자가 의도하지 않은, 공격자가 의도한 요청을 수행하게 됩니다.

• 예시로 보면, 사용자는 의도하지 않은 요청인, '000011112222' 계좌로 9,999원을 송금하게 됩니다.

CSRF 공격 사례

CSRF는 데이터 값을 변경하는 요청을 대상으로 합니다.

그러한 요청으로는 제품을 구입하거나 계정 설정, 기록을 삭제하거나 비밀번호를 변경하는 등의 요청이 있습니다. 

실제로 2008년에 옥션이 중국인 해커에게 CSRF 공격 방식으로 회원정보가 유출된 사례가 있습니다.

해커는 권한을 가지고 회사 내 작업을 하던 옥션 관리자에게 메일을 보냈고, 관리자는 이 메일을 조회했습니다. 

해커가 보낸 메일에는 태그가 들어간 코드가 포함되어 있었습니다. 

< img  src = "http://auction.com/changeUserAccount?id=admin&password=admin"  너비 = "0"  높이 = "0" >

(이미지 크기가 0이므로 관리자는 이 존재를 알지 못합니다.)

관리자가 메일을 조회하는 순간 이미지 파일을 받아오기 위해 URL이 열리게 되고, 해커가 원하는대로 관리자의 계정이 해커가 설정한 "admin"으로 변경됩니다. 이후 해커는 이 계정으로 서버 관리자 페이지에 접속해서 *백도어 프로그램을 올렸습니다.

*백도어 프로그램: 정상적인 절차를 거치지 않고도 접근을 가능하게 해주는 프로그램

백도어 프로그램을 이용해서 옥션 내부 웹 서버에 접속해 데이터베이스를 해킹했고, 회원 정보를 빼내간 것입니다.

이때 유출된 회원 정보가 1860만명이라고 합니다.

이러한 CSRF 공격에 당하게 되면 막대한 피해가 발생할 수 있습니다. 그렇기 때문에 웹 애플리케이션은 CSRF 공격을 방지하기 위해 CSRF 토큰을 통해 해당 요청이 인증된 사용자가 전송한 것이 맞는지를 확인하거나 재인증을 요구하는 등의 방식으로 CSRF 공격을 방지해야합니다.

2. CSRF 공격 방지 - Synchronizer Token Pattern

Spring에서는 CSRF 공격을 방지하기 위한 메커니즘 중 Synchronizer Token Pattern을 가장 우세하고 포괄적인 방법으로 소개하고 있습니다. Synchronizer Token Pattern은 CSRF 공격으로부터 애플리케이션을 보호하기 위해 서버와 클라이언트 간에 고유한 보안 토큰인 CSRF 토큰을 사용하는 방법입니다.

🔐 CSRF 토큰

사용자가 인증을 하더라도 CSRF 공격이 가능하기 때문에 보통 JWT만을 이용하여 사용자를 인증한다하였을때에도 공격을 받을 수 있습니다. 그래서 CSRF 토큰을 사용해서 CSRF 공격을 방지합니다.

CSRF 토큰이란, 서버에 들어온 요청이 실제 서버에서 허용한 요청이 맞는지를 확인하기 위한 토큰입니다.

CSRF 토큰은 서버에서 생성해서 클라이언트와 공유되는 인증 값입니다. 클라이언트는 서버에 요청시에 서버에서 인증해준 CSRF 토큰을 포함해서 요청해야합니다. CSRF 토큰이 없으면 서버는 요청을 거부하게 됩니다. 

CSRF 토큰을 HTML 폼에 담아서 보내는 방식이 일반적으로 사용되는 방식입니다.

1️⃣ 클라이언트는 애플리케이션 서버에 HTTP GET 요청을 통해 액세스합니다.

2️⃣ 서버는 CSRF 토큰을 생성하고 HTTP 세션에 저장합니다. 생성된 CSRF 토큰은 HTML 형식의 숨겨진 태그(hidden)를 사용하여 클라이언트와 연결됩니다.

3️⃣ 클라이언트는 HTML 폼의 버튼을 통해 애플리케이션 서버에 요청을 보냅니다. CSRF 토큰은 HTML 폼의 Hidden 필드에 포함되어 있으므로 CSRF 토큰 값이 요청 매개변수로 함께 전송됩니다. 

4️⃣ 서버는 요청 파라미터에 지정된 CSRF 토큰 값과 HTTP POST 메서드를 사용하여 액세스 할 때 HTTP 세션에 유지된 CSRF 토큰 값이 동일한지 확인합니다. 토큰 값이 일치하지 않으면 잘못된 요청으로, 오류가 발생합니다.

다시 정리하자면, 아래와 같습니다.

• 로그인한 사용자가 페이지에 접속시 서버에서는 CSRF 토큰을 생성해서 사용자 세션이 저장합니다.
• 이후 사용자가 서버에 애플맄이션의 상태를 변경하는 작업을 요청할 때 페이지에 Hidden 으로 숨어있는 CSRF 토큰 값이 서버로 전송됩니다. 
• 서버에서는 이 CSRF 값이 세션에 저장된 값과 일치하는지 확인하여 해당 요청이 정상적인 요청임을 확인할 수 있습니다. 

CSRF 토큰 유의사항

[CSRF 토큰의 위치]

• HTML 폼 제출시 hidden 필드로 포함시켜서 전송해야합니다.
• AJAX 요청을 보낼시에는 CSRF 토큰을 Custom Header 값으로 포함시키거나 JSON payload(데이터)로 전송할 수 있습니다.
• CSRF 토큰을 쿠키에 포함시켜서 전송하면 안됩니다.
  
  • CSRF 토큰은 실제 사용자가 요청한 정상적인 작업인지를 검증해야하는데, 쿠키는 브라우저에 의해 자동으로 HTTP 요청에 포함되므로, 정상적인 요청인지 검증할 수 없게 됩니다.
  • '자동 전송'이라는 기능때문에 공격자가 만든 요청이여도 쿠키가 자동으로 포함되어 서버에 전송됩니다. 이로인해 서버는 이 요청이 정상적인 요청이라고 착각하여 요청을 수행할 수도 있습니다.
  • 따라서 CSRF 토큰은 사용자가 직접 제어할 수 있는 방식으로 전송되어야 합니다.
• CSRF 토큰은 서버 로그나 URL에 노출되어서는 안됩니다.

[HTTP 요청에 따른 요구사항]

• 애플리케이션의 상태를 변경하는 요청에 대해서만 CSRF를 요청해도 괜찮습니다. (POST, PUT, PATCH, DELETE)
  • 단, 이를 위해서는 상태가 변경되지 않는(=멱등 요청)요청(GET, HEAD, OPTIONS, 및 TRACE)이 오직 읽기 전용(read-only) 작업만 수행하도록 보장해야합니다.
• HTTP GET(상태가 변경되지 않는 안전한 요청)에는 CSRF 토큰을 포함시키지 않아야합니다.
  • GET 요청은 캐시되거나 URL로 노출될 수 있기 때문에 CSRF 토큰이 유출될 수도 있습니다.
  • 토큰이 유출되면 공격자가 이 토큰을 재사용하여 CSRF 공격을 시도할 수도 있습니다.

3. CSRF vs XSS

CSRF와 XSS는 모두 웹 애플리케이션에서의 공격 유형이지만, 차이점이 있습니다.

먼저 XSS가 무엇인지 간단하게 짚고 넘어가겠습니다.

XSS(Cross-Site Scripting)

XSS는 Cross-Site Scripting의 약자로, 번역하면 사이트 간 스크립팅 입니다.

XSS 공격은 공격자가 웹 페이지에 악의적인 스크립트를 삽입하여, 사용자의 브라우저에서 실행시키는 공격입니다. 

이로인해 사용자는 의도하지 않은 동작을 수행하거나, 공격자에게 쿠키, 세션 등의 정보를 탈취 당하게 됩니다.

XSS는 SQL Injection과 함께 웹 상에서 가장 기초적인 취약점 공격 방법 중 하나입니다.

XSS 공격 대응 방안

• 중요 정보는 쿠키 대신 서버에 저장합니다.
• 정보를 암호화 합니다.
• httpOnly 옵션을 설정합니다.
  • document.cookie를 이용해 쿠키에 직접 접근하는 것을 방지
• URL Encoding이나 문자열을 치환합니다.

CSRF 와 XSS 의 차이

[공격 대상]

• CSRF 공격 대상은 "Server"이고 XSS 공격 대상은 "Client"입니다.
• CSRF는 특정 웹 사이트가 사용자의 웹 브라우저를 신뢰하는 상태를 노린 것이고, XSS는 사용자가 특정 웹 사이트를 신뢰하는 점을 노린 것입니다.

[공격 방식]

• CSRF는 공격자가 사용자의 브라우저를 속여 의도하지 않은 요청을 특정 웹사이트로 보내도록 유도합니다. 사용자의 권한을 이용해 서버에 대한 악성 공격을을 하게 하는 것입니다. 
• XSS는 공격자가 악성 스크립트를 웹페이지에 삽입하여 해당 페이지를 방문하는 사용자의 브라우저에서 스크립트가 실행되게 합니다. 스크립트는 사용자의 브라우저에서 실행되므로 사용자의 권한으로 민감한 데이터를 탈취하거나 임의의 명령을 실행할 수 있습니다.

CSRF 공격

1️⃣ 공격자자 웹 사이트에 자금 이체 요청을 위조합니다.

2️⃣ 공격자는 그 요청을 하이퍼링크(스크립트)에 삽입하여 웹 사이트에 로그인 할 사용자에게 전송합니다.

3️⃣ 사용자가 그 링크를 클릭하면, 사용자도 모르게 웹 사이트에 요청을 전송하게 됩니다.

4️⃣ 웹 사이트의 서버는 로그인 된 사용자의 요청이기 때문에 정상으로 판단하고, 사용자의 계정에서 공격자의 계정으로 자금을 이체합니다.

XSS 공격

1️⃣ 공격자가 스크립트 주입이 가능한 취약점이 있는 웹 사이트를 찾습니다.

2️⃣ 취약점을 찾아 세션 쿠키를 탈취하는 악성 스크립트를 사이트에 삽입합니다.

3️⃣ 사용자가 웹 사이트를 방문할 때마다 스크립트가 작동됩니다.

4️⃣ 작동된 스크립트를 통해 사용자의 세션 쿠키를 탈취합니다.

Reference

문제 링크

문제 설명

리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다. 

이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.

다음은 보드게임판을 나타낸 예시입니다.

...D..R
.D.G...
....D.D
D....D.
..D....

여기서 "." 은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.

위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return하는 solution 함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

제한사항

• 3 ≤ board의 길이 ≤ 100
  • 3 ≤ board의 원소의 길이 ≤ 100
  • board의 원소의 길이는 모두 동일합니다.
  • 문자열은 ".", "D", "R", "G"로만 구성되어 있으며 각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다.
  • "R"과 "G"는 한 번씩 등장합니다.

입출력 예

문제 풀이

[고려사항]

시작 위치부터 목표 위치까지 모든 경로 중 최소 움직임을 찾아야한다. 

board의 최대 크기는 100 * 100(10,000)이므로, 모든 가능한 경로를 탐색하는 방식으로 구현한다면 시간을 초과한다.

그래서 최단 거리를 찾는 알고리즘으로 BFS를 이용해서 구현한다.

BFS로 구현할 경우에는, 모든 노드를 4방향으로 방문하기 때문에 최악의 경우라도, O(10,000)이 된다.

[알고리즘, 구현방법]

최단 경로를 찾는 문제이므로 BFS를 이용해서 구현했다.

여기서 말의 움직임은 장애물(D)이나 보드의 맨 끝에 부딪힐 때까지 미끄러지는 것이다. 

일반적인 BFS와 다른점은 이동하는 칸의 개수가 한 칸이 아니라, 장애물이나 벽에 부딪힐 때까지 최대한 갈 수 있는 n칸을 이동한다는 것이다.

즉, 상하좌우의 방향 중 한 칸만 움직이는것이 아니라 특정 방향으로 최대한 갈 수 있는 칸을 구해야한다.

그래서 BFS 방문 배열을 boolean이 아니라 int 로 선언해서 해당 지점까지의 이동 횟수를 저장했다.

[풀이 과정]

*자세한건 코드내에 주석을 확인하면서 따라가주세요!

1. 시작 위치 찾기(R)

2. 시작 위치를 Queue에 저장하고 BFS 수행

• 4방향에 대해 BFS 수행
• 한 방향에 대해 최대한 갈 수 있는 만큼 이동
• 벽이나 장애물에 부딪힌 경우, 벽이나 장애물을 부딪히기 전 좌표로 돌아와서, 해당 지점까지의 이동 횟수 저장하고 Queue에 저장하여 해당 지점부터 탐색
• 현재 지점이 목표 위치(G)라면 이동 횟수 answer에 저장하고 Break;

정답 코드

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public int solution(String[] board) {
        int row = board.length;
        int col = board[0].length();
        int[][] cnt = new int[row][col];

        // 1. 시작 위치(R) 찾기
        Queue<Point> q = new LinkedList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i].charAt(j) == 'R') {
                    q.add(new Point(i, j));
                    cnt[i][j] = 1;
                    break;
                }
            }
        }

        // 2. BFS 탐색
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        int answer = -1; // 목표위치에 도달할 수 없다면 -1을 return
        while (!q.isEmpty()) {
            Point current = q.poll();
            // 현재 지점이 목표 위치인지
            if (board[current.x].charAt(current.y) == 'G') {
                answer = cnt[current.x][current.y] - 1; // 시작 위치를 1로 초기화 했으므로, 이동 횟수는 -1
                break;
            }
            // 4방향에 대해 BFS를 수행
            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                // 해당 방향으로 최대한 이동
                while (true) {
                    if ((nx >= 0 && nx < row && ny >= 0 && ny < col) && board[nx].charAt(ny) != 'D') {
                        nx += dx[i];
                        ny += dy[i];
                    } else { // 벽이나 장애물에 부딪힌 경우
                        nx -= dx[i];
                        ny -= dy[i];
                        break;
                    }
                }
                // 최대한 움직인 지점을 방문한 적이 없으면, 해당 지점에서 탐색
                if (cnt[nx][ny] == 0) {
                    q.add(new Point(nx, ny));
                    cnt[nx][ny] = cnt[current.x][current.y] + 1; // 현재 탐색을 시작한 위치에서 이동 횟수 +1
                }
            }
        }
        return answer;
    }

    public class Point {
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

문제 링크

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

(자세한 예시는 문제 링크에서 확인요망)

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
  • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
  • land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.
  • land[i][j]는 0 또는 1입니다.
  • land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.
• 정확성 테스트 케이스 제한사항
  • 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100
    • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 100
• 효율성 테스트 케이스 제한사항: 주어진 조건 외 추가 제한사항 없습니다.

입출력 예

문제 풀이

[고려사항]

n, m은 최대 500으로, 땅을 최대 500 * 500이다. 최대 250,000(25만)개의 좌표를 매번 순회한다는 등의 계산으로는 시간이 초과할 수 있기에 최대한 효율적인 방식으로 풀어야한다.

[알고리즘, 구현방법]

이 문제는 석유 덩어리를 시추관이 통과하면 석유량에 해당 석유 덩어리의 크기가 누적되고, 그 중 가장 많은 양의 석유를 반환해야한다. 그렇기때문에 일단 1)석유 덩어리를 구하고 2)시추관을 열을 기준으로 땅에 꽂았을때 열 별로 나오는 석유량을 계산 해야한다.

1)석유 덩어리 구하기 : BFS

석유가 있는 땅(land[i][j] = 1)에서 석유 덩어리들을 식별하고, 각 덩어리를 객체로 만들어 리스트에 저장했다. 이 덩어리들을 모두 식별해야만 석유 시추 시 정확한 석유량을 계산할 수 있기때문이다. 

[BFS(너비 우선 탐색)를 이용한 석유 덩어리 탐색]

석유 덩어리는 BFS 를 이용해서 탐색했다. 

먼저, land를 끝까지 순회하면서, 석유인(=1) 좌표를 발견하면 새로운 석유 덩어리의 시작이라고 판단한다.

BFS를 이용해서 이 시작이 되는 좌표와 연결된 모든 1을 탐색하고, 이를 하나의석유 덩어리로 묶어서 리스트에 저장했다 .

이렇게 해서 모든 좌표를 순회하면, land 배열에 존재하는 모든 석유 덩어리들을 식별할 수 있다.

2)가장 많은 석유를 뽑을 수 있는 시추관 찾기

처음에는 land를 다시 순회하면서 석유가 있는 땅(=1)일 때 분기 처리를 통해 석유량을 계산하는 방법을 생각했다. 그런데 이 방법은 이미 한 번 석유 덩어리를 찾아 순회한 이후, 또다시 땅 전체를 순회해야 하므로 비효율적이다. 땅 전체를 다시 순회하는 것은 시간과 자원의 낭비로 이어지기 때문이다. 

땅 전체를 다시 순회하는 대신, 이미 식별하고 저장해둔 석유 덩어리 정보를 활용하여 석유량을 계산하는 방법으로 계산했다.

이전에 저장해둔 석유 덩어리 객체들에 포함된 좌표들을 활용해서, 각 석유 덩어리의 좌표 중에서 열 값을 기준으로 시추관 별로 뽑을 수 있는 석유량을 계산했다.

이 방법을 통해서 전체 땅을 다시 순회하지 않고, 이미 탐색한 석유 덩어리 좌표만 순회하여서 석유량을 계산할 수 있게된다. 어차피 구해야하는 것은 특정 열에 속한 석유 덩어리 정보이기 때문에, 이를 직접 활용하는 것이 효율적이다. 

[풀이 과정]

1. 석유 덩어리 구하기 (BFS)

• 땅 배열(land)을 전체 탐색
• 방문한적 없는 좌표이고(좌표 방문 여부 배열 (visited[i][j] = false), 석유가 있는 땅(land[i][j] = 1)이라면 주변 탐색 시작
  
  • Queue에서 좌표를 하나씩 꺼내면서 상하좌우로 인접한 좌표를 확인하여 방문한적 없고 석유가 있는 땅이면 Queue에 추가
  • 이때 석유 덩어리에 포함되는 좌표들이 Queue에 추가되고, 이 좌표들은 동시에 해당 석유 덩어리의 좌표 리스트(pointList)에 추가
• BFS 탐색이 끝나면, 해당 석유 덩어리의 좌표 리스트인 pointList를 석유 덩어리 객체를 담은 리스트(oils)에 저장

2. 가장 많은 석유를 뽑을 수 있는 시추관 찾기

• 저장된 석유 덩어리 리스트(oils)를 순회하며 각 석유 덩어리의 좌표를 확인
• 좌표의 열 값을 기준으로 해당 열에서 시추할 수 있는 석유량 계산
  • 열에 대한 시추관 정보(Drill) 객체를 생성해서 시추할 수 있는 석유량을 누적
  • 특정 열에 있는 석유 덩어리가 아직 누적되지 않았다면, 즉, 아직 해당 열에 해당 석유 덩어리를 계산한 적 없다면, 해당 석유 덩어리의 크기(좌표 리스트의 크기)를 누적합에 더하고, 해당 석유 덩어리를 방문처리한다.

3. 열마다 시추할 수 있는 석유량을 저장한 리스트(drils)를 순회하여 최댓값 찾아서 반환

정답 코드

import java.util.*;
public class Solution { 
	public int solution(int[][] land) {
        int n = land.length; // 세로 길이
        int m = land[0].length; // 가로 길이

        boolean[][] visited = new boolean[n][m];
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        // 석유 덩어리 구하기
        Queue<Point> queue = new LinkedList<>();
        List<Oil> oils = new ArrayList<>();
        // BFS 탐색
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && land[i][j] == 1) { // 방문한적 없고, 석유가 있는 땅인 경우
                    visited[i][j] = true;

                    List<Point> pointList = new ArrayList<>(); // 현재 석유 덩어리의 좌표 리스트
                    pointList.add(new Point(i,j));
                    queue.offer(new Point(i,j));

                    while (!queue.isEmpty()) {
                        Point point = queue.poll();

                        for (int k = 0; k < 4; k++) {
                            int nx = point.x + dx[k];
                            int ny = point.y + dy[k];

                            if(nx >= 0 && nx < n && ny >= 0 && ny < m) {
                                if (!visited[nx][ny] && land[nx][ny] == 1) {
                                    visited[nx][ny] = true;
                                    queue.offer(new Point(nx, ny));
                                    pointList.add(new Point(nx, ny));
                                }
                            }
                        }
                    }
                    oils.add(new Oil(pointList)); // 석유 덩어리 리스트에 현재 석유 덩어리 정보 저장
                }
            }
        }

        // 가장 많은 석유를 뽑을 수 있는 시추관 찾기
        Drill[] drills = new Drill[m]; // 열 개수(=가로 길이)만큼 할당
        int oilCnt = oils.size();
        // 석유 덩어리 정보를 저장한 List를 순회하면서 해당 포인트의 열을 기준으로 석유 덩어리 사이즈 계산
        for (int o = 0; o < oilCnt; o++) {
            for (Point point : oils.get(o).pointList) {
                int y = point.y;
                // 아직 생성한적 없다면 석유 덩어리 개수를 매개변수로 넣어서 생성
                if (drills[y] == null) {
                    drills[y] = new Drill(oilCnt);
                }

                if (!drills[y].visitedOil[o]) { // 현재 석유 덩어리가 해당 좌표 열에 아직 누적합 되지 않은 경우
                    drills[y].visitedOil[o] = true; // 방문한 석유 덩어리니까 true 할당
                    drills[y].addOilSum(oils.get(o).pointList.size()); // 현재 석유 덩어리의 크기 누적
                }
            }
        }

        // Max 석유량 찾기
        int max = 0;
        for (Drill drill: drills) {
            // 석유가 없는 열이라면 drill이 null 일 수도 있으므로 null 검증
            if (drill != null && drill.oilSum > max) max = drill.oilSum;
        }
        return max;
    }

    public class Point {
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public class Oil {
        List<Point> pointList;

        public Oil(List<Point> pointList) {
            this.pointList = pointList;
        }
    }

    public class Drill {
        boolean[] visitedOil;
        int oilSum = 0;

        public Drill(int oilCnt) {
            this.visitedOil = new boolean[oilCnt];
        }
        public void addOilSum(int oilSize) {
            this.oilSum += oilSize;
        }
    }
}

문제 링크

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

문제 설명

KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.

탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.

입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

문제 풀이

[고려사항]

탑의 개수(N)는 최대 500,000 (50만)개 이고 시간 제한이 1.5초이므로 전체 탐색을 하면 자신을 제외한 모든 건물을 탐색해야하므로 O(N(N-1)) = O(N^2) 가 발생해서 시간 초과하여 실패할 것이다. 

[알고리즘, 구현방법]

이 문제는 한 방향만 고려하면 되고, 가장 먼저 만나는 건물 번호를 구하면 되므로, Stack을 이용해서 Stack의 최상단 값이 현재 탐색중인 건물의 높이보다 높은 값이 나올 때까지 값을 제거하면서 계산하면 된다.

입력된 탑이 6 9 5 7 4 일때, 레이저는 왼쪽 방향으로 쏘기때문에 입력되는 값의 반대 방향으로 본인보다 높은 건물을 찾아야한다.

그리고 가장 먼저 만나는 && 나보다 높은 건물 번호를 구하면 되기 때문에 별도의 고려사항이 추가되지 않는다.

즉, 입력되는 건물을  Stack에 담으면서 현재 Stack의 최상단 값이 높다면 정답으로 할당하고, 낮다면 Stack의 최상단 값을 높은 건물이 나올때까지 pop하면 된다. 

[풀이 과정]

1. 건물 높이 입력값을 받으면서,

• Stack 에 건물이 있다면
  • Stack의 최상단에 있는 높이 값이 현재 건물 높이보다 높을때까지 stack.pop()
  • 현재 건물보다 높은 건물을 만나면 해당 건물 번호를 정답으로 할당
• 없다면, Stack에 건물 정보(건물 번호, 건물 높이) 저장

3. 정답 출력

정답 코드

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));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        Deque<Building> stack = new ArrayDeque<>(); // 건물 정보를 담을 Stack
        int[] answers = new int[n];
        for (int i=0; i<n; i++) {
            int height = Integer.parseInt(st.nextToken()); // 현재 건물 높이

            while (!stack.isEmpty()) {
                Building building = stack.peek();
                // Stack의 최상단에 있는 높이 값이 현재 견물보다 높을때까지 stack.pop()
                if (building.height <= height) {
                    stack.pop();
                } else { // 현재 건물보다 높은 건물을 만나면 해당 건물 번호 정답으로 할당
                    answers[i] = building.num;
                    break;
                }
            }
            stack.push(new Building(i+1, height));
        }

        StringBuilder sb = new StringBuilder();
        for (int answer: answers) {
            sb.append(answer);
            sb.append(" ");
        }
        System.out.println(sb);
    }
    static class Building {
        int num;
        int height;

        public Building(int num, int height) {
            this.num = num;
            this.height = height;
        }
    }
}

문제 링크

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

문제 설명

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

• 1+1+1+1
• 2+1+1 (1+1+2, 1+2+1)
• 2+2
• 1+3 (3+1)

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

문제 풀이

[고려사항]

숫자 합은 중복이 없는 조합으로 구해야한다.

그리고 주어지는 테스트 케이스 개수는 최대 10,000개이므로 매 테스트마다 모든 수에 대한 계산을 하면 시간초과가 발생한다. 

[알고리즘, 구현방법]

이미 한 계산에 대한 값을 꺼내 쓰는 문제이기 때문에 DP 로 구현했다.

dp[i-1]은 dp[i]의 1을 포함한 숫자 합의 경우의 수이다.

dp[2]는 1+1, 2의 경우로 2가지의 합의 조합이 나온다.

dp[3]은 1+1+1, 1+2, 3 의 합의 조합이 나오는데, 이때 dp[2]의 (1+1)에 +1, 2에 +1을 한 두가지의 경우의 수가 무조건 포함된다

따라서 dp[i]는 dp[i-1]의 합의 조합에 +1을 한 경우와 2,3의 조합으로만 이루어진 합의 조합의 수를 합한 것이 된다.

dp[i] = dp[i-1] + (2,3으로만 이루어진 합의 조합)

2,3으로만 이루어진 합의 조합을 찾는 방법은 아래와 같다.

n을 2로 나눈 몫만큼 반복하면서, 2의 개수를 순차적으로 줄여, 2,3의 합으로 n을 만들 수 있다면 카운팅하면 된다.

예를 들어, n = 10 일때, 10을 2로 나눈 몫은 5이다. 2의 개수를 5개, 4개, 3개, 2개, 1개로 줄이면서 3과의 합의 조합이 되는지 확인한다.

• 2가 5개: 10 - (2 * 5) = 0이므로 합이 된다. (O)
• 2가 4개: 10 - (2 * 4) = 2 | 2 < 3이므로 합이 되지 않는다. (X)
• 2가 3개: 10 - (2 * 3) = 4 | 4 > 3 | 4 % 3 != 0 이므로 합이 되지 않는다. (X) 
  • → 10에서 2를 3개 합한 6을 뺀 값인 4는 3보다 크지만 3으로 나누어떨어지지 않기 때문
• 2가 2개: 10 -(2 * 2) = 6 | 6 > 3 | 6 % 3 = 0 이므로 합이 된다. (O)
• 2가 1개: 10 -(2 * 1) = 8 | 8 > 3 | 8 % 3 != 0 이므로 합이 되지 않는다. (X)
• 2가 0개: 10 -(2 * 0) = 10 | 10 > 3 | 10 % 3 != 0 이므로 합이 되지 않는다. (X)

정리하면,

n을 2로 나눈 몫부터 0까지, 2의 개수를 순차적으로 줄이면서 n과 2의 개수만큼의 합을 뺀 값이 0이거나, 3보다 크고 3으로 나누어떨어지는 경우에만 합이 되는 경우로 쳐서 dp[n]에 카운팅하면 된다.

[풀이 과정]

1. dp[] 정수 배열은 n의 최댓값 + 1로 초기화, dp[1] = 1로 할당

2. 테스트 케이스만큼 반복

3. 2부터 n까지 반복하면서 dp 값 계산

• 이전에 이미 계산된 값은 넘어감
• 2로 나눈 몫에서 0까지 반복하면서 2의 개수를 줄여가며 3과 합의 조합이 이루어지는지 확인
  • 현재 dp[i] 라 했을때, i가 2의 배수인 경우, 카운팅
  • i 에서 2의 개수의 합을 뺀 값이 3보다 크고(AND) 3으로 나누어 떨어지는 경우, 카운팅

4. dp[n] 출력

정답 코드

import java.io.*;

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

        int[] test = new int[t];
        for (int i = 0; i < t; i++) {
            test[i] = Integer.parseInt(br.readLine());
        }

        int[] dp = new int[10001]; // n 은 최대 10,000
        dp[1] = 1;
        for (int num : test) { // Test case 만큼 반복
            for (int i = 2; i <= num; i++) {
                if (dp[i] > 0) continue; // 이미 계산된 값은 넘어감
                int count = 0;
                int div = i / 2;
                for (int j = div; j >= 0; j--) { // 2로 나눈 몫만큼 반복하면서 2의 개수를 순차적으로 줄임
                    int diff = i - (j * 2);
                    // i가 2의 배수인 경우(diff == 0)
                    // 2를 i개 만큼 더한 후 남은 수를 3으로 나누어서, 나누어 떨어지면 3을 채워서 합으로 만들 수 있는 경우
                    if (diff == 0 || (diff >= 3 && diff % 3 == 0)) count++;
                }
                dp[i] = dp[i-1] + count; // dp[i] = dp[i-1] + (2,3으로만 이루어진 합)
            }
            System.out.println(dp[num]);
        }
    }
}

문제 링크

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

문제 설명

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 𝐾개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 100,000 이하의 양의 정수로 이루어진 길이가 𝑁인 수열이 주어진다.  이 수열에서 같은 정수를 𝐾개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

입력

첫째 줄에 정수 𝑁(1≤𝑁≤200,000)과 𝐾(1≤𝐾≤100)가 주어진다.

둘째 줄에는 𝑎1,𝑎2,...𝑎𝑛이 주어진다 (1≤𝑎𝑖≤100,000)

출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

문제 풀이

[고려사항]

정수 N은 최대 200,000(20만)이라서 수열의 모든 정수를 돌면서 확인하면 시간초과가 될 것이다.

단순 반복해서 계산하면 안되고, 알고리즘을 사용해야한다.

[알고리즘, 구현방법]

주어진 수열에서 같은 정수를 K개 이하를 포함하는 최장 연속 부분 수열을 찾아야하므로, 두개의 포인터를 두고 조건을 확인해서 구해야한다.

즉, 투 포인터로 푸는 문제이다.

정수를 카운팅하는 배열을 두고 수열을 투 포인터(start, end)를 이용해서 확인한다.

수열의 현재 정수의 개수가 K개를 초과하면 start를 오른쪽으로 한칸씩 옮기면서 부분 수열을 확인한다.

의사코드(pseudocode)로 작성하면 아래와 같다.

while (end 포인터가 수열 원소의 개수(N)보다 작은 경우) 
    if (end 포인터가 가리키는 정수의 개수가 K개 초과하면)
        최장 거리 갱신
        while (현재 정수의 개수가 K개 이하가 될 때까지)
            start 포인터가 가리키는 정수 개수 1 감소(=부분 수열의 범위를 한칸 옆으로 이동)
            부분 수열 길이 1 감소
            start 포인터 1 증가
    else
        현재 정수(=end 포인터가 가리키는) 개수 1 증가
        부분 수열 길이 1 증가

최장 거리 갱신

[풀이 과정]

1. 입력 값 세팅 및 수열 정수의 개수 배열 생성(int[] cnt)

2. end 포인터가 n 이상이 될때까지 반복

• 현재 수열의 숫자가 연속으로 K개 초과한 경우,
  • 최장 거리 갱신
  • 현재 숫자가 K개 이하가 될 때까지
    • start 포인터 이동(=부분 수열의 시작 부분 이동)
    • 수열 길이 1 감소 & start 포인터가 가리키는 정수의 개수 1 감소(부분 수열의 범위가 옆으로 한칸 이동하기 때문)
• K개 초과하지 않은 경우
  • 현재 숫자 개수 1 증가
  • 부분 수열 길이 1 증가

3. 마지막 갱신된 부분 수열의 길이를 고려하여 최장 거리 갱신 후 정답 출력

정답 코드

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());

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

    // 숫자 개수 배열
    int[] cnt = new int[100001]; // 숫자는 최대 100_000
    int start = 0;
    int end = 0;
    int answer = 0;
    int max = 0;
    while (end < n) {
        if (cnt[sequence[end]] + 1 > k) { // 하나의 숫자가 연속 k개 초과
            if (max < answer) max = answer; // 최장 거리 갱신
            // while (sequence[start] != sequence[end]) { // 1개가 늘어서 연속 k개 초과했으므로, start가 end 숫자랑 같아질때까지 이동시키기
            while (cnt[sequence[end]] + 1 > k) { // 현재 숫자가 k개 이하가 될 때까지 start 이동
                cnt[sequence[start]]--; // start 숫자 제외
                answer--; // 수열 길이 -1
                start++; // start pointer +1
            }
        } else { // 초과 하지 않는 경우, 1) 현재 숫자 카운팅 & 2) 숫자 연속 길이 증가
            cnt[sequence[end++]]++;
            answer++;
        }
    }
    if (max < answer) max = answer; // 마지막 갱신된 길이를 고려하여 최종 max 값 갱신
    System.out.println(max);
}

문제 링크

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

문제 설명

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

문제 풀이

[고려사항]

지름길로 가는 거리와 아닌 거리의 합을 구하면서, 모든 조합 중 가장 짧은 거리를 찾아야한다.

여기서 지름길은 원래 거리보다 짧은 거리여야하고, 지름길 여러개가 범위가 겹치면 더 짧은 거리의 지름길을 선택해야한다.

이런 식으로 지름길을 선택하고 최단 거리를 고려해서 구현하려고하면 구현이 복잡해져서 예외처리를 제대로 하지 못할 수 있다.

그래서 이 문제는 DP(Dynamic Programming)로 풀어야 한다.

[알고리즘, 구현방법]

DP로 모든 거리(0 ~ D)의 지점을 방문해서 해당 거리에서의 최단 거리를 저장한다.

즉, dp[i] = i meter 까지의 최단 거리를 의미한다.

그리고 지름길의 도착 위치에서는 지름길 시작 위치 ~ 도착 위치까지의 거리와 이전 위치 + 1 중에 최솟값을 할당해야한다.

즉, 현재 지점까지의 최단 거리 = min(이전 지점까지의 최단 거리 + 1, 지름길 최단 거리(=지름길 시작 지점까지의 최단 거리 + 지름길 거리)로 계산해야한다.

지름길의 시작 위치를 s, 지름길 길이가 distance라고 한다면, (i = 현재 거리 = 지름길의 도착 위치)

dp[i] = MIN(dp[i-1] + 1, dp[s] + distance) 가 된다.

[지름길 정보 저장 방식]

지름길에 대한 정보를 가지고 있다가 0 ~ D거리를 방문하면서 지름길의 도착 위치에 도달했는지를 확인할 수 있어야한다.

dp[i]를 할당할때, 지름길의 도착 위치라면 지름길 거리를 반영해서 최솟값을 계산해야하기 때문이다.

그래서 지름길 정보를 Map<(도착 위치), (지름길 정보)>로 저장했다. Key를 도착 위치로 해두면 dp[i] 값을 할당할 때 현재 위치(i)가 Key값으로 포함되어있는지를 확인하여 지름길 여부를 판단할 수 있기 때문이다.

그리고 지름길의 도착 위치가 2개 이상인 경우도 있기 때문에, 도착 위치(Key)에 매핑되는 지름길 정보를 List로 저장했다.

Map<Integer, List<Shortcut>> shortcutInfo = new HashMap<>();

[풀이 과정]

1. 지름길 정보 저장

• 도착 위치가 고속도로 길이를 초과하면 저장 안함
• 끝 지점 - 시작 지점이 지름길 거리보다 짧으면 저장 안함 (즉, 지름길 거리가 짧은 경우에만 저장)
• 지름길 도착 위치가 2개 이상인 경우, 저장된 리스트에 지름길 정보 추가
• 지름길 도착 위치에 대해 저장된 지름길 정보가 없다면, 새로 리스트에 지름길 정보 추가

2. dp 배열에 각 위치별 최단 거리를 저장

• 현재 위치에 지름길 정보가 있다면 (=도착 위치 정보가 있다면 =Map의 containsKey가 true라면), 지름길 정보 계산
  • 도착 위치까지의 지름길 정보가 여러개인 경우가 있기때문에 해당 위치에서의 지름길 리스트를 반복하면서 최단 거리 갱신
    • 지름길 거리를 포함한 현재 위치에서의 거리 = 시작 지점까지의 최단 거리 + 해당 지름길 거리
• 현재 위치에서의 최단 거리 할당
  • 현재 지점까지의 최단 거리 = min(이전 지점까지의 최단 거리 + 1, 지름길 최단 거리(=지름길 시작 지점까지의 최단거리 + 지름길 거리)

3. dp[D] 출력

정답 코드

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());

        Map<Integer, List<Shortcut>> shortcutInfo = new HashMap<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            // 고속도로 길이를 초과하면 저장 안함
            if (e > D) continue;
            // 끝 지점 - 시작 지점이 지름길 거리보다 짧으면 저장 안함 (즉, 지름길 거리가 짧은 경우에만 저장)
            if (e - s <= d) continue;

            // 지름길 정보 세팅
            Shortcut sc = new Shortcut(s, e, d);
            List<Shortcut> list = new ArrayList<>();
            // 이미 도착 지점 지름길 정보가 있으면, 저장된 리스트 정보에 추가해야됨
            if (shortcutInfo.containsKey(e)) list = shortcutInfo.get(e);

            list.add(sc);
            shortcutInfo.put(e, list);
        }

        int[] dp = new int[D + 1];
        dp[1] = 1;
        for (int i = 1; i <= D; i++) {
            int min = D;
            if (shortcutInfo.containsKey(i)) { // 지름길 루트가 있는 경우
                int val = 0;
                for (Shortcut s: shortcutInfo.get(i)) { // 도착 지점까지의 지름길이 여러개인 경우를 위한 반복문
                    val = dp[s.start] + s.distance; // 시작 지점까지의 최단 거리 + 해당 지름길 거리
                    if (val < min) min = val; // 도착 지점까지의 지름길 중 최솟값 갱신
                }
            }
            // 현재 지점까지의 최단 거리 = min(이전 지점까지의 최단 거리 + 1, 지름길 최단 거리(=지름길 시작 지점까지의 최단 거리 + 지름길 거리)
            dp[i] = Math.min(dp[i-1] + 1, min); // 해당 지점까지의 최단 거리 계산
        }
        System.out.println(dp[D]);
    }

    public static class Shortcut {
        int start;
        int end;
        int distance;

        public Shortcut(int start, int end, int distance) {
            this.start = start;
            this.end = end;
            this.distance = distance;
        }
    }
}

문제 링크

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

문제 설명

빨간색 볼과 파란색 볼이 <그림 1>에서 보인 것처럼 일직선상에 섞여 놓여 있을 때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 볼을 옮기는 규칙은 다음과 같다.

1. 바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.
2. 옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.

예를 들어, 처음에 볼이 <그림 1>에서 보인 것처럼 있을 때, 빨간 볼을 <그림 2>에서 보인 것처럼 옮긴 후, <그림 3>에서 보인 것처럼 옮긴다면 두 번 만에 같은 색끼리 모을 수 있다.

반면에 파란색 볼을 선택하여 에서 보인 것처럼 옮기면(화살표에 있는 수는 옮기는 순서를 나타낸다) 네 번을 옮겨야 같은 색의 볼끼리 모을 수 있다.

일직선상에 놓여 있는 볼에 관한 정보가 주어질 때, 규칙에 따라 볼을 이동하여 같은 색끼리 모으되 최소 이동횟수를 찾는 프로그램을 작성하시오.

입력

첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주어질 수도 있으며, 이 경우 답은 0이 된다.

출력

최소 이동횟수를 출력한다.

입출력 예

문제 풀이

[고려사항]

볼의 총 개수인 N은 최대 500,000(50만)이고, 시간 제한은 1초(추가 시간 없음)이므로, O(N^2)이 나오지 않게 고려하여서 구현해야한다.

[알고리즘, 구현방법]

이 문제는 *그리디 알고리즘과 구현으로 해결해야한다.

*그리디 알고리즘(Greedy Algorithm): 최적해를 구하는 알고리즘으로, 각 단계에서 최적이라고 생각되는 것을 선택해나가는 방식으로 진행하여 최종적인 해답을 찾는 알고리즘이다.

빨간공(R), 파란공(B)을 각각 왼쪽, 오른쪽으로 모으는 경우에 대해 모두 확인해야한다. (총 4번) 

옮기는 횟수는 옮기려는 방향의 가장 끝 인덱스부터, 현재 확인하려하는 볼의 연속된 개수를 해당 색상의 총 볼의 개수에서 빼주면 된다. 

• 빨간 공(R)을 왼쪽/오른쪽으로 옮기는 횟수: 빨간 공의 총 개수 - 왼쪽/오른쪽에 연속으로 있는 빨간 공의 개수
• 파란 공(B)을 왼쪽/오른쪽으로 옮기는 횟수: 파란 공의 총 개수 - 왼쪽/오른쪽에 연속으로 있는 파란 공의 개수

문제의 예시로 예를 들어보면,

빨간 공(R)을 왼쪽으로 옮기는 경우, 가장 왼쪽에 있는 빨간 공(R) 하나를 제외한 4개의 공을 옮겨야하고, 옮기는 횟수는 4회이다.

파란 공(B)을 왼쪽으로 옮기는 경우, 가장 왼쪽에 있는 파란 공이 없으므로 총 4개의 파란 공을 옮겨야하고, 횟수는 4회이다.

오른쪽 방향에서는 오른쪽 끝에 있는 각 공의 수를 확인해서 계산하면 된다.

[풀이 과정]

1. 입력을 받아서 각 공의 총 개수를 저장 | 공의 위치를 배열로 저장

2. 한 종류의 공만 있는 경우, 답은 0

3. 왼쪽 끝으로 빨간 공과 파란 공을 옮기는 경우를 계산

• 왼쪽 끝부터 빨간 공, 파란 공이 연속적으로 있을때까지만 공의 개수(cnt) 카운팅
• 옮기는 횟수(moved) 계산 (moved = total - cnt)하고 횟수 최솟값 갱신

4. 오른쪽 끝으로 빨간 공과 파란 공을 옮기는 경우를 계산

• 왼쪽 끝으로 모은 경우와 방향만 다름

5. 횟수 최솟값(min) 출력

정답 코드

import java.io.*;
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());
    String ball = br.readLine();

    char[] balls = new char[N];
    int[] total = {0, 0}; // 빨간 공의 수, 파란 공의 수
    for(int i=0; i<N; i++) {
        char c = ball.charAt(i);
        balls[i] = c;
        // 색상별 공의 개수 카운팅
        if (c == 'R') total[0]++;
        else total[1]++;
    }
    // 한 종류의 공만 있는 경우
    if (total[0] == N || total[1] == N) {
        System.out.println(0);
        return;
    }

    int min = N+1;
    char[] color = {'R', 'B'};
    // 왼쪽 끝으로 모으는 경우
    for (int b = 0; b < 2; b++) {
        int idx = 0;
        int cnt = 0;
        // 공 순서에서 옮기는 공이 연속으로 존재할때까지만 왼쪽 끝에 있는 공의 수 카운팅
        while (balls[idx++] == color[b]) {
            cnt++;
        }
        int moved = total[b] - cnt; // 옮긴 횟수 계산 (총 공의 개수 - 왼쪽 끝에 있는 공의 수)
        if (moved < min) min = moved; // 최솟값 갱신
    }
    // 오른쪽 끝으로 모으는 경우
    for (int b = 0; b < 2; b++) {
        int idx = N - 1;
        int cnt = 0;
        // 공 순서에서 옮기는 공이 연속으로 존재할때까지만 오른쪽 끝에 있는 공의 수 카운팅
        while(balls[idx--] == color[b]) {
            cnt++;
        }
        int moved = total[b] - cnt; // 옮긴 횟수 계산 (총 공의 개수 - 왼쪽 끝에 있는 공의 수)
        if (moved < min) min = moved; // 최솟값 갱신
    }

    System.out.println(min);
}

1. 모노톤 스택(Monotone stack) 이란?

스택(Stack)은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 후입선출(LIFO:Last In, First Out) 형태의 자료구조 입니다.
즉, 가장 먼저 들어온 데이터가 가장 마지막에 나가고, 마지막에 들어온 데이터가 가장 먼저 나가는 구조입니다.

• 모노톤 스택(Monotone stack)은 특정한 순서를 유지하면서 데이터를 관리하는 스택 자료구조 입니다.
  • Monotone은 증가하거나 감소하는 등의 일정한 경향이 보임을 의미합니다.
• 모노톤 스택(Monotone stack)은 증가하거나 감소하는 일정한 경향을 가진 스택입니다.
• 모노톤 스택(Monotone stack)은 특정 문제에 대해 시간 복잡도를 O(N)으로 줄여주는 매우 효율적인 해결책을 제공합니다.
  • 다음/이전 데이터의 최댓값/최솟값을(Nearest Greater/Smaller Element) 찾는 문제에 유용하게 쓰입니다.

2. 모노톤 스택(Monotone stack)의 종류 및 구현

스택은 LIFO(Last In, First Out) 자료 구조이기 때문에 모노톤 스택의 최상위 요소를 제거하면서 단조 증가/감소 순서를 유지합니다. 새로운 요소는 항상 최상위에 추가됩니다.

1) 단조 증가 스택(Monotone Increasing Stack)

• 스택의 요소들이 오름차순으로 정렬되는 스택
  • 오름차순을 유지한다는 것은 스택의 아래쪽부터 위쪽으로 올라갈수록 값이 커진다는 의미
  • 스택의 최상위에서부터 시작하여 아래로 내려갈수록 값이 작아짐

• 스택의 맨 위에 있는 요소가 항상 그 아래에 있는 요소보다 크거나 같은 경우를 유지하는 스택
  
  • 스택에 새로운 요소를 추가할 때, 그 요소가 스택의 최상위 요소보다 작거나 같을 때까지 기존 요소를 제거
  • 이때, 단조성을 유지해야합니다. (스택에 있는 요소들이 항상 특정 순서(오름차순)를 유지)
  • 중복 값 허용 여부에 따라 값이 같은 경우에 대한 제거 여부를 정하면 됩니다.

Deque<Integer> stack = new ArrayDeque<>();
for (int i=0; i<arr.length; i++) {
    // 스택의 최상위 요소가 현재 값보다 크거나 같으면 pop();
    while (!stack.isEmpty() && stack.peekFirst() >= arr[i]) {
    	stack.removeFirst();
    }
    // 스택의 최상위 요소보다 작을때까지 기존 요소를 제거하고, 현재 요소 스택에 추가
    stack.offerFirst(arr[i]);
}

2) 단조 감소 스택(Monotone Decreasing Stack)

• 스택의 요소들이 내림차순으로 정렬되는 스택
  • 내림차순을 유지한다는 것은 스택의 아래쪽부터 위쪽으로 올라갈수록 값이 작아진다는 의미
  • 스택의 최상위에서부터 시작하여 아래로 갈수록 값이 커짐

• 스택의 맨 위에 있는 요소가 항상 그 아래에 있는 요소보다 작거나 같은 경우를 유지하는 스택
  • 스택에 새로운 요소를 추가할 때, 그 요소가 스택의 최상위 요소보다 크거나 같을 때까지 기존 요소를 제거
  • 이때, 단조성을 유지해야합니다. (스택에 있는 요소들이 특정 순서(내림차순)를 유지)
  • 중복 값 허용 여부에 따라 값이 같은 경우에 대한 제거 여부를 정하면 됩니다.

Deque<Integer> stack = new ArrayDeque<>();
for (int i=0; i<arr.length; i++) {
    // 스택의 최상위 요소가 현재 값보다 작거나 같으면 pop();
    while (!stack.isEmpty() && stack.peekFirst() <= arr[i]) {
    	stack.removeFirst();
    }
    // 스택의 최상위 요소보다 클 때까지 기존 요소를 제거하고, 현재 요소 스택에 추가
    stack.offerFirst(arr[i]);
}

3. 모노톤 스택(Monotone stack) 구현 - 예시로 확인

개인적으로 모노톤 스택의 종류에 대해 이해하는데에 조금 시간이 걸렸습니다. 단조 증가 스택과 단조 감소 스택의 정렬 순서가 어디부터 시작하는지에 대한 정확한 이해를 못하고 무작정 이해하려고 하다보니 헷갈렸습니다. 

그래서 마지막으로 배열 예시를 정리하면서 아직은 조금 헷갈리는 부분을 정리해보겠습니다.

public static void main(String[] args) {
    int[][] testArrays = {
        {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
        {10, 9, 8, 7, 6, 5, 4, 3, 2, 1},
        {5, 5, 4, 4, 3, 3, 2, 2, 1, 1},
        {3, 6, 1, 9, 4, 7, 2, 8, 5, 10}
    };

    for (int[] arr : testArrays) {
        System.out.println("Monotonic Stack for array: " + Arrays.toString(arr));
        incresing(arr);
        decresing(arr);
        System.out.println();
    }
}

테스트 배열을 위와 같이 4가지 정도로 생성해두고 단조 증가 스택과 단조 감소 스택을 출력해보았습니다.

*각 스택은 2번 목차의 코드를 수행해서 생성

위 코드에 대한 출력 결과는 아래와 같습니다.

Monotonic Stack for array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Monotonic Increasing Stack: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 
Monotonic Decreasing Stack: 10, 

Monotonic Stack for array: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Monotonic Increasing Stack: 1, 
Monotonic Decreasing Stack: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 

Monotonic Stack for array: [5, 5, 4, 4, 3, 3, 2, 2, 1, 1]
Monotonic Increasing Stack: 1, 
Monotonic Decreasing Stack: 1, 2, 3, 4, 5, 

Monotonic Stack for array: [3, 6, 1, 9, 4, 7, 2, 8, 5, 10]
Monotonic Increasing Stack: 10, 5, 2, 1, 
Monotonic Decreasing Stack: 10,

단조 증가 스택은 요소들이 오름차순(스택의 아래부터 최상위까지)으로 정렬되어 있는 스택

단조 감소 스택은 요소들이 내림차순(스택의 아래부터 최상위까지)으로 정렬되어 있는 스택

인 점을 머리속에 꼭 담아두고 출력 결과를 확인해보면, 제대로 출력되는 것을 알 수 있습니다.

코드 구현시 중복 값은 허용하지 않았기 때문에 3번 예시처럼 중복 값이 없는 것을 확인할 수 있습니다.

만약 중복을 허용한다면 아래와 같은 결과가 출력됩니다.

Monotonic Stack for array: [5, 5, 4, 4, 3, 3, 2, 2, 1, 1]
Monotonic Increasing Stack: 1, 1, 
Monotonic Decreasing Stack: 1, 1, 2, 2, 3, 3, 4, 4, 5, 5,

단조 증가 스택 함수는 아래와 같을때 마지막 예시인 {3, 6, 1, 9, 4, 7, 2, 8, 5, 10} 에 대한 단조 증가 스택 생성 과정을 구체적으로 보겠습니다.

public static void incresing(int[] arr) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i=0; i<arr.length; i++) {
        // 스택의 최상위 요소가 현재 값보다 크거나 같으면 pop();
        while (!stack.isEmpty() && stack.peekFirst() >= arr[i]) {
        	stack.removeFirst();
        }
        // 스택의 최상위 요소보다 작을때까지 기존 요소를 제거하고, 현재 요소 스택에 추가
        stack.offerFirst(arr[i]);
    }
}

• 배열: {3, 6, 1, 9, 4, 7, 2, 8, 5, 10}

최종적으로 스택을 출력하면 [10, 5, 2, 1] 이 출력됩니다.

스택의 맨 위 요소가 현재 배열 요소보다 크거나 같으면 스택에서 제거하고, 현재 요소를 스택에 추가하면서 단조성을 유지할 수 있는 것입니다.

4. 모노톤 스택(Monotone stack) 관련 문제

• 백준 - 탑 보기

참고 링크

지난번에 트라이를 공부하고 포스팅으로 정리했는데, 아래 포스팅에서는 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 카테고리로 분류하긴 했지만, 단축 평가는 대부분의 주요 프로그래밍 언어에서 지원한다고 한다.

참고 포스팅