[코드 트리] 블럭쌓는 명령2

블럭쌓는 명령2

처음 입력으로 들어오는 입력 N, K는 각각 블록을 놓을 수 있는 칸의 수, 블록을 쌓을 명령의 횟수를 의미합니다.

각 구간이 입력될 때마다 구간별로 블록을 하나씩 쌓아올립니다.

블록을 쌓는 일이 끝나면 각 칸의 블록 높이를 세어서 출력합니다.

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

class Command {
    int start, end;
    public Command(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class Main {
    public static int length, commandCount;
    public static List<Command> commands = new ArrayList<>();
    public static int[] blocks;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        length = input[0];
        blocks = new int[length+1];
        commandCount = input[1];
        for (int i = 0; i < commandCount; i++) {
            int[] command = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int start = command[0];
            int end = command[1];
            commands.add(new Command(start, end));
        }

        for (Command command : commands) {
            for (int i = command.start; i <= command.end; i++) {
                blocks[i] += 1;
            }
        }

        int count = 0;
        for (int i = 0; i < blocks.length; i++) {
            if (blocks[i] > count) {
                count = blocks[i];
            }
        }

        System.out.println(count);
    }
}

시간복잡도

시간복잡도는 O(NK)가 됩니다.

명령 횟수만큼 최대로 블록의 칸 수를 반복해서 돌 수 있기 때문입니다.