[BOJ] 백준 7578번 : 공장 (JAVA)

문제

어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블로 연결되어 있다. 즉, A열의 임의의 기계는 B열의 유일한 기계와 케이블로 연결되어 있고, B열의 임의의 기계는 A열의 유일한 기계와 케이블로 연결되어 있다.

 

또한, 각 기계에는 식별번호가 붙어있으며, 짝이 맺어진 기계끼리는 같은 식별번호가 붙어있다. 즉, 각 열에 있는 N개의 기계끼리는 서로 다른 식별번호를 가지고 있으며, 반대쪽 열에 있는 같은 식별번호를 가진 기계와 케이블로 이어져 있다.

 

공장 작업의 효율성을 위해 기계들은 짝을 맺은 순서대로 배치되지 않으며, 필요에 따라 각 열의 기계들의 순서를 바꾼 바람에 케이블은 마구 엉켜있는 상태이다. 이렇게 엉켜버린 케이블은 잦은 고장의 원인이 되기 때문에, 기계의 위치를 바꾸지 않은 상태에서 케이블을 두 기계를 잇는 직선의 형태로 만들기로 했다.

 

 

 

 

예를 들어, 위의 그림과 같이 N = 5이고, A열에 위치한 기계의 식별번호가 순서대로 132, 392, 311, 351, 231이고 B열에 위치한 기계의 식별번호가 순서대로 392, 351, 132, 311, 231이라면 케이블들의 교차 횟수 혹은 서로 교차하는 케이블 쌍의 개수는 3이 된다.

 

정수 N과 A열에 위치한 기계, B열에 위치한 기계의 식별번호가 각각 순서대로 주어질 때에 서로 교차하는 케이블 쌍의 개수를 정확하게 세어 출력하는 프로그램을 작성하시오.

 

 

입력

입력은 세 줄로 이루어져 있다. 첫 줄에는 정수 N이 주어지며, 두 번째 줄에는 A열에 위치한 N개 기계의 서로 다른 식별번호가 순서대로 공백문자로 구분되어 주어진다. 세 번째 줄에는 B열에 위치한 N개의 기계의 식별번호가 순서대로 공백문자로 구분되어 주어진다.

 

단, 1 ≤ N ≤ 500,000이며, 기계의 식별번호는 모두 0 이상 1,000,000 이하의 정수로 주어진다

 

 

출력

여러분은 읽어 들인 2N개의 기계의 배치로부터 서로 교차하는 케이블 쌍의 개수를 정수 형태로 한 줄에 출력해야 한다.

 

 

풀이

세그먼트 트리와 해쉬 맵을 사용하여 풀 수 있는 문제였습니다.

 

자세한 설명은 문제의 예시를 통해서 전개해 보도록 하겠습니다.

 

 

 

 

문제의 예시를 그림으로 살펴보면, 위와 같은 형태일 것입니다.

첫번 째 줄에 있는 식별 번호를 두번 째 줄에 있는 동일한 식별 번호를 계속해서 이어주면서 겹치는 선의 개수를 구하는 것이 핵심이었습니다.

 

 

 

 

첫번 째 줄에 132와 두번 째 줄에 132를 서로 이어줍니다. 그리고 두번 쨰 줄에 132 뒤에 있는 311과 231 중에 이미 방문한 적이 있는지 체크합니다. 311과 231은 방문한 적이 없으므로 겹치는 선이 없음을 의미합니다.

그리고 132가 있는 곳을 방문했다는 의미로 1을 표시해 줍니다.

 

 

 

 

첫번 째 줄에 392와 두번 째 줄에 392를 서로 이어줍니다. 그리고 392 뒤에 있는 351, 132, 311, 231 중에 방문한 적이 있는 식별번호를 찾습니다. 보니까 식별번호 132가 방문한적이 있습니다. 따라서 겹치는 선이 1개 발생한 것이므로 ans에 1을 더해줍니다.

마지막으로, 392가 있는 곳을 방문했다는 의미로 1을 표시해 줍니다.

 

 

 

 

 

첫번 째 줄에 311과 두번 째 줄에 311을 이어줍니다. 식별번호 231은 방문한 적이 없으므로 겹치는 선이 없습니다.

따라서 311이 있는 곳을 방문했다는 의미로 1을 표시해 줍니다.

 

 

 

 

첫번 째줄에 351과 두번 째 줄에 351을 서로 이어줍니다. 132, 311, 231 중에 방문한 식별번호가 132, 311로 2개이므로 겹치는 선이 2개 있음을 의미합니다. 따라서 ans에 2를 더해 줍니다.

마지막으로, 351을 방문했다는 의미로 1을 표시해 줍니다.

 

 

 

 

231은 마지막 점이기때문에 겹치는 선은 없습니다. 이것으로 서로의 식별 번호를 모두 찾아 주었고, 겹치는 선은 1 + 2 = 3개 라는 사실을 알 수 있습니다.

 

 

위 과정에서 세그먼트 트리를 사용한 이유는 간단합니다. [i + 1, N] 구간의 방문한 식별번호의 개수의 합을 구하기 위해서죠. 또한, 특정 점이 방문한 점으로 바뀔 때마다 tree[i] = 0 에서 tree[1]로 바뀌는 동시에 i와 관련된 구간 합을 모두 업데이트 해 주어야하므로 세그먼트 트리를 사용하는 것이 편리합니다.

 

또한, 해쉬 맵을 사용하는 이유는 A[1], A[2], ... , A[N] 과 대응하는 B[1], B[2], ... , B[N]을 찾기 위함입니다.

(A는 첫번 째 줄의 식별 번호, B는 두번 째 줄의 식별 번호를 의미합니다.) 

 

예를 들어, A = { 132, 392, 311, 351, 231 } 이고, B = { 392, 351, 132, 311, 231 } 이라고 해 봅시다.

인덱스는 1부터 시작한다고 가정하면, A[1]에 대응하는 B의 인덱스를 찾아야 합니다.

 

A는 입력값을 순서대로 받은 후, B의 입력값은 Key가 식별번호, Value가 인덱스인 해쉬맵을 정의해 주면 됩니다.

B의 입력값을 순서대로 받으면 해쉬맵 MapB는 다음과 같은 entry를 갖게 될 것입니다.

 

{392, 1}, {351, 2}, {132, 3}, {311, 4}, {231, 5}

 

만약, A[1] = 132와 대응하는 점을 찾으려면, MapB.get(A[1])을 사용하여 3이라는 인덱스를 얻어낼 수 있습니다.

실제로 B[3] = 132이므로 올바른 인덱스를 찾았다는 사실을 알 수 있습니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.