[SWEA][D3][#06485] 삼성시의 버스 노선

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

삼성시에 있는 5,000개의 버스 정류장은 관리의 편의를 위해 1에서 5,000까지 번호가 붙어 있다.

그리고 버스 노선은 N개가 있는데, i번째 버스 노선은 번호가 Ai이상이고,

Bi이하인 모든 정류장만을 다니는 버스 노선이다.

P개의 버스 정류장에 대해 각 정류장에 몇 개의 버스 노선이 다니는지 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N ( 1 ≤ N ≤ 500 )이 주어진다.

다음 N개의 줄의 i번째 줄에는 두 정수 Ai, Bi ( 1 ≤ Ai ≤ Bi ≤ 5,000 )가 공백 하나로 구분되어 주어진다.

다음 줄에는 하나의 정수 P ( 1 ≤ P ≤ 500 )가 주어진다.

다음 P개의 줄의 j번째 줄에는 하나의 정수 Cj ( 1 ≤ Cj ≤ 5,000 ) 가 주어진다.

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고 한 칸을 띄운 후, 한 줄에 P개의 정수를 공백 하나로 구분하여 출력한다.

j번째 정수는 Cj번 버스 정류장을 지나는 버스 노선의 개수여야 한다.

예제

입력

1      //테스트 케이스 개수
2      //첫 번째 테스트 케이스, N=2
1 3    // A1 = 1, B1 = 3
2 5    // A2 = 2, B2 = 5
5      // P = 5
1      // 이하 C1 = 1, C2 = 2, C3 = 3, C4 = 4, C5 = 5
2
3
4
5

출력

#1 1 2 2 1 1  //첫 번째 테스트 케이스 결과

My Sol

T = int(input())
for tc in range(1, T+1):
    print(f'#{tc}', end=' ')

    temp = [0]*5001
    N = int(input())

    for i in range(N):
        A, B = map(int, input().split())
        for j in range(A, B+1):
            temp[j] += 1

    P = int(input())
    for k in range(P):
        bs = int(input())
        print(temp[bs], end=' ')

    print()

문제 자체를 이해하는데 꽤나 시간이 걸렸던 문제이다. 문제를 해석하자면, 테스트 케이스마다 먼저 다니는 버스의 대수 N을 입력한다. 그리고 N개의 버스들의 구간 정보를 입력하는데, 처음 나오는 수가 시작하는 종점, 그리고 다음 수가 끝나는 종점이다. 이를 N개만큼 받는다.

그리고 다음은 정류장의 번호를 조회한다. 이 개수가 총 P개이며, 먼저 몇 개의 정류장을 조회할 것인지 입력하고 이후에 정류장 번호를 써내려가는 것이다.

버스 구간에 대한 정보가 먼저 나오기 때문에 5000번까지 있는 버스정류장에 대해서 각각 다니는 버스의 대수를 먼저 구해줄 것이다. 즉, 버스정류장에 대한 리스트를 만드는 것이다. 그래서 최초에 다니는 버스가 모두 없다고 생각하는 temp 리스트를 0을 5001개 넣어 초기화하였다. 5001개인 이유는 0번 index 때문에 배열이 틀어지는 것을 고려해, index 표기의 편의상 넣었다. 0번 버스정류장을 구간으로 하는 버스는 없다.

그리고 각각의 버스들에 대하여 for문을 돌리는데, 구간 정보가 들어오면 이를 처리해서 구간에서 구간만큼 temp 리스트에 1을 더하는 것이다. 그러면 구간에 있는 버스정류장에 버스 하나가 지나간다는 표시를 해주는 것이다. 버스마다 이렇게 구간에 대한 처리를 해주며 for문을 마친다.

이후 버스 정류장을 조회하는데, P개의 버스 정류장을 조회하므로 P번 반복을 진행하는 for문이 필요하다. 그리고 그 반복의 내부에서 입력을 받는데 입력 받은 번호에 해당하는 버스 정류장에 다니는 버스 수는 곧, 해당 버스 정류장 번호를 index로 하는 temp 배열 변수의 항목 값이다. 이를 출력하면 된다.

처음에는 리스트에 담아서 출력할까 하다가, 처음에 테스트 케이스 #? 을 먼저 출력해놓고 리스트 저장 없이 하나씩 출력하며 공백을 기준으로 늘어놓으면 되겠다고 생각했다. 별도의 리스트 저장이 없이 출력이 가능하다.

테스트 케이스의 모든 작업을 마치면 print() 문 하나를 넣어 다음 테스트 케이스 이전에 개행을 하여 다음 테스트 케이스 입력을 받을 준비를 하면 되겠다.

결과

PASS