BaekJoon
[BaekJoon] 2568번 전깃줄 - 2 (Java) 문제 풀이 [Platinum 5]
문제 https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 어떻게 풀 것인가? 문제를 천천히 읽어보자. 두 전봇대 사이 A와 B에서 교차를 하면 안된다. 여기서 단순 구현이라기엔 시간제한 1초이며, 주어진 데이터(전깃줄의 개수)는 100,000 이하의 자연수이다. 브루트포스로 푼다면 1초를 훌쩍 넘긴다. 문제에서 주어진 두 전봇대에 주어진 숫자를 하나의 기준으로 정렬을 해본다면, 인덱스와 값이 보인다. 즉, 가장 긴 오름차순 수열이 아닌 것들을 ..
