[백준] 알고리즘 분류(자료구조,JAVA)13334번, 철로

문제 링크

13334번: 철로

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 집과 사무실은 수평선 상에 존재합니다.

2. 한 명의 집의 위치가 다른 사람의 사무실 위치와 동일할 수 있습니다.

3. 철로의 길이 d가 주어질 때 집과 사무실이 모두 포함되는 사람의 최대값을 결과로 출력합니다

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 우선순위 큐를 이용하여 철로를 놓았을 때 집과 사무실이 포함된 인원들을 탐색합니다.

 

3. 탐색이 종료한 뒤 얻은 최대 인원을 결과로 출력합니다.

 

 

우선순위 큐으로 탐색!

선분이 주어지는 경우

철로를 놓을 수 있는 구간 : 사람들의 집, 사무실 위치 중 더 적은 위치

파란색 실선 : 철로의 시작점을 놓을 수 있는 위치!

 

 

철로의 시작 위치가 작은 것부터 놓기 시작합니다.

 

철로를 놓을 때에는 현재 사람이 조건에 만족하면 PriorityQueue에 저장합니다.

 

PriorityQueue에 저장된 Size가 현재 조건에 만족하는 사람의 수입니다.

 

다음 철로의 끝 위치를 탐색할 때에는 PriorityQueue에 저장된 값들이 조건에 만족하는지 확인

 

만족하지 못한다면 poll()을 진행하여 PriorityQueue의 사이즈를 조절하도록 진행합니다.

 

위 과정을 반복하여 PriorityQueue의 Size가 가장 큰 값이었을 때개 최대 인원입니다.

 

위 그림에서 시작 위치가 30일 때

진행되는 과정은 예제입력이 진행되는 과정을 살펴보시면 이해하시기 편하실 것입니다.

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N : 4

D : 10

 

 

2. 우선순위 큐를 이용하여 철로를 놓았을 때 집과 사무실이 포함된 인원들을 탐색합니다.

 

철로를 놓을 수 있는 구간 : 사람들의 집, 사무실 위치 중 더 적은 위치

파란색 실선 : 철로의 시작점을 놓을 수 있는 위치!

 

시작 위치 기준 탐색

: 0개

: 0개

 

: 0개

 

: 0개

 

※ 이번 예제에서는 시작하는 선분이 D보다 클 때도 탐색을 하였지만 실제로 코드에서는 해당 선분은 절대 포함할 수 없기 때문에 탐색을 넘깁니다.

 

3. 탐색이 종료한 뒤 얻은 최대 인원을 결과로 출력합니다.

 

0개 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 집과 오피스의 위치를 띄어쓰기 기준 나누었습니다.
• 집과 오피스 위치를 기준으로 데이터를 저장한 뒤 정렬을 진행하였습니다.
• 각 선분 시작위치에 철로가 설치되는 경우를 탐색합니다.
• 탐색이 끝난 뒤 얻은 최대 인원을 System.out.print()을 통해 출력하였습니다.

 

결과코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    //선분 정보 관련 클래스
    static class Road implements Comparable<Road>{
        int s, e;	//s : 시작 위치,  e : 끝나는 위치
        public Road(int s, int e) {
            this.s = s;
            this.e = e;
        }
        @Override
        //끝나는 위치 기준 오름차순, 끝나는 위치가 동일할 때에는 시작위치 오름차순
        public int compareTo(Road o) {
            if(this.e == o.e)
                return this.s - o.s;
            return this.e - o.e;
        }
    }
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        List<Road> roads = new ArrayList<>();
        //철로 정보 저장
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine()," ");
            int h = Integer.parseInt(st.nextToken());
            int o = Integer.parseInt(st.nextToken());
            if(h <= o)	//집의 위치가 오피스 위치보다 작을 때
                roads.add(new Road(h, o));
            else	//오피스 위치가 집의 위치보다 작을 때
                roads.add(new Road(o, h));

        }
        int L = Integer.parseInt(br.readLine());
        Collections.sort(roads);	//선분 정렬 진행!
        //현재 철로에 포함되는 인원 저장 우선순위 큐
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int result = 0;
        //각 철로 시작위치에서 탐색
        for(Road road : roads) {
            if(road.e - road.s > L)		//현재 선분의 길이가 D보다 클 때
                continue;	//해당 선분은 절대 포함될 수 없기에 넘기기
            pq.offer(road.s);	//현재 선분 철로 그룹에 포함
            //철로 그룹에 현재 선분에 포함되지 않는 선분들 제거
            while(!pq.isEmpty()) {
                if(road.e - pq.peek() <= L)
                    break;
                pq.poll();
            }
            result = Math.max(result, pq.size());	//최대값 비교
        }	
        System.out.print(result);		//결과 출력

    }
}