1. 첫번째 문제 풀이(2024-08-03)

첫번째 문제와 두번째 문제는 코테의 대표적인 일차원 좌표 문제들 중 하나인데요. 그 중 첫번째 문제는 끝점을 포함하지 않는 오프셋 범위의 좌표 문제이고, 두번째 문제는 오프셋을 고려하지 않고 끝 점을 고려한 좌표 문제였죠.

그래서 일단 오프셋에 대한 개념과 끝점을 포함하는지에 대한 여부의 개념을 먼저 설명드린 뒤에 각 문제의 문제 풀이를 설명 드리도록 하겠습니다.

오프셋

오프셋이란 특정 기준점에서의 상대적인 위치나 거리, 또는 차이를 의미하는데요. 여기서는 음의 좌표에 대한 오프셋을 계산하는 용도로 사용되는데, 예시를 들면 다음과 같습니다.

끝이 겹치는 경우?

다시 문제로 돌아와, 저는 위와 같은 원리로 첫번째 문제에 다음과 같은 조건을 걸었습니다.

1. 각 선분 중에서의 최소값 x1 좌표와 최대값 x2 좌표를 구해 이 좌표 길이 만큼의 배열(arr)을 만들고 0으로 채운다.
2. 오프셋은 최소값의 절대값으로 잡고 각 전체 선분 개수만큼 반복문을 돌면서 arr의 각 자리값에 각 좌표대로 1씩 더해준다
3. 내림차순 정렬을 수행한 뒤 첫번째 값 (제일 큰 값)을 구한다. (물론 이 연산은 Math.max 연산으로도 가능합니다.)

그리고 두번째 문제도 이와 같은 원리로 다음과 같은 조건을 걸었는데요. 다만 끝점을 포함하기 때문에 for문을 끝 점 까지의 범위로 잡고(<=) 진행했습니다.

이와 같은 원리로 풀게 된 JS 코드는 다음과 같습니다.

1-1. 첫번째 문제 자바스크립트 버전

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

// 입력의 첫 줄에서 범위의 개수를 읽어옴
const length = Number(input.shift());

// 최소 범위와 최대 범위를 저장할 변수
let minRange = 0;
let maxRange = 0;
const ranges = [];

// 각 범위를 처리하여 최소 및 최대 범위를 결정
for (let i = 0; i < length; i++) {
    const [startPoint, endPoint] = input[i].split(" ").map(Number);
    ranges.push({ startPoint, endPoint });
    if (startPoint < minRange) {
        minRange = startPoint;
    }
    if (endPoint > maxRange) {
        maxRange = endPoint;
    }
}

// 음수 인덱스를 처리하기 위해 배열의 오프셋을 계산
const offset = Math.abs(minRange);

// 최소 범위에서 최대 범위까지의 크기를 가진 배열을 생성 (0의 범위를 포함하기 위해 +1을 해줌)
const arr = Array.from({ length: maxRange - minRange + 1 }, () => 0);

// 각 범위에 따라 배열의 값을 증가시킴
for (const { startPoint, endPoint } of ranges) {
    for (let i = startPoint + offset; i < endPoint + offset; i++) {
        arr[i]++;
    }
}

// 배열에서 최대 값을 찾아 출력
console.log(Math.max(...arr));

1-2. 두번째 문제 자바스크립트 버전

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

// 선분의 개수
const length = Number(input.shift());

// 최소 범위와 최대 범위를 저장할 변수 (초기값 설정)
let minRange = Infinity;
let maxRange = -Infinity;

// 각 선분의 시작점과 끝점을 저장
const lines = [];

for (let i = 0; i < length; i++) {
    const [startPoint, endPoint] = input[i].split(" ").map(Number);
    lines.push([startPoint, endPoint]);
    if (minRange > startPoint) minRange = startPoint;
    if (maxRange < endPoint) maxRange = endPoint;
}

// 이번에는 offset을 이용하지 않고  전체 길이를 이용해서 풀었는데요.
// 최소값에서 최대값까지의 크기를 오프셋과 선분 0을 고려해 배열을 생성했습니다.
const overlapArray = Array(maxRange - (Math.abs(minRange) + 1)).fill(0);

// 각 선분의 시작점부터 끝점까지 배열의 값을 증가
for (const [startPoint, endPoint] of lines) {
    for (let i = startPoint; i <= endPoint; i++) {
        // 해당 구간의 오프셋을 고려해 -minRange를 먼저 계산한 후 그 구간을 증가
        overlapArray[i - minRange]++;
    }
}

// 결과 출력
console.log(overlapArray.sort((a,b) => b-a)[0]);

그리고 이 코드를 자바 코드로 변환한 버전은 다음과 같습니다.

2-1 첫번째 문제 자바 코드 버전

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int length = scanner.nextInt();
        scanner.nextLine(); // 줄바꿈 문자 처리
      
        int minRange = Integer.MAX_VALUE;
        int maxRange = Integer.MIN_VALUE;
		// 선분의 개수와 x1, x2 좌표 개수
        int[][] ranges = new int[length][2];

        // 입력 및 범위 계산
        for (int i = 0; i < length; i++) {
            String line = scanner.nextLine();
            String[] parts = line.split(" ");
            int startPoint = Integer.parseInt(parts[0]);
            int endPoint = Integer.parseInt(parts[1]);
            ranges[i] = new int[]{startPoint, endPoint};

            if (startPoint < minRange) {
                minRange = startPoint;
            }
            if (endPoint > maxRange) {
                maxRange = endPoint;
            }
        }

        // 음수 인덱스를 처리하기 위한 오프셋 계산
        int offset = Math.abs(minRange);
        int size = maxRange - minRange + 1;
        int[] arr = new int[size];

        // 배열 값 증가
        for (int[] range : ranges) {
            int startPoint = range[0];
            int endPoint = range[1];
            for (int i = startPoint + offset; i < endPoint + offset; i++) {
                if (i >= 0 && i < size) { // 배열의 범위를 벗어나지 않도록 확인
                    arr[i]++;
                }
            }
        }
     
        // 최대값 찾기 (내림차순 후 배열의 마지막 끝 요소 출력)
        Arrays.sort(arr);
        int max = arr[arr.length - 1];

        System.out.println(max);
      
      
        scanner.close();
    }
}

2-2 두번째 문제 자바 코드 버전

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 선분의 개수 읽기
        int length = scanner.nextInt();
        scanner.nextLine(); // 줄바꿈 문자 처리
       
        // 최소 범위와 최대 범위를 저장할 변수
        int minRange = Integer.MAX_VALUE;
        int maxRange = Integer.MIN_VALUE;
      
        // 선분의 시작점과 끝점을 저장할 배열
        int[][] lines = new int[length][2];
      
        // 선분 입력 받기
        for (int i = 0; i < length; i++) {
            String line = scanner.nextLine();
            String[] parts = line.split(" ");
            int startPoint = Integer.parseInt(parts[0]);
            int endPoint = Integer.parseInt(parts[1]);
            lines[i] = new int[]{startPoint, endPoint};
          
            if (startPoint < minRange) minRange = startPoint;
            if (endPoint > maxRange) maxRange = endPoint;
        }
       
        // 배열 크기 계산 (오프셋을 고려하여 배열 생성)
        int[] overlapArray = new int[maxRange - minRange + 1];

        // 각 선분의 시작점부터 끝점까지 배열 값 증가
        for (int[] line : lines) {
            int startPoint = line[0];
            int endPoint = line[1];
            for (int i = startPoint; i <= endPoint; i++) {
                overlapArray[i - minRange]++;
            }
        }
       
        // 배열에서 최대값 찾기
        int max = Arrays.stream(overlapArray).max().orElse(0);

        // 결과 출력
        System.out.println(max);
      
        scanner.close();
    }
}

2. 자바와 자바스크립트 풀이 차이점

1. JS의 경우 배열은 쉽게 생성 및 접근이 가능해서 크게 걱정도 없었고, 구조 분해 할당도 지원해서 for-of를 쓸때나 for문을 쓸 때 되게 편했는데 자바는 그런거 없고 되게 불편하게 배열을 생성하고 접근을 해야되서 괴에에에에에에에엥장히 불편했습니다.

2. JS의 경우 오름차순 뿐만 아니라 내림차순도 쌉가능인데 자바는 내림차순의 경우 스트림을 이용하거나 직접 로직을 짜야되서... 참.... 코테는 역시 JS가 손에 익은 것 같다고 느껴졌네요.

최근에 학원 과제로 신경을 못쓰다가 다시 코테를 풀기 시작했는데 반성되네요... ㅎ...

그래도 기초 과정은 거의 다 풀었으니 이제 알고리즘을 슬슬 시작 해볼까 합니다...! (응? 그럼 여태까지 어떻게 풀고 있던거지...?)