[백준]15922번 아우으 우아으이야!! 문제 풀이

문제

 

이미지를 클릭하면 문제 링크로 이동합니다

 

풀이 

고려해야할 점

 

• 선분의 겹침 처리: 여러 개의 선분이 주어졌을 때, 겹치는 부분을 제외하고 전체 선분의 총 길이를 구해야 합니다.
• 입력 순서: 선분들이 입력되는 순서가 정렬되어 있지 않을 수 있으므로, 시작점 기준으로 선분들을 정렬할 필요가 있습니다.
• 데이터 타입: 좌표의 범위가 매우 크거나 작을 수 있으므로, 오버플로우를 방지하기 위해 적절한 데이터 타입(long)을 사용해야 합니다.

 

 

문제 풀이 아이디어

 

• 선분 정렬: 시작점 기준으로 선분들을 정렬하여 겹치는 부분을 효율적으로 처리할 수 있도록 합니다.
• 현재 선분의 범위 추적:
  • 변수 l과 r을 사용하여 현재까지의 유효한 선분의 시작점과 끝점을 추적합니다.
  • 초기값으로 l은 가장 작은 값(Integer.MIN_VALUE)으로 설정하고, r은 총 길이를 저장하는 변수로 사용합니다.
• 겹치는 경우의 처리:
  • 겹치지 않는 경우 (a >= l):
    • 현재 선분이 이전 선분과 겹치지 않으므로, 선분의 길이 (b - a)를 총 길이에 더합니다.
    • l을 현재 선분의 끝점 b로 업데이트합니다.
  • 부분적으로 겹치는 경우 (a < l이고 b > l):
    • 현재 선분이 이전 선분과 일부 겹치므로, 겹치지 않는 부분의 길이 (b - l)를 총 길이에 더합니다.
    • l을 현재 선분의 끝점 b로 업데이트합니다.
  • 완전히 겹치는 경우:
    • 현재 선분이 이전 선분에 완전히 포함되면 추가적인 처리가 필요 없습니다.

 

 

 

코드

import java.io.*;
import java.util.*;

public class BOJ15922_아우으우아으이야 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 선분의 개수를 입력받습니다.
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        
        // 현재 선분의 끝점을 저장할 변수 l과 총 길이를 저장할 변수 r을 초기화합니다.
        long l = Integer.MIN_VALUE, r = 0;
        
        for(int i = 0; i < n; i++) {
            // 각 선분의 시작점(a)과 끝점(b)을 입력받습니다.
            st = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());
            
            if(a >= l) {
                // 현재 선분이 이전 선분과 겹치지 않는 경우
                r += (b - a); // 선분의 길이를 총 길이에 더합니다.
                l = b;        // 현재 선분의 끝점을 업데이트합니다.
            }
            else if (b >= l) {
                // 현재 선분이 이전 선분과 일부 겹치는 경우
                r += b - l;   // 겹치지 않는 부분의 길이를 더합니다.
                l = b;        // 현재 선분의 끝점을 업데이트합니다.
            }
            // 현재 선분이 이전 선분에 완전히 포함되는 경우는 처리하지 않습니다.
        }
        // 총 길이를 출력합니다.
        System.out.print(r);
    }
}