[백준] 7578번 공장 문제 풀이

풀이 고려해야할 점더보기입력 값의 크기가 최대 500,000이므로 시간 복잡도를 고려하면 O(nlogn) 이내로 해결해야 한다.  연결되는 기계의 번호를 기준으로 연결되는 기계의 위치를 저장해야 한다. 문제의 핵심 포인트 더보기첫 번째 줄의 인덱스를 기준으로 두 번째 줄 입력을 인덱스화하여 배열을 생성한다. 두 번째 줄 입력에서 역순으로 정렬되어 있는 쌍들의 개수를 구한다. 케이블이 교차한다는 것은 기계의 위치가 역순으로 존재하는 것이 존재한다는 의미이다.  문제 해결 아이디어 더보기병합 정렬을 하면서 역순으로 정렬된 기계의 개수를 센다. (nlogn)또 다른 방법으로 세그먼트 트리를 응용하여 문제를 해결할 수 있다.  코드import java.io.BufferedReader;import java.io...
알고리즘/코딩테스트 2024. 10. 28. 13:20
1