개발옹

문제 링크

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

문제 링크

문제 설명

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

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

이 게임에서 말의 움직임은 상, 하, 좌, 우 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);
}

문제 링크

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

문제 링크

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

문제 링크

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

문제 링크

문제 설명

빙하가 깨지면서 스노우타우에 떠내려 온 "죠르디"는 인생 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;
}

문제 링크

문제 설명

완호네 회사는 연말마다 1년 간의 인사고과에 따라 인센티브를 지급합니다. 각 사원마다 근무 태도 점수와 동료 평가 점수가 기록되어 있는데 만약 어떤 사원이 다른 임의의 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있다면 그 사원은 인센티브를 받지 못합니다. 그렇지 않은 사원들에 대해서는 두 점수의 합이 높은 순으로 석차를 내어 석차에 따라 인센티브가 차등 지급됩니다. 이때, 두 점수의 합이 동일한 사원들은 동석차이며, 동석차의 수만큼 다음 석차는 건너 뜁니다. 예를 들어 점수의 합이 가장 큰 사원이 2명이라면 1등이 2명이고 2등 없이 다음 석차는 3등부터입니다.

각 사원의 근무 태도 점수와 동료 평가 점수 목록 scores이 주어졌을 때, 완호의 석차를 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ scores의 길이 ≤ 100,000
• scores의 각 행은 한 사원의 근무 태도 점수와 동료 평가 점수를 나타내며 [a, b] 형태입니다.
  • scores[0]은 완호의 점수입니다.
  • 0 ≤ a, b ≤ 100,000
• 완호가 인센티브를 받지 못하는 경우 -1을 return 합니다.

입출력 예

문제 풀이

[고려사항]

scores의 최대 길이가 100,000(십만)이므로 시간복잡도를 고려해서 구현해야한다.

*O(n^2)이면 10,000,000,000(백억)으로 보통 코딩테스트 시간을 넘어섬

[알고리즘, 구현방법]

문제만 딱 봤을때는 쉽게 풀 수 있을 줄 알았는데 생각보다 정답인 구현 방법을 생각해내기가 어려워서 시간이 꽤 걸렸다.

혼자서 생각을 못해내서 다른 분들의 아이디어에서 힌트를 얻어서 구현했다.

X 1차 생각

✅ 2차 생각

모든 사원의 근무 태도 점수(A)를 내림차순으로 정렬하고, 같은 근무 태도 점수인 경우 동료 평가 점수(B)를 오름차순으로 정렬한다.

• 입출력 예시로 들면 [3,2] [3,2] [2,1] [2,2] [1,4] 로 정렬한다.

이 리스트에서 뒤에 나온 사원의 근무 태도 점수(A)는 항상 앞에 있는 사원의 근무 태도 점수보다 작거나 같다.

반면 동료 평가 점수(B)는 오름차순으로 정렬되어있기 때문에, 뒤에 나온 사원의 동료 평가 점수가 앞에 있는 사원의 동료 평가 점수보다 작은 경우, 해당 학생(= 뒤에 나온 사원)보다 두 점수가 높은 사원이 있음이 보장된다.

• 위에서 정렬한 예시로 보면, 인덱스를 0부터 시작할때, 1번 사원과 2번 사원을 비교해보면 된다.
• [3,2] [3,2] [2,1] [2,2] [1,4] 
  • 2번 사원(=뒤에 나온 사원)의 동료 평가 점수(B)는 1로, 1번 사원보다 작다.
  • 그 말은 2번 사원보다 두 점수가 높은 사원인 1번 사원이 있음이 보장된다는 것이다.

앞에 있는 사원과 뒤에 있는 사원을 비교할 때, 근무 태도 점수(A)가 같은 경우가 있으니, 동료 평가 점수(B)가 작다고 해서 둘 다 작다고는 말할 수 없지 않나? 라고 생각이 든다면, 아니다.

근무 태도 점수(A)는 내림차순, 동료 평가 점수(B)는 오름차순이므로 근무 태도 점수(A)가 같은 두 사원은 앞에 있는 사원이 항상 더 큰(정확히는 크거나 같은) 동료 평가 점수(B)를 가지기 때문에 그런 경우는 없다.

결국, 정렬한 리스트에서 뒤에 있는 사원의 동료 평가 점수(B)가 앞에 있는 사원의 동료 평가 점수보다 크거나 같을때만 인센티브를 받는 사원이 되는 것이다.

[풀이 과정]

1. 완호 점수와 합계 저장
2. scores 배열을 근무 태도 점수는 내림차순으로, 동료 평가 점수는 오름차순으로 정렬
3. 정렬한 scores 배열을 순회하면서
   • 완호가 인센티브 대상자인지 확인
   • 비교할 사원의 동료 평가 점수가 이전 사원의 점수보다 크거나 같은 경우
     • 완호의 합계보다 큰 경우에만 석차 1 증가

정답 코드

import java.util.Arrays;
class Solution {
    public int solution(int[][] scores) {
        // 완호 점수와 합계 저장
        int[] target = scores[0];
		int targetSum = target[0] + target[1];
		// 근무 태도 점수는 내림차순, 동료 평가 점수는 오름차순으로 정렬
		Arrays.sort(scores, (o1, o2) -> {
			return o1[0]!=o2[0] ? o2[0]-o1[0] : o1[1]-o2[1];
		});
		
		int answer = 1;
		int before = 0;
		for (int[] score : scores) {
             // 완호가 인센티브 대상자인지 확인
			if (target[0] < score[0] && target[1] < score[1]) return -1;
            // 현 사원의 동료 평가점수가 이전 사원의 점수보다 크거나 같은 경우만 인센티브 받는 대상
			if (before <= score[1]) {
                // 완호의 합계보다 큰 경우만 석차를 올린다
				if (targetSum < score[0] + score[1]) {
					answer++;
				}
				before = score[1];
			}
		}
       
        return answer;
    }
}

문제 링크

문제 설명

민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합시다.

민호는 center이며, 파란색 네모는 여덟 명의 판매원을 표시한 것입니다. 각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10%를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가집니다. 모든 판매원은 자신이 칫솔 판매에서 발생한 이익 뿐만 아니라, 자신이 조직에 추천하여 가입시킨 판매원에게서 발생하는 이익의 10%까지 자신에 이익이 됩니다. 자신에게 발생하는 이익 또한 마찬가지의 규칙으로 자신의 추천인에게 분배됩니다. 단, 10%를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.

(상세 예시 설명은 링크 확인 요망)

각 판매원의 이름을 담은 배열 enroll, 각 판매원을 다단계 조직에 참여시킨 다른 판매원의 이름을 담은 배열 referral, 판매량 집계 데이터의 판매원 이름을 나열한 배열 seller, 판매량 집계 데이터의 판매 수량을 나열한 배열 amount가 매개변수로 주어질 때, 각 판매원이 득한 이익금을 나열한 배열을 return 하도록 solution 함수를 완성해주세요. 판매원에게 배분된 이익금의 총합을 계산하여(정수형으로), 입력으로 주어진 enroll에 이름이 포함된 순서에 따라 나열하면 됩니다.

제한사항

• enroll의 길이는 1 이상 10,000 이하입니다.
  • enroll에 민호의 이름은 없습니다. 따라서 enroll의 길이는 민호를 제외한 조직 구성원의 총 수입니다.
• referral의 길이는 enroll의 길이와 같습니다.
  • referral 내에서 i 번째에 있는 이름은 배열 enroll 내에서 i 번째에 있는 판매원을 조직에 참여시킨 사람의 이름입니다.
  • 어느 누구의 추천도 없이 조직에 참여한 사람에 대해서는 referral 배열 내에 추천인의 이름이 기입되지 않고 “-“ 가 기입됩니다. 위 예제에서는 john 과 mary 가 이러한 예에 해당합니다.
  • enroll 에 등장하는 이름은 조직에 참여한 순서에 따릅니다.
  • 즉, 어느 판매원의 이름이 enroll 의 i 번째에 등장한다면, 이 판매원을 조직에 참여시킨 사람의 이름, 즉 referral 의 i 번째 원소는 이미 배열 enroll 의 j 번째 (j < i) 에 등장했음이 보장됩니다.
• seller의 길이는 1 이상 100,000 이하입니다.
  • seller 내의 i 번째에 있는 이름은 i 번째 판매 집계 데이터가 어느 판매원에 의한 것인지를 나타냅니다.
  • seller 에는 같은 이름이 중복해서 들어있을 수 있습니다.
• amount의 길이는 seller의 길이와 같습니다.
  • amount 내의 i 번째에 있는 수는 i 번째 판매 집계 데이터의 판매량을 나타냅니다.
  • 판매량의 범위, 즉 amount 의 원소들의 범위는 1 이상 100 이하인 자연수입니다.
• 칫솔 한 개를 판매하여 얻어지는 이익은 100 원으로 정해져 있습니다.
• 모든 조직 구성원들의 이름은 10 글자 이내의 영문 알파벳 소문자들로만 이루어져 있습니다.

입출력 예

문제 풀이

[고려사항]

enroll, referral는 최대 10,000(1만)이고, seller는 100,000(10만) 때문에 시간 복잡도를 고려하여 구현해야한다.

[알고리즘, 구현방법]

판매원의 이름을 key값으로 해서 각 판매원의 정보를 저장한다.

판매원 정보로는 판매원을 조직에 참여시킨 다른 판매원의 이름과 판매원의 누적 이익금을 포함시킨다.

판매량 집계 데이터의 판매원 이름 정보인 seller를 기준으로 판매액을 분배해야하기 때문에, 각 판매원이 이익을 분배해야하는 다른 판매원 정보를 가지고 있어야한다.

판매원 정보 저장한 후 seller 정보를 기준으로 수익금을 배분한다.

예를 들어, young은 위로 3명의 판매원이 걸쳐매있기 때문에 총 4인이 이익금을 나눠가져야한다.

young이 1,200원의 이익금을 벌었다면, young은 10%를 제외한 1,080원 / young의 바로 위 판매원에게는 10%를 제외한 (120-12)108원 / 그 위 판매원에게는 10%를 제외한 (12-1)11원 / 그리고 가장 위인 center에는 1원을 분배해야한다.

즉 각 판매원이 가지는 이익금은 본인에게 할당된 금액의 10%를 제외한 금액이고, 10%만큼의 금액은 그 위 판매원에게 할당되어야한다.

X 1차 생각

아래 과정을 재귀 함수로 호출해서 수행하면 정답이 나오긴 하지만, 시간 복잡도가 O(mn)이 되어 시간 초과로 실패한다.

1. 해당 판매원에게 할당되는 이익금의 10%제외한 금액을 판매원 이익금에 누적합
2. 해당 판매원의 referral 판매원에게 10%를 제외한 금액을 할당
3. referral 판매원으로 1을 다시 수행
4. 판매원 정보에 referral이 없을때까지 수행 (=center)

public static int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        // 1. 판매원 정보 저장
        for (int i=0; i<enroll.length; i++) {
            sellerInfoMap.put(enroll[i], new SellerInfo(referral[i]));
        }
        // 2. seller 판매액 분배
        for (int i=0; i<seller.length; i++) {
            distributeProfits(seller[i], amount[i] * 100);
        }
        // 3. 결과
        int[] answer = new int[enroll.length];
        for (int i=0; i<enroll.length; i++) {
            answer[i] = sellerInfoMap.get(enroll[i]).getProfits();
        }
        return answer;
    }
    public static void distributeProfits(String seller, int profits) {
        // 해당 판매원에게 할당되는 이익금의 10% 제외한 금액을 판매원 이익금에 누적합
        int excludingTen = profits / 10;
        int netProfit = profits - excludingTen;

        SellerInfo s = sellerInfoMap.get(seller);
        s.addProfits(netProfit);

        if (s.getReferral().equals("-")) return; // 최상위 판매원(center)은 이익금 결과로 없어도 됨

        distributeProfits(s.getReferral(), excludingTen); // 해당 판매원의 referral 판매원에게 10%를 제외한 금액을 할당
    }

distributeProfits 함수를 seller 길이만큼 호출하고, 함수 내부에서는 최대 깊이가 총 판매원 수(=enroll 길이)이므로, 최악의 경우 seller 최대 길이 100,000(10만) * enroll 최대 길이 10,000(1만) = 1,000,000,000(10억)이므로 시간 초과가 뜬다.

즉, 시간 복잡도O(mn)으로 실패한다. (m = seller 길이, n = enroll 길이)

✅ 2차 생각

seller를 순회하면서 각 seller에 대한 이익금 분배를 BFS로 수행하면 시간 복잡도를 O(m+n)으로 줄일 수 있다.

각 판매원에 대해 BFS 순회를 1번만 하기때문에 m(seller 길이) + n(enroll 길이)로 수행할 수 있는 것이다.

그리고 탈출 조건으로 더이상 분배할 이익금이 없는 경우도 추가한다.

해당 조건을 추가함으로써 불필요한 반복문 수행을 없앤다.

[풀이 과정]

1. 판매원 정보 저장
   • 판매원 정보: 해당 판매원을 추천한 판매원 정보(referral), 해당 판매원의 이익금(profits)
2. seller 순회하면서 판매액 분배
   • 이익금을 얻은 판매원(seller)의 상위 판매원들을 모두 BFS로 순회하면서 이익금을 규칙에 맞게 할당
3. 결과 출력

정답 코드

static Map<String, SellerInfo> sellerInfoMap = new HashMap<>();
public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
    // 1. 판매원 정보 저장
    for (int i=0; i<enroll.length; i++) {
        sellerInfoMap.put(enroll[i], new SellerInfo(referral[i]));
    }
    // 2. seller 판매액 분배
    for (int i=0; i<seller.length; i++) {
        distributeProfits(seller[i], amount[i] * 100);
    }
    // 3. 결과
    int[] answer = new int[enroll.length];
    for (int i=0; i<enroll.length; i++) {
        answer[i] = sellerInfoMap.get(enroll[i]).getProfits();
    }
    return answer;
}
public void distributeProfits(String seller, int profits) {
    Queue<String> queue = new LinkedList<>();
    queue.offer(seller);
    int currentProfit = profits;

    while (!queue.isEmpty() && currentProfit > 0) { // 더이상 분배할 판매원이나 이익금이 없을때까지 반복
        String currentSeller = queue.poll();
        // 해당 판매원에게 할당되는 이익금의 10% 제외한 금액을 판매원 이익금에 누적합
        int excludingTen = currentProfit / 10;
        int netProfit = currentProfit - excludingTen;

        SellerInfo s = sellerInfoMap.get(currentSeller);
        s.addProfits(netProfit);

        currentProfit = excludingTen;
        if (!s.getReferral().equals("-")) { // 최상위가 아닌 경우에 Queue에 판매원 추가
            queue.offer(s.getReferral());
        }
    }
}
public class SellerInfo {
    private String referral;
    private int profits;
    public SellerInfo(String referral) {
        this.referral = referral;
        this.profits = 0;
    }
    public void addProfits(int profits) {
        this.profits += profits;
    }
    public String getReferral() {
        return referral;
    }
    public int getProfits() {
        return profits;
    }
}

문제 링크

문제 설명

도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있습니다. 이 그래프들은 1개 이상의 정점과, 정점들을 연결하는 단방향 간선으로 이루어져 있습니다.

• 크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있습니다. 도넛 모양 그래프의 아무 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가면 나머지 n-1개의 정점들을 한 번씩 방문한 뒤 원래 출발했던 정점으로 돌아오게 됩니다. 도넛 모양 그래프의 형태는 다음과 같습니다.

• 크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있습니다. 막대 모양 그래프는 임의의 한 정점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재합니다. 막대 모양 그래프의 형태는 다음과 같습니다.

• 크기가 n인 8자 모양 그래프는 2n+1개의 정점과 2n+2개의 간선이 있습니다. 8자 모양 그래프는 크기가 동일한 2개의 도넛 모양 그래프에서 정점을 하나씩 골라 결합시킨 형태의 그래프입니다. 8자 모양 그래프의 형태는 다음과 같습니다.

도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프가 여러 개 있습니다. 이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모야 ㅇ그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다.

그 후 각 정점에서 서로 다른 번호를 매겼습니다. 

이때 당신은 그래프의 간선 정보가 주어지면 생성한 정점의 번호와 정점을 생성하기 전 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 구해야 합니다.

그래프의 간선 정보를 담은 2차원 정수 배열 edges가 매개변수로 주어집니다. 이때, 생성한 정점의 번호, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 순서대로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ edges의 길이 ≤ 1,000,000
  • edges의 원소는 [a,b] 형태이며, a번 정점에서 b번 정점으로 향하는 간선이 있다는 것을 나타냅니다.
  • 1 ≤ a, b ≤ 1,000,000
• 문제의 조건에 맞는 그래프가 주어집니다.
• 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다.

입출력 예

문제 풀이

[고려사항]

edges는 최대 1,000,000(백만)이기 때문에 시간 복잡도 n^2을 조심해야한다.

[알고리즘, 구현방법]

먼저 기준이 되는 중앙노드를 판별해야한다.

그래프들과 무관한 정점을 중앙 노드라하면, 중앙 노드는 out 간선이 무조건 2개 이상인 노드이다.

제한사항에 나와있듯 나올 수 있는 그래프 개수는 2개 이상이므로, 중앙 노드에서 연결해야하는 노드는 2개 이상이기 때문에 중앙 노드에서 뻗어나가는 간선만 있고, 그 간선의 개수는 2개 이상이어야 한다.

도넛, 막대, 8자 모양 그래프에서 나가는 간선만 있으면서 그 간선 수가 2개 이상인 것은 없다.

그래서 중앙 노드 판별을 위와 같이 할 수 있다.

X 1차 생각

1. edges를 순회하면서 각 노드별 들어오는 간선, 나가는 간선, 자식 노드, 해당 노드에 연결된 노드를 Node 객체에 저장하고 중앙 노드의 자식 노드를 중심으로 순회한다.
2. 중앙 노드에 연결된 자식 노드를 순회할때는 각 자식 노드에서도 자식 노드를 순회하면서 해당 노드의 간선을 계산한다.
3. 중앙 노드에 연결된 자식 노드의 순회가 끝날때까지 2번을 반복한다.
4. 중앙 노드에 연결된 자식 노드의 자식 노드 순회도 끝나면, 저장한 간선 수와 노드 수로 그래프 모양을 판별한다.

이렇게 하면 테스트 케이스 22, 26번에서 런타임 에러가 발생한다.

edges가 크게 주어질때 재귀 깊이가 초과해서 발생하는 것으로 보인다.

* 재귀 호출을 하면 호출된 메서드에서 사용할 변수가 메모리에 추가 할당되기에 너무 깊이 들어가면 메모리가 차서 StackOverFlowError 예외가 발생한다. 

✅ 2차 생각

런타임 에러 관련해서 찾아보다가, 들어오고 나가는 간선을 기준으로 그래프 모양을 판별하라는 힌트를 보고, 코드를 수정했다.

도넛 모양, 막대 모양, 8자 모양 그래프의 각각 고유한 특성을 확인했다.

*이렇게 하니까 속도와 메모리 차이가 2배 이상 차이났다..!

• 막대 모양 : 단방향이기 때문에 Root 노드는 들어오는 간선 수가 0개이면서 나가는 간선은 1개이고, Leaf 노드는 들어오는 간선 수가 1개이면서 나가는 간선은 0개인 경우
• 도넛 모양 : 모든 노드가 들어오는 간선 수가 1개이면서 나가는 간선도 1개인 경우
• 8자 모양 : 정점으로 들어오는 간선 수가 2개이면서 나가는 간선도 2개인 경우 (=8자 모양의 중앙 노드)

이때 모든 그래프에 있는 경우는, 들어오는 간선이 1개이면서 나가는 간선도 1개인 경우이다.

이때는 해당 노드의 방문 여부와 자식 노드를 확인해서 재탐색하면 그래프 모양 확인이 가능하다.

즉, 들어오고 나가는 간선 수가 모두 1개인 경우, 해당 노드의 자식노드를 탐색하거나 이미 방문한 노드인지 확인하여 판별한다.

• 도넛 모양의 경우, 들어오고 나가는 간선 수가 1개인데 이미 방문한 노드라면 판별이 가능하다. 
• 막대 모양의 경우, 중간에 있는 노드면 위의 경우가 되는데, 이때 막대 모양 그래프는 Leaf 노드까지 방문해서 Leaf 노드에 도달하면 들어오는 간선 수가 1개이면서 나가는 간선 수가 0개이므로 판별이 가능하다.
• 8자 모양의 경우, 중간에 있는 노드가 무조건 들어오는 간선 수가 2개, 나가는 간선 수가 2개이고, 8자 모양 그래프를 모두 탐색하려면 무조건 8자 모양 그래프의 중앙 노드를 거치게 되므로 판별이 가능하다.

* 8자 모양의 경우, 도넛 모양이 2개 합쳐진 모양이지만, 시작 노드에서 전체 탐색을 하고 다시 돌아와야 이미 방문한 노드를 재방문하므로 도넛 모양과 별개로 판별 가능

[풀이 과정]

1. edges를 순회하면서 노드 정보 저장
   • Node 객체 : 들어오는 간선 수(in), 나가는 간선 수(out), 자식노드 리스트(childNodeList)
   • 예시) [2,3]
     • 2번 노드에는 나가는 간선 수 +1 & 자식노드 리스트에 3추가
     • 3번 노드에는 들어오는 간선 수 +1
2. 저장한 노드 정보로 중앙노드 찾기
   • 들어오는 간선(in) == 0 && 나가는 간선(out) >= 2
3. 중앙 노드의 자식 노드를 순회
   • 그래프 하나씩 확인해야하므로, 깊이 탐색을 위해 Stack에 자식노드 번호 저장
4. Stack 이 비워질 때까지 아래 과정 반복
   • 해당 노드에서 그래프 모양 판별이 가능하다면 판별하여 각 그래프 수 +1
     • 8자 모양이나 막대 모양 그래프의 고유한 특징으로 판별이 가능하다면 각 그래프 수 +1
   • 아니라면, 노드 방문여부 확인
     • 방문한 노드이면서 들어오고 나가는 간선 수가 1개라면 (in == 1 && out == 1) 도넛 모양 그래프 수 +1
     • 아니라면, 해당 노드의 자식 노드를 Stack에 push해서 해당 노드 위와 같은 과정으로 탐색
5. 중앙 노드 번호, 각 그래프 수 반환

정답 코드

import java.util.*;
public class Solution {
    public class Node {
        int in = 0; // 들어오는 간선
        int out = 0; // 나가는 간선
        boolean visited = false;
        List<Integer> childNodeList = new ArrayList<>(); // 자식 노드 (=나가는 간선이 가리키는 노드)
        public Node(int child) {
            if (child != 0) this.addChildNode(child); // 자식 노드가 있을때
            else this.in++;
        }
        public void addChildNode(int child) {
            this.out++;
            this.childNodeList.add(child);
        }
    }
    public int[] solution(int[][] edges) {
        /**
         * 방문한 노드인데 자식 노드로 재방문하는 경우, 도넛 모양
         * 단방향이라 무조건 한번씩만 방문하는 막대 모양 그래프는, Leaf 노드가 in=1, out=0 | Root 노드는 in=0, out=1
         * in=2, out=2인 노드가 있으면 8자 모양
         */
        int donut = 0;
        int bar = 0;
        int eight = 0;
        Map<Integer, Node> nodeMap = new HashMap<>(); // key: Node num, value: Node 정보
        // Node Setting
        for (int[] edge: edges) {
            int node = edge[0];
            int childNode = edge[1];

            if (nodeMap.containsKey(node)) nodeMap.get(node).addChildNode(childNode);
            else nodeMap.put(node, new Node(childNode));

            if (nodeMap.containsKey(childNode)) nodeMap.get(childNode).in++;
            else nodeMap.put(childNode, new Node(0));
        }
        // 중앙 노드 찾기
        int middle = 0;
        Iterator<Integer> it = nodeMap.keySet().iterator();
        while (it.hasNext()) {
            int nodeNum = it.next();
            Node node = nodeMap.get(nodeNum);
            // 들어오는 간선(in), 나가는 간선(out) 계산
            if (node.in == 0 && node.out >= 2) {
                middle = nodeNum;
                break;
            }
        }
        Stack<Integer> searchStack = new Stack<>(); // 탐색할 노드 번호 (깊이 탐색을 해야하기 때문에 Stack)
        for (int child: nodeMap.get(middle).childNodeList) {
            searchStack.push(child);
            nodeMap.get(child).in--; // 중앙 노드에서 들어오는 선 제외
        }
        // Find Graph
        while (!searchStack.isEmpty()) {
            Node child = nodeMap.get(searchStack.pop());
            int in = child.in;
            int out = child.out;

            if (in == 2 && out == 2) {
                eight++;
            } else if ((in == 0 && out == 0) || (in == 1 && out == 0) || (in == 0 && out == 1)) {
                bar++;
            } else {
                if (child.visited && (in == 1 && out == 1)) donut++;
                else if (!child.childNodeList.isEmpty()) for (int num: child.childNodeList) searchStack.push(num);
            }
            child.visited = true;
        }
        return new int[]{middle, donut, bar, eight};
    }
}

문제 링크

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution을 작성해주세요.

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

문제 풀이

[고려사항]

입국심사를 기다리는 사람(n)의 최대값이 1,000,000,000(십억)이고, 시간복잡도 O(n)으로 풀어야한다.

[알고리즘, 구현방법]

times에 담긴 각 심사관의 심사 시간이 더 짧은 순으로 배정을 해서 n명을 입국심사한다.

어떤 시점에서 심사 시간이 더 긴 심사관이 비어있는 상태라해도 더 짧게 끝낼 수 있는 심사관이 심사해야 최솟값을 구할 수 있다.

X 1차 생각

times를 값이 작은 순서대로 정렬해서, 더 짧게 끝낼 수 있는 심사관이 우선 심사할 수 있게 한다.

맨 처음에는 별도의 조건 없이 times 배열 길이 = 심사관 수만큼 사람을 배정한다.

총 심사 소요시간 변수(answer)에는 입국심사하는 사람의 심사 시간을 누적한다.

그런데 이렇게 순차적으로 심사관을 배정하면 고려해야하는 조건이 많아진다.

ex) 입출력 예시에서 나왔듯 20분이 지난 시점에서 10분이 걸리는 심사관이 비어있지만, 1분 더 기다려서 7분이 걸리는 심사관이 심사해야 최소 시간이 나오는 예시

✅ 2차 생각

프로그래머스에 이분탐색으로 분류되어있는 것에서 힌트를 얻어서

심사 소요시간에 대한 이분탐색으로 계산해야겠다고 생각했다.

• 이분탐색은 오름차순 또는 내림차순으로 정렬된 배열에 적용 가능한 탐색 기법으로, 정렬된 배열에서 특정 값을 찾을 때 정중앙에 위치한 값을 활용하면 아주 빠른 속도로 탐색을 끝낼 수 있는 방법이다.

탐색 기준을 시간의 범위로 잡아서 이분탐색을 수행한다.

기준이 되는 mid값을 소요시간으로 두고, 그 시간(mid분)에 몇 명을 심사할 수 있는지 계산한다.

계산 값이 심사 받아야하는 인원(n)과 같다면 반환한다.

예를들어, mid = 30이고 심사시간이 각각 7분, 10분 걸리는 심사관이 있다면,

30/7 + 30/10 = 4+3 = 7명이 30분안에 심사를 받을 수 있다는 뜻이다.

여기서 28분, 29분을 같은 예시로 계산하면 모두 6명이 나오는데, 

이는 심사 받아야하는 인원(n)이 나오더라도 그보다 더 적은 시간내에 심사를 할 수도 있음을 의미한다.

따라서 반환하는 조건을 심사 받아야 하는 인원(n) == 계산한 값 으로 하면 안된다.

최소 심사 시간을 구해야하기 때문에, 이분탐색시 양 끝값인 left, right를 left > right로 조건을 두어야 

n명이 모두 심사를 받은 시간이라해도 더 적은 시간을 찾을 수 있다.

[풀이 과정]

1. 심사 소요시간이 짧은 순으로 배열 정렬
   
   • times에 담긴 각 심사관의 심사 시간이 더 짧은 순으로 배정하기 위함
2. 최대 소요시간 계산
   • 가장 긴 심사시간 * 심사 받아야하는 총 인원
3. 이분탐색 하면서 최소 시간 구하기
   • left = 0분 , right = 최대 소요시간 , mid = (left + right) / 2
   • n명이 모두 심사가능한 시간이라해도 그보다 더 최솟값이 있을 수 있으므로,
     • 반복문 탈출 조건을 심사 받아야 하는 인원(n) == 계산한 값으로 하지 않음
     • 반복문 탈출 조건은 left > right 로 설정 (while문의 수행 조건으로는 left <= right가 됨)
   • mid분에 계산한 심사 가능 인원이 n보다 작다면,
     • 해당 시간안에 모든 사람을 심사할 수 없다는 뜻이므로, mid보다 큰 값의 범위를 탐색
   • mid분에 계산한 심사 가능 인원이 n보다 크거나 같다면, 
     • mid보다 작은 값의 범위를 탐색
     • 현재 값보다 최솟값이 있을 수 있으므로 우선 answer에 저장 후 진행
4. left <= right 가 FALSE가 되면 반복문 탈출해서 answer 반환

[Java 문법]

int[] to List

1차 생각을 구현하기 위해 int 배열을 List로 변환하는 방법에 대해 찾아보다가 알게된 내용을 포스팅 했다.

[Java] Array를 List로 변환 : int[] to List<Integer>

1차 시도 실패

이분탐색에 필요한 right 값, 

즉 최대 소요시간 계산시 우항인 n, times[times.length-1]을 long 타입으로 변환하지 않아서 실패했다.

long right = n * times[times.length-1];

🔼 실패코드 원인 부분

int * int = int인데, int 값의 범위를 넘어서면서(=오버플로우 발생) long 변수에 할당하여 문제가 발생한 것이다.

n의 최대값은 1,000,000,000(십억)이고 심사관은 최대 100,000(10만)명이라서 

두 수의 최대값은 1,000,000,000 * 100,000 = 100,000,000,000,000(100조)라는 어마무시하게 큰 수가 나온다. 

int형은 할당되는 메모리의 크기가 4바이트로, 최대값은 2의 31승 - 1인 2,147,483,647이므로 당연히 오버플로우가 발생한다.

long형은 할당되는 메모리의 크기가 8바이트로, 최대값은 2의 63승 - 1인 9,223,372,036,854,775,807라서 범위가 넘지 않는다.

* 2의 n승보고 대략적인 0의 개수 확인하기

따라서 int형은 오버플로우 발생 가능성이 있으므로, 우항 변수를 long 타입으로 변환하여 계산하는 것으로 바꿨다.

정답 코드

public static long solution(int n, int[] times) {
    Arrays.sort(times); // 심사 소요시간이 짧은 순으로 정렬
    long answer = 0; // 최소 심사 시간(최종 결과)

    long left = 0;
    // 최대 소요시간 = 가장 긴 심사시간 * 심사 받아야하는 총 인원
    long right = (long)n * (long)times[times.length-1]; // int형 오버플로우 발생 가능성이 있으므로, 우항 변수를 long 타입으로 변환하여 계산
    // n명이 모두 심사가능한 시간이라해도, 그보다 더 최솟값이 있을 수 있으므로, while조건을 (n == complete)로 하지 않음
    while (left <= right) {
        long mid = (left + right) / 2;
        long complete = 0; // mid 분안에 심사를 할 수 있는 인원수
        // mid 분 안에 심사를 할 수 있는 인원수 계산
        for (int i=0; i < times.length; i++) {
            complete += mid / times[i]; // 각 심사 시간으로 나눠서 심사 가능 인원 계산
        }

        // 심사 가능 인원이 n보다 작다면, 해당 시간안에 모든 사람을 심사할 수 없다는 뜻이므로, mid보다 큰 값의 범위를 탐색
        if (complete < n) {
            left = mid + 1;
        } else { // 계산한 심사한 사람 수가 n보다 크거나 같다면
            right = mid - 1; // mid보다 작은 값의 범위를 탐색
            answer = mid; // 현재 값보다 최솟값이 있을 수 있으므로 우선 answer에 저장 후 진행
        }
    }
    return answer;
}

참고 포스팅

[ 알고리즘 ] 이분탐색(Binary Search), upper_bound, lower_bound (C++)

JAVA 기본 자료형 & 데이터 타입 - 한눈에 정리

문제 링크

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0,1,3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

문제 풀이

이 문제는 numbers에서 추출한 한자리 숫자의 조합을 먼저 찾고, 조합한 수가 소수인지 판별하면 된다.

추출한 한자리 숫자의 조합은 dfs로 완전탐색을 이용해서 찾고, 찾은 수를 기준으로 소수 판별을 하면 된다.

이때 소수란, 1과 자기 자신 만을 약수로 가지는 수를 뜻한다.

어떤 수가 소수인지를 확인하기 위해서는 2부터 그 숫자 횟수만큼 반복하며 나누어떨어지는 수가 있는지 확인하는 방법도 있지만,

해당 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 더 빠르게 구할 수 있다.

* 제곱근까지만 반복해도 되는 이유

* 이때, 대량의 소수를 한번에 판별해야 하는 경우, 에라토스테네스의 체를 이용한다.

[풀이 과정]

이 문제에서는 특정 한자리 숫자들로 조합된 숫자들의 소수 판별을 해야하므로 

1. 숫자들로 조합할 수 있는 모든 경우의 수를 찾고
2. 찾은 수가 소수가 맞는지 판단

하면 된다.

[알고리즘, 구현방법]

먼저 숫자의 조합은 위에서 말한대로 완전탐색 중 DFS를 이용해서 찾는다.

dfs(numbers, "", 0);

public static void dfs(String numbers, String s, int depth) {
    if (depth > numbers.length()) return; // numbers 끝까지 순회하면 return

    for (int i=0; i<numbers.length(); i++) {
        if (!checked[i]) {
            checked[i] = true;
            set.add(Integer.parseInt(s + numbers.charAt(i)));
            dfs(numbers, s + numbers.charAt(i), depth+1);
            checked[i] = false; // 다음 조합을 위해 false로
        }
    }
}

방문하지 않은 문자를 기존 문자열(s)에 추가하는 방식으로 숫자를 추가했다.

숫자가 중복되면 안되므로 저장할 자료구조는 Set으로 정했다.

numbers 문자열의 특정 문자의 조합이 끝나면, 다음 조합을 위해 checked를 false로 돌려준다.

이 과정을 numbers 문자열을 문자 개수만큼(=문자열 길이) 반복하면 모든 조합을 찾을 수 있다.

그리고 조합한 수의 소수 판별은 해당 수의 제곱근까지 반복하여 나머지 연산 결과가 0이 아닌지 확인한다.

public static boolean isPrime(int num) {
    if (num < 2) return false;
    for (int i=2; i <= (int)Math.sqrt(num); i++) { // num의 제곱근까지 확인
        if (num % i == 0) return false;
    }
    return true;
}

코드

import java.util.*;
public class Solution {
	Set<Integer> set;
    boolean[] checked = new boolean[7]; // 조합한 수인지 (numbers는 최대 7자)
    
	public int solution(String numbers) {
   		set = new HashSet<>();
        // 문자열 numbers의 수 조합 찾기
        dfs(numbers, "", 0);

        int answer = 0;
        // 소수 판별
        for (int val: set) {
            if (isPrime(val)) answer++;
        }

        return answer;
    }

	public void dfs(String numbers, String s, int depth) {
        if (depth > numbers.length()) return; // numbers 끝까지 순회하면 return

        for (int i=0; i<numbers.length(); i++) {
            if (!checked[i]) {
                checked[i] = true;
                set.add(Integer.parseInt(s + numbers.charAt(i)));
                dfs(numbers, s + numbers.charAt(i), depth+1);
                checked[i] = false; // 다음 조합을 위해 false로
            }
        }
    }

    public boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i=2; i <= (int)Math.sqrt(num); i++) { // num의 제곱근까지 확인
            if (num % i == 0) return false;
        }
        return true;
    }
}

문제 링크

문제 설명

고객의 약관 동의를 얻어서 수집된 1 ~ n번으로 분류되는 개인정보 n개가 있습니다. 약관 종류는 여러 가지 있으며 각 약관마다 개인정보 보관 유효기간이 정해져 있습니다. 당신은 각 개인정보가 어떤 약관으로 수집됐는지 알고 있습니다. 수집된 개인정보는 유효기간 전까지만 보관 가능하며, 유효기간이 지났다면 반드시 파기해야 합니다.

예를 들어, A라는 약관의 유효기간이 12달이고, 2021년 1월 5일에 수집된 개인정보가 A약관으로 수집되었다면 해당 개인정보는 2022년 1월 4일까지 보관 가능하며 2022년 1월 5일부터 파기해야 할 개인정보입니다. 

당신은 오늘 날짜로 파기해야 할 개인정보 번호들을 구하려 합니다.

모든 달은 28일까지 있다고 가정합니다.

오늘 날짜를 의미하는 문자열 today, 약관의 유효기간을 담은 1차원 문자열 배열 terms와 수집된 개인정보의 정보를 담은 1차원 문자열 배열 privates가 매개변수로 주어집니다. 이때 파기해야 할 개인정보의 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

• today는 "YYYY.MM.DD" 형태로 오늘 날짜를 나타냅니다.
• 1 ≤ terms의 길이 ≤ 20
  • terms의 원소는 "약관 종류 유효기간" 형태의 약관 종류와 유효기간을 공백 하나로 구분한 문자열입니다.
  • 약관 종류는 A~Z중 알파벳 대문자 하나이며, terms 배열에서 약관 종류는 중복되지 않습니다.
  • 유효기간은 개인정보를 보관할 수 있는 달 수를 나타내는 정수이며, 1 이상 100 이하입니다.
• 1 ≤ privacies의 길이 ≤ 100
  • privacies[i]는 i+1번 개인정보의 수집 일자와 약관 종류를 나타냅니다.
  • privacies의 원소는 "날짜 약관 종류" 형태의 날짜와 약관 종류를 공백 하나로 구분한 문자열입니다.
  • 날짜는 "YYYY.MM.DD" 형태의 개인정보가 수집된 날짜를 나타내며, today 이전의 날짜만 주어집니다.
  • privacies의 약관 종류는 항상 terms에 나타난 약관 종류만 주어집니다.
• today와 privacies에 등장하는 날짜의 YYYY는 연도, MM은 월, DD는 일을 나타내며 점(.) 하나로 구분되어 있습니다.
  • 2000 ≤ YYYY ≤ 2022
  • 1 ≤ MM ≤ 12
  • MM이 한 자릿수인 경우 앞에 0이 붙습니다.
  • 1 ≤ DD ≤ 28
  • DD가 한 자릿수인 경우 앞에 0이 붙습니다.
• 파기해야 할 개인정보가 하나 이상 존재하는 입력만 주어집니다.

입출력 예

문제 풀이

[구현방식 생각]

약관 종류별 유효기간을 개인정보 수집 일자에서 계산해서 오늘 일자와 비교한다.

개인정보 수집일자 + 약관 유효기간 > 오늘 : 보관 가능한 개인정보

개인정보 수집일자 + 약관 유효기간 < 오늘 : 파기해야 할 개인정보

수집된 개인정보 중 파기해야 할 개인정보를 반환해야 하므로,

수집된 개인정보의 정보를 담은 1차원 문자열 배열 privacies를 순회하면서 각 정보의 보관 가능 여부를 판단하는 걸로 구현했다.

[고려사항]

privacies의 최대 길이는 100이므로 한 원소씩 확인해도 시간 초과하지 않을 것이다.

그리고 파기해야 할 개인정보는 무조건 하나 이상 존재하므로 result가 null인 경우는 없기 때문에 null 예외처리는 제외해도 된다.

또한 약관 종류로 주어진 약관만 privacies에 주어지므로 이에 대한 예외처리도 하지 않아도 된다.

그리고 파기될 약관 개수가 몇 개인지 모르기 때문에 정답 배열은 리스트로(ArrayList)로 초기화한다.

약관 종류는 String이기 때문에 유효기간 정보를 담을 자료구조는 Map으로 한다.

[풀이 과정]

1. 오늘 일자(today), 약관 종류 배열(terms) 구현 용도에 맞게 세팅
   • 오늘 일자는 온점(.)을 구분자로 연, 월, 일로 변수에 저장
   • 약관 종류를 Key, 유효기간을 Value로 해서 Map에 저장
2. privacies 순회하면서 약관 유효기간 계산
   • 날짜와 약관 종류를 공백을 구분자로 분리하여 저장
   • Map에서 해당하는 약관 종류의 유효기간 가져와서 달(month)에 더함
     • 계산한 달이 12월을 넘어가는 경우 연도에 1 더하고 달에 12 빼기
   • 계산한 유효 일자랑 현재 일자 비교
     • 파기되지 않는 경우(=보관 가능한 경우)를 체크
     • 위 조건에 해당하지 않는 경우, 정답 리스트에 추가
3. int[]을 반환해야하므로 List 순회해서 answer 배열에 담아서 반환

[구현시 고려한 사항]

문자열을 구분할때 split()을 사용할지, StringTokenizer를 사용할지 고민했는데,

자바 공식 문서를 확인해보니 StringTokenizer는 레거시 클래스로, 호환성을 위해 사용되고 있기때문에  spilt 함수를 사용할 것을 권장하고 있다.

StringTokenizer is a legacy class that is retained for compatibility reasons although its use is discouraged in new code. It is recommended that anyone seeking this functionality use the split method of String or the java.util.regex package instead.

그래서 날짜를 년,월,일로 구분할때나 약관 정보를 가져올때 split() 함수를 사용했다.

💡 spilt() 주의사항

split()은 정규표현식으로 문자열을 구분하기 때문에 온점(.)을 구분자로 구분하려고 한다면 온점 앞에 역슬래시(\)를 붙여줘야한다. 

이때 Java에서 역슬래시를 표현하기 위해서는 앞에 역슬래시(\)를 붙여줘야한다. (\\)

즉, split("\\.")으로 사용해야 온점을 구분자로 문자열을 분리할 수 있다.

* 정규표현식에서 온점(.)은 임의의 한 문자를 뜻하기 때문에 온점(.)만 구분자로 넣는 경우 (즉,  split(".")), 그냥 빈 배열이 반환된다.

코드

import java.util.*;
class Solution {
	public static int[] solution(String today, String[] terms, String[] privacies) {
        // 오늘 일자 Y,M,D로 분리
        String[] todayInfo = today.split("\\.");
        int todayY = Integer.parseInt(todayInfo[0]);
        int todayM = Integer.parseInt(todayInfo[1]);
        int todayD = Integer.parseInt(todayInfo[2]);

        // 약관 종류
        Map<String, Integer> termsMap = new HashMap<>();
        for (String el : terms) {
            String[] temp = el.split(" ");
            termsMap.put(temp[0], Integer.parseInt(temp[1]));
        }

        // privacies 순회하면서 약관 유효기간 계산
        List<Integer> list = new ArrayList<>();
        int collectionY, collectionM, collectionD;
        for (int i=0; i<privacies.length; i++) {
            String[] privacyInfo = privacies[i].split(" ");
            String[] collectionDate = privacyInfo[0].split("\\.");
            collectionY = Integer.parseInt(collectionDate[0]);
            collectionM = Integer.parseInt(collectionDate[1]);
            collectionD = Integer.parseInt(collectionDate[2]);

            String typeOfTerms = privacyInfo[1];

            collectionM += termsMap.get(typeOfTerms);
            while (collectionM > 12) { // 계산한 달이 12월을 넘어가는 경우 연도에 1추가
                collectionM -= 12;
                collectionY += 1;
            }

            // 계산한 유효 일자랑 현재 일자 비교 (파기되지 않는 경우(=보관 가능한 경우)를 체크)
            if (collectionY > todayY) {
                continue;
            } else if (collectionY == todayY) {
                if (collectionM > todayM) {
                    continue;
                } else if (collectionM == todayM) {
                    if (collectionD > todayD) continue;
                }
            }
           list.add(i+1);
        }

        int[] answer = new int[list.size()];
        int idx = 0;
        for (int index : list) {
            answer[idx++] = index;
        }
        return answer;
    }
}

문제 링크

문제 설명

주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 아래는 하나의 예시를 나타냅니다.

• 어떤 차량이 입차된 후에 출차된 내역이 없다면, 23:59에 출차된 것으로 간주합니다.
  • 0000번 차량은 18:59에 입차된 이후, 출차된 내역이 없습니다. 따라서, 23:59에 출차된 것으로 간주합니다.
• 00:00부터 23:59까지의 입/출차 내역을 바탕으로 차량별 누적 주차 시간을 계산하여 요금을 일괄로 정산합니다.
• 누적 주차 시간이 기본 시간이하라면, 기본 요금을 청구합니다. 
• 누적 주차 시간이 기본 시간을 초과하면, 기본 요금에 더해서, 초과한 시간에 대해서 단위 시간 마다 단위 요금을 청구합니다.
  • 초과한 시간이 단위 시간으로 나누어 떨어지지 않으면, 올림합니다. 
  • ⌈a⌉ : a보다 작지 않은 최소의 정수를 의미합니다. 즉, 올림을 의미합니다.

주차 요금을 나타내는 정수 배열 fees, 자동차의 입/출차 내역을 나타내는 문자열 배열 records가 매개변수로 주어집니다. 차량 번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

제한사항

• fees의 길이 = 4 
  • fees[0] = 기본 시간(분) | 1 ≤ fees[0] ≤ 1,439
  • fees[1] = 기본 요금(원) | 0 ≤ fees[1] ≤ 100,000
  • fees[2] = 단위 시간(분) | 1 ≤ fees[2] ≤ 1,439
  • fees[3] = 단위 요금(원) | 1 ≤ fees[3] ≤ 10,000
• 1 ≤ records의 길이 ≤ 1,000
  • records의 각 원소는 "시각 차량번호 내역" 형식의 문자열입니다.
  • 시각, 차량번호, 내역은 하나의 공백으로 구분되어 있습니다.
  • 시각은 차량이 입차되거나 출차된 시각을 나타내며, HH:MM 형식의 길이 5인 문자열입니다.
    • HH:MM은 00:00부터 23:59까지 주어집니다. 
    • 잘못된 시각("25:22", "09:65" 등)은 입력으로 주어지지 않습니다.
  • 차량번호는 자동차를 구분하기 위한, `0'~'9'로 구성된 길이 4인 문자열입니다. 
  • 내역은 길이 2 또는 3인 문자열로, IN 또는 OUT입니다. IN은 입차를, OUT은 출차를 의미합니다. 
  • records의 원소들은 시각을 기준으로 오름차순으로 정렬되어 주어집니다. 
  • records는 하루 동안의 입/출차된 기록만 담고 있으며, 입차된 차량이 다음날 출차되는 경우는 입력으로 주어지지 않습니다.
  • 같은 시각에, 같은 차량번호의 내역이 2번 이상 나타내지 않습니다. 
  • 마지막 시각(23:59)에 입차되는 경우는 입력으로 주어지지 않습니다. 
  • 아래의 예를 포함하여, 잘못된 입력은 주어지지 않습니다.
    • 주차장에 없는 차량이 출차되는 경우 
    • 주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우

입출력 예

문제 풀이

시각을 기준으로 오름차순 정렬되어있는 records를 차량번호을 기준으로 오름차순 정렬해서 사용 요금을 반환해야한다.

그래서 먼저 records를 차량번호를 Key값, 그 외 정보를 Value로 담아서 저장해서 계산해야겠다고 생각하여 구현했다.

[정의한 클래스 및 함수 설명]

[ParkingInfo 클래스]

• 차량번호별 주차 정보를 관리할 클래스
• 멤버 변수: 차량번호(carNum), 입차시간(inTime), 총 누적시간(totalTime)
  • 주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우는 입력에 없기 때문에, 입차시간과 출차시간을 쌍으로 묶어 저장할 필요는 없다고 판단하였다.
  • 입/출차 기록에서 출차인 경우, 총 누적시간(totalTime)을 계산하여 갱신하는 방식으로 구현했다.
• setTotalTime(doble totalTime)
  • 해당 차량의 총 누적시간을 갱신 
    • this.totalTime += totalTime
  • '주차장에 없는 차량이 출차되는 경우'나 '주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우'는 없기 때문에 총 누적시간 계산/갱신시 저장되어있던 입차시간(inTime)은 초기화한다.
    • this.inTime = "";
• implements Comparable<ParkingInfo> : @Override compareTo(ParkingInfo o)
  • 차량번호를 기준으로 정렬하기 위해 Comparable 인터페이스를 implements한다.
• @Override equals(), hashCode()
  • 차량번호를 기준으로 객체 비교
  • 객체의 멤버 변수인 차량번호(carNum)가 같다면, 같은 객체로 판단해야하기때문에 equals()와 hashCode()를 오버라이딩했다.

[calculateTime(String in, String out)]

public static double calculateTime(String in, String out) {
    double inH = Integer.parseInt(in.substring(0,2));
    double inM = Integer.parseInt(in.substring(2));
    double outH = Integer.parseInt(out.substring(0,2));
    double outM = Integer.parseInt(out.substring(2));

    return (outH * 60 + outM) - (inH * 60 + inM);
}

• 주차장 사용 시간 계산 메소드
• 이후 주차 요금 계산시 단위 시간 당 총 누적시간을 계산해야되어서 올림 연산이 필요하기 때문에 double로 선언
• 입/출차 시간의 시, 분을 나눠서, 시간에 *60해서 분으로 치환하여 계산한다.
  • 사용시간 = (출차 시 * 60 + 출차 분) - (입차 시 * 60 + 입차 분)

[풀이 과정]

1. records 순회하면서 Map, ParkingInfo 로 세팅
   • Map<String, ParkingInfo>
   • 입/출차 내역은 "시각 차량번호 내역" 형식의 문자열
     • 시각: "HH:MM"형식이므로 ":"를 공백으로 치환
       
       • 이후 누적시간 계산시 형변환하여 계산하기 위함
       • 올림 함수인 Math.ceil 을 정수형으로 계산시, 정수로 계산되기 때문에 원하는 값을 얻지 못할 수 있다.
         • 정수10/정수4를 올림함수를 이용하면 기대하던 3.0이 아니라 2.0이 반환된다.
         • 따라서 올림 값을 제대로 받으려면 실수형을 계산해야한다.
   • Map의 Key값인 차량번호가 이미 있는 경우
     • 내역이 입차(IN)인 경우, 저장된 ParkingInfo 객체에 inTime을 갱신
     • 내역이 출차(OUT)인 경우, 저장된 ParkingInfo 객체의 inTime을 가져와서 출차시간으로 총 누적시간 계산하고 갱신
       • calculateTime(String in, String out)
       • setTotalTime(double totalTime)
   • MaP의 Key값인 차량번호가 없는 경우(=입/출차기록이 없는 경우)
     • Key로 cardNum과 Value에 ParkingInfo를 세팅해서 Map에 추가한다.
     • OUT이 먼저 들어오는 경우는 제한사항에서 제외되었기에 고려하지 않아도 된다.
2. records 확인 및 List에 값 할당 / 정렬
   • Map에 저장된 차량 번호를 순회하면서
     • 출차 시간이 입력되지 않은 경우 totalTime 계산해서 갱신
       • 이때, 출차 시간은 23시 59분
     • 정렬을 위해 ParkingInfo를 리스트에 저장
       • infoList.sort(ParkingInfo::compareTo);
       • 정렬은 ParkingInfo에 오버라이딩 한 비교(compareTo)를 기준으로 한다.
3. 주차 요금 계산
   • fees 요소를 기본 시간, 기본 요금, 단위 시간, 단위 요금을 할당
   • 정렬을 한 list를 순회하면서 계산한 주차 요금을 int[] answer에 저장
     • 총 누적시간이 기본 시간이상이라면 요금 계산
       • 기본 요금 + 올림((총 누적시간 - 기본시간) / 단위 시간) * 단위 요금
     • 총 누적시간이 기본 시간을 넘지 않는다면 기본 요금을 저장
   • list에 이미 차량번호 순으로 정렬해두었기 때문에 answer 배열에 차량번호 순으로 주차 요금을 저장할 수 있다.

[구현시 고려(고민)한 사항]

records를 ParkingInfo로 저장할 때, 자바 클래스 중 List, Map 중 Map 으로 선택했다. 

입차/출차 내역이 있는지 확인해야 했기에 해당 Key값이 있는지 확인할 수 있는 구조가 필요했다.

•  Key 값을 차량번호로 두고 containsKey로 판단했다.

코드

import java.util.*;
class Solution {
	public static int[] solution(int[] fees, String[] records) {
        /**
         * 1. records 세팅
         *      - 이미 저장되어있는 차량번호 체크를 위해 map으로 선언
         */
        Map<String, ParkingInfo> map = new HashMap<>();
        for (String record : records) {
            StringTokenizer st = new StringTokenizer(record, " ");
            String time = st.nextToken().replace(":", "");
            String carNum = st.nextToken();
            String type =  st.nextToken();

            double inH, inM, outH, outM;
            if (map.containsKey(carNum)) {
                ParkingInfo carParkingInfo = map.get(carNum);
                if (type.equals("IN")) {
                    carParkingInfo.setInTime(time);
                } else { // type == "OUT"
                    // 이전에 저장되어있는 입차시간 가져와서 계산
                    String inTime = carParkingInfo.getInTime();
                    carParkingInfo.setTotalTime(calculateTime(inTime, time));
                }
            } else {
                // OUT이 먼저 들어오는 경우는 제한사항에서 제외되었기에 고려하지 않아도 됨
                map.put(carNum, new ParkingInfo(carNum, time));
            }
        }

        /**
         * 2. records 확인
         *      - 출차 시간이 입력되지 않은 경우 totalTime 계산해서 갱신
         *      - ParkingInfo를 리스트에 저장 : 정렬을 위함
         */
        List<ParkingInfo> infoList = new ArrayList<>();
        for (ParkingInfo mapInfo : map.values()) {
            String infoInTime = mapInfo.getInTime();
            if (!infoInTime.isBlank()) {
                mapInfo.setTotalTime(calculateTime(infoInTime, "2359"));
            }
            infoList.add(mapInfo);
        }
        infoList.sort(ParkingInfo::compareTo);

        /**
         * 3. 주차 요금 계산
         */
        double basicTime = fees[0];
        int basicPrice = fees[1];
        double unitTime = fees[2];
        int pricePerTime = fees[3];

        int[] answer = new int[map.size()];
        int idx = 0;
        for (ParkingInfo info : infoList) {
            int calPrice = basicPrice;
            if (info.getTotalTime() >= basicTime) {
                calPrice += Math.ceil((info.getTotalTime() - basicTime)/unitTime) * pricePerTime;
            }
            answer[idx++] = calPrice;
        }

        return answer;
    }

    public static double calculateTime(String in, String out) {
        double inH = Integer.parseInt(in.substring(0,2));
        double inM = Integer.parseInt(in.substring(2));
        double outH = Integer.parseInt(out.substring(0,2));
        double outM = Integer.parseInt(out.substring(2));

        return (outH * 60 + outM) - (inH * 60 + inM);
    }

    public static class ParkingInfo implements Comparable<ParkingInfo>{
        String carNum; // 차량번호

        String inTime; // 입차시간 (주차장에 이미 있는 차량(차량번호가 같은 차량)이 다시 입차되는 경우는 입력에 없기 때문에)
        double totalTime; // 총 누적시간

        public ParkingInfo(String carNum, String inTime) {
            this.carNum = carNum;
            this.inTime = inTime;
            this.totalTime = 0;
        }

        public void setInTime(String inTime) {
            this.inTime = inTime;
        }

        public String getInTime() {
            return inTime;
        }

        public void setTotalTime(double totalTime) {
            this.inTime = ""; // 입차시간 초기화 (출차시간 입력되는 경우에만 totalTime Setting)
            this.totalTime += totalTime;
        }

        public double getTotalTime() {
            return totalTime;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            ParkingInfo other = (ParkingInfo) o;
            return other.carNum == carNum;
        }

        @Override
        public int hashCode() {
            return Objects.hash(carNum);
        }

        @Override
        public int compareTo(ParkingInfo o) {
            int intCarNum = Integer.parseInt(this.carNum);
            int intOtherCarNum = Integer.parseInt(o.carNum);
            return intCarNum - intOtherCarNum;
        }
    }
}

참고 포스팅