6485. 삼성시의 버스 노선 (D3)

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWczm7QaACgDFAWn

각 버스의 노선 정보가 주어지고 입력되는 정류장 번호에 따라 해당 정류장이 포함된 노선의 개수를 출력하는 간단한 문제이다.

<입력>

노선의 개수 N (1<=N<=5,000)

각 노선의 출발점과 도착점

원하는 정류장의 개수 P

정류장 번호 P개

<출력>

P개의 정류장들을 지나는 노선의 개수

<풀이>

간단한 아이디어를 사용했다.

정류장의 번호를 인덱스로 가지는 배열 arr을 만든다.

각 노선을 입력받을 때마다 arr[출발점]의 값을 1 늘리고 arr[도착점+1]의 값을 1 내린다.

이 과정을 수행할 경우 다음과 같은 배열이 만들어진다.

ex) 노선 2개 ( 1, 3 ) ( 2, 4 )

(1) 1

(2) 1

(3) 0

(4) -1

(5) -1

이제 다음으로 count라는 변수를 만든 뒤 배열을 앞에서부터 탐색하며

해당 칸에서 만나는 숫자를 더하고 count로 값을 바꿔줄 것이다.

(1) 1

(2) 2

(3) 2

(4) 1

(5) 0

이렇게 만들어진 배열은 각 정류소 번호 별로 지나는 노선의 개수를 나타내게 된다.

앞에서부터 새로운 노선의 시작점을 만날 경우 count를 1 늘려주고

노선의 종료점을 지날 경우 count를 1 감소시켜주는 것과 같은 결과를 보일 수 있다.

이제 P개의 입력을 받으며 해당 칸의 값을 출력해주기만 하면 된다.

---

- 소스 코드 -

A와 B는 각 노선의 시작점과 종료점을 저장한 배열이다.

이 문제에서는 필요가 없지만 혹시 추가로 시작점과 종료점의 값이 필요할 수 있으므로 배열을 통해 값을 저장해가며 문제를 해결했다.

#include<iostream>
 
using namespace std;
 
int main(void)
{
    int T;
 
    cin>>T;
 
    for (int test_case = 1; test_case <= T; test_case++) {
        int arr[5001] = { 0 };
        int N;
        cin >> N;
        int A[5000] = { 0 };
        int B[5000] = { 0 };
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &A[i], &B[i]);
            arr[A[i] - 1]++;
            arr[B[i]]--;
        }
        int count = 0;
        for (int i = 0; i < 5000; i++) {
            count += arr[i];
            arr[i] = count;
        }
        int P;
        scanf("%d", &P);
        
        int out[500] = { 0 };
        for (int i = 0; i < P; i++) {
            scanf("%d", &out[i]);
        }
        printf("#%d ", test_case);
        for (int i = 0; i < P; i++) {
            printf("%d ", arr[out[i] - 1]);
        }
        printf("\n");
        
    }
}

---