[21주차_금요일] 선 긋기

[KodaHye]

• 사이트: 백준(BOJ)
• 문제: 선 긋기
• 번호: 2170

### 🤔 시간복잡도 고려사항



### 💡 풀이 아이디어

[KodaHye]

🤔 시간복잡도 고려사항

• 1 ≤ 선을 그은 횟수 ≤ 1,000,000
• NlogN으로 풀이할 수 있음

💡 풀이 아이디어

우선순위 큐에 선분들을 입력받고 그어진 선의 총 길이 구하기

변수	설명
Point.class	시작점(s)과 끝점(e`) 저장 1. 시작점 오름차순, 2. 끝점 오름차순 정렬
final int MIN, MAX	좌표에서 가능한 최솟값과 최댓값

1. 우선순위 큐에 선분들 입력받기

   // 우선순위큐에 점들 넣어주기
   for(int i = 0; i < N; i++) {
   	st = new StringTokenizer(br.readLine());
   	
   	int s = Integer.parseInt(st.nextToken());
   	int e = Integer.parseInt(st.nextToken());
   	
   	pq.add(new Point(s, e));
   }

2. 입력 후에 우선순위 큐에 시작과 끝이 MAX + 1 인 선분(점) 추가해주기

   // 마지막 선분에 대한 길이를 구하기 위함
   // (MAX, MAX) 로 넣으면 마지막에 넣은 점이 MAX일 때, 올바른 정답이 안나옴
   pq.add(new Point(MAX + 1, MAX + 1));

3. 큐에 있는 선분들을 꺼내고, 시작점과 끝점을 비교하면서 가능한 선분의 최대 길이 구하기

   while(!pq.isEmpty()) {
   	Point current = pq.poll();
   	
   	// 현재 시작점이 이전까지 확인한 지점들의 끝점보다 크면
   	// 이전 점들을 이어서 만들어진 선분의 길이 더해주기
   	if(end < current.s) {
   		result += end - start;
   		
   		start = current.s;
   		end = current.e;
   		
   	} else {
   		end = Math.max(end, current.e);
   	}
   }

[yeongleej]

🤔 시간복잡도 고려사항

• 선을 긋는 횟수 : N ≤ 1,000,000

=> 최대 O(NlogN)까지 가능
=> 정렬 활용 가능

💡 풀이 아이디어

• x를 기준으로 정렬 -> 뒤에오는 것들은 모두 시작값 s보다 x가 작음(y값만 신경쓰면됨)
• 0번째를 기준값 s, e로 설정
• 나머지 선들을 반복
  • 기준값과 겹치는 경우 => now.x가 e보다 작거나 같은 경우
    • e값만 갱신
  • 기준값과 겹치지 않는 경우
    • 현재까지의 기준 선 저장하고,
    • s, e 모두 업데이트

  	Collections.sort(pList);
  	
  	int s = pList.get(0).x;
  	int e = pList.get(0).y;
  	int ans = 0;
  	for(int i=1; i<N; i++) {
  		Pos now = pList.get(i);
  		
  		// now.x가 end보다 작다면 겹침 -> end 갱신
  		if(e >= now.x) {
  			e = Math.max(e, now.y);
  		}
  		// 겹치지 않는 경우
  		else {
  			// 기존것 더해주고 새로 업데이트
  			ans += (e - s);
  			s = now.x;
  			e = now.y;
  		}
  	}
  	ans += (e - s);

[jewan100]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 1,000,000 → 10^6이므로 O(N logN)까진 가능

💡 풀이 아이디어

• 기본적인 스위핑 문제
• 입력 받은 좌표들을 시작 지점 기준으로 오름차순 정렬
• 좌표를 순회하면서 현재 선분의 시작 지점이 이전 선분들의 끝 지점 이하일 경우, 하나의 선분으로 취급 가능
• 현재 선분이 이전 선분들의 끝 지점을 넘어설 경우 새로운 선분의 시작

Arrays.sort(arr, (o1, o2) -> o1[0] - o2[0]); // 시작 지점 기준으로 오름차순 정렬
int totalLen = 0, sPos = arr[0][0], ePos = arr[0][1]; // 초기화
for (int i = 1; i < n; i++) {
    // 현재 선분이 포함되는 선분일 경우
    if (arr[i][0] <= ePos) {
        sPos = Math.min(sPos, arr[i][0]);
        ePos = Math.max(ePos, arr[i][1]);
    } else {
        totalLen += ePos - sPos;
        sPos = arr[i][0];
        ePos = arr[i][1];
    }
}
totalLen += ePos - sPos; // 마지막 남은 값 계산
System.out.println(totalLen);

원래 스위핑은 우선 순위 큐로 푸는데, 이거는 그냥 선분 이어주면 되는거라 간단하게 풀었습니다!

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 1,000,000
  • 10^6, O(NlogN)이내로 풀기

💡 풀이 아이디어

• 정렬, 우선순위 큐
  • 시작지점으로 정렬 후 겹침여부 판별해서 선분 업데이트
  • 겹침 → 기존 끝과 현재 끝 중 큰 값으로 업데이트
  • 안겹침 → 새로운 선분 시작 (정렬해놨기에 더 큰 값이 들어온거임)
    • 지금까지의 길이 더해주기
    • 시작, 끝 값 새로운 값으로 업데이트

Node first = pq.poll();
int start = first.s;
int end = first.e;
int cnt = 0;

while (!pq.isEmpty()) {
    Node cur = pq.poll();
    if (start <= cur.s && cur.s <= end) {   // 현재 선분이랑 겹칠 경우
        end = Math.max(end, cur.e);         // 더 큰 끝값으로 업데이트
        continue;
    }

    // 겹치지 않음 (== 새로운 선분 시작)
    cnt += end - start;     // 지금까지의 선분 길이 더해주기
    start = cur.s;
    end = cur.e;
}
cnt += end-start;   // 마지막 선분 길이 업데이트

System.out.println(cnt);