정류장이 1번부터 n번까지 차례로 있는 버스 노선이 있다. 버스는 1번 정류장에서 n번 정류장까지 한 번 달린다.
i번 정류장에서 i+1번 정류장까지 가는 길을 i번 구간이라 한다(1 ≤ i ≤ n − 1).
승객 m명이 있고, 승객마다 두 정수 a, b가 주어진다. 이 승객은 a번 정류장에서 타서 b번 정류장에서 내린다(a < b).
그래서 이 승객은 a번 구간부터 b − 1번 구간까지 버스에 있다. b번 정류장에서 다른 사람이 타더라도, 내린 사람은 b번 구간에 없다.
구간마다 버스에 있던 사람 수를 셌을 때 가장 많은 사람 수를 구하라.
사람 수가 그 가장 많은 수인 구간 가운데 가장 작은 번호와 가장 큰 번호도 구하라. 그런 구간이 하나뿐이면 두 번호는 같다.
가장 많은 사람 수, 가장 작은 번호, 가장 큰 번호를 빈칸 하나씩 띄워 한 줄에 출력하라.
첫 줄에 n과 m이, 다음 m줄에 승객마다 a와 b가 빈칸으로 나뉘어 주어진다.
입력
2 ≤ n ≤ 9,999, 1 ≤ m ≤ 10,000, 1 ≤ a < b ≤ n(모두 정수)
출력
한 줄: 가장 많은 사람 수, 그 수인 구간의 가장 작은 번호, 가장 큰 번호
예시 1 · stdin
5 4
1 3
2 5
3 4
4 5
stdout
2 2 4
예시 2 · stdin
4 3
1 2
2 3
3 4
stdout
1 1 3
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
승객마다 a번부터 b − 1번 구간까지 하나씩 더하면 최악에 10,000명 × 9,998구간, 약 1억 번이라 Python·크레이콘은 너무 느려요. 대신 차이 목록을 써요. 승객마다 diff[a] += 1, diff[b] -= 1만 적고, 1번 구간부터 앞에서부터 더해 가면(누적 합) 그 값이 그 구간의 사람 수예요. 빼는 자리가 함정이에요. b번 정류장에서 내리니 b번 구간부터 빼야 하고, diff[b + 1]에서 빼면 내린 사람이 한 구간 더 타고 가요. b는 n까지 오니 목록은 n + 1칸이 필요해요. Java new int[n]은 ArrayIndexOutOfBoundsException, C#은 IndexOutOfRangeException이고, C는 오류 없이 배열 밖에 써요. JS·TS new Array(n + 1)은 빈 칸뿐이라 += 1이 NaN이 되니 .fill(0)을 붙여요. Python [0] * (n + 1), C++ std::vector<int>(n + 1, 0), 크레이콘 새목록(n + 1, 0), Java·C#의 int[]는 처음부터 0이에요. 첫 구간과 마지막 구간을 한 번에 찾으려면 더 커질 때(>)만 첫 구간을 바꾸고, 같을 때(==)는 마지막 구간만 바꿔요.
Pythonmain.py · 20 줄
import sysdata = sys.stdin.buffer.read().split()n, m = int(data[0]), int(data[1])# 차이 목록: a번 구간부터 한 명 늘고, b번 구간부터 한 명 준다(b번 정류장에서 내리니까)diff = [0] * (n + 1)for k in range(m): a, b = int(data[2 + 2 * k]), int(data[3 + 2 * k]) diff[a] += 1 diff[b] -= 1load = 0best, first, last = -1, 0, 0for i in range(1, n): # i번 구간: i번 → i+1번 정류장 load += diff[i] # 앞에서부터 더하면 그 구간에 있는 사람 수 if load > best: best, first, last = load, i, i elif load == best: last = iprint(best, first, last)
JavaScriptmain.js · 15 줄
const nums = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = nums;// fill(0)이 없으면 빈 칸이라 += 1이 NaN이 된다const diff = new Array(n + 1).fill(0);for (let k = 0; k < m; k++) { diff[nums[2 + 2 * k]] += 1; diff[nums[3 + 2 * k]] -= 1;}let load = 0, best = -1, first = 0, last = 0;for (let i = 1; i < n; i++) { load += diff[i]; if (load > best) [best, first, last] = [load, i, i]; else if (load === best) last = i;}console.log(`${best} ${first} ${last}`);
TypeScriptmain.ts · 15 줄
import { readFileSync } from "node:fs";const nums: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = nums;const diff: number[] = new Array<number>(n + 1).fill(0);for (let k = 0; k < m; k++) { diff[nums[2 + 2 * k]] += 1; diff[nums[3 + 2 * k]] -= 1;}let load = 0, best = -1, first = 0, last = 0;for (let i = 1; i < n; i++) { load += diff[i]; if (load > best) [best, first, last] = [load, i, i]; else if (load === best) last = i;}console.log(`${best} ${first} ${last}`);
JavaMain.java · 38 줄
import java.io.DataInputStream;import java.io.IOException;public class Main { static DataInputStream in = new DataInputStream(System.in); static int readInt() throws IOException { int c = in.read(); while (c < '0') c = in.read(); int r = 0; while (c >= '0') { r = r * 10 + (c - '0'); c = in.read(); } return r; } public static void main(String[] args) throws IOException { int n = readInt(), m = readInt(); int[] diff = new int[n + 1]; // b는 n까지 오니 n + 1칸 for (int k = 0; k < m; k++) { int a = readInt(), b = readInt(); diff[a]++; diff[b]--; } int load = 0, best = -1, first = 0, last = 0; for (int i = 1; i < n; i++) { load += diff[i]; if (load > best) { best = load; first = last = i; } else if (load == best) { last = i; } } System.out.println(best + " " + first + " " + last); }}
C#Main.cs · 25 줄
using System;using System.IO;class Program{ static void Main() { string[] t = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(t[0]), m = int.Parse(t[1]); var diff = new int[n + 1]; for (int k = 0; k < m; k++) { diff[int.Parse(t[2 + 2 * k])]++; diff[int.Parse(t[3 + 2 * k])]--; } int load = 0, best = -1, first = 0, last = 0; for (int i = 1; i < n; i++) { load += diff[i]; if (load > best) { best = load; first = last = i; } else if (load == best) last = i; } Console.WriteLine($"{best} {first} {last}"); }}
C++main.cpp · 27 줄
#include <iostream>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<int> diff(n + 1, 0); for (int k = 0; k < m; k++) { int a, b; std::cin >> a >> b; diff[a]++; diff[b]--; } int load = 0, best = -1, first = 0, last = 0; for (int i = 1; i < n; i++) { load += diff[i]; if (load > best) { best = load; first = last = i; } else if (load == best) { last = i; } } std::cout << best << " " << first << " " << last << "\n";}
Cmain.c · 25 줄
#include <stdio.h>static int diff[10000];int main(void) { int n, m, a, b; scanf("%d %d", &n, &m); for (int k = 0; k < m; k++) { scanf("%d %d", &a, &b); diff[a]++; /* a번 구간부터 한 명 늘고 */ diff[b]--; /* b번 정류장에서 내리니 b번 구간부터 준다 */ } int load = 0, best = -1, first = 0, last = 0; for (int i = 1; i < n; i++) { load += diff[i]; if (load > best) { best = load; first = last = i; } else if (load == best) { last = i; } } printf("%d %d %d\n", best, first, last); return 0;}
Craykonmain.cray · 30 줄
first = 콘솔.수들읽기();n = first[0];m = first[1];// 차이 목록: a번 구간부터 한 명 늘고, b번 구간부터 한 명 준다diff = 새목록(n + 1, 0);반복 (k = 0; k < m; k++){ p = 콘솔.수들읽기(); diff[p[0]] += 1; diff[p[1]] -= 1;}load = 0;best = -1;from = 0;to = 0;반복 (i = 1; i < n; i++){ load += diff[i]; 만약 (load > best) { best = load; from = i; to = i; } 아니면 만약 (load == best) { to = i; }}콘솔.쓰기(best + " " + from + " " + to);