10165 KOI 2014_Elementary

์•Œ๊ณ ๋ฆฌ์ฆ˜

1. ๊ฐ ๋ฒ„์Šค๋…ธ์„ ์˜ ์ถœ๋ฐœ์ , ๋„์ฐฉ์ , ๋ฒˆํ˜ธ๋ฅผ ๊ธฐ๋กํ•œ ๊ตฌ์กฐ์ฒด๋ฅผ ๋งŒ๋“ค๊ณ , ์ถœ๋ฐœ์ ์„ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌ. ์ถœ๋ฐœ์ ์ด ๊ฐ™์œผ๋ฉด ๋„์ฐฉ์ ์ด ์ž‘์€ ๊ฒƒ์ด ์•ž์— ์œ„์น˜ํ•˜๋„๋กํ•จ.
2. ๋ฒ„์Šค๋…ธ์„ ์ธ๋ฑ์Šค๋ฅผ ์ €์žฅํ•˜๋Š” ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด, ๋ฒ„์Šค๋…ธ์„ ์„ ํ•˜๋‚˜์”ฉ ๊ฒ€์‚ฌํ•จ.
	-์ดˆ๊ธฐ : ์ฒซ๋ฒˆ์งธ ๋ฒ„์Šค๋…ธ์„ ์„ ๋„ฃ์Œ
3. ๊ฒ€์‚ฌ๋‚ด์šฉ
	-์ถœ๋ฐœ์ ์ด ์ด์ „ ๋ฒ„์Šค๋…ธ์„ ๊ณผ ๊ฐ™์€๊ฐ€
		-์ด์ „ ๋ฒ„์Šค๋…ธ์„ ์ด 0์„ ์ง€๋‚˜์น˜๊ณ , ํ˜„์žฌ ๋ฒ„์Šค๋…ธ์„ ๋„ 0์„ ์ง€๋‚˜์น˜๋Š”๊ฐ€	(์ •๋ ฌ๋กœ ์ธํ•ด ์ž๋™์œผ๋กœ ํ˜„์žฌ๋ฒ„์Šค๋…ธ์„ ์ด ์ด์ „๋ฒ„์Šค๋…ธ์„ ์„ ๊ฐ์‹ธ๋Š” ํ˜•ํƒœ๊ฐ€ ๋จ.)
			-ํ˜„์žฌ๋ฒ„์Šค ๋…ธ์„ ์„ ๋„ฃ์—ˆ์„ ๋•Œ ์ง€์›Œ์ง€๋Š” ๋…ธ์„ ์„ ์ „๋ถ€ ์ง€์›€
			-์ด์ „๋ฒ„์Šค๋…ธ์„ ๋„ ์ง€์›Œ์กŒ์œผ๋ฏ€๋กœ, ์ด์ „ ๋ฒ„์Šค๋…ธ์„ ์ธ๋ฑ์Šค ์œ„์น˜์— ํ˜„์žฌ ๋ฒ„์Šค๋…ธ์„ ์˜ ์ธ๋ฑ์Šค๋ฅผ ๋„ฃ์Œ
		-์ด์ „ ๋ฒ„์Šค๋…ธ์„ ์ด 0์„ ์ง€๋‚˜์น˜์ง€๋งŒ, ํ˜„์žฌ ๋ฒ„์Šค๋…ธ์„ ์€ 0์„ ์ง€๋‚˜์น˜์ง€ ์•Ÿ์Œ
			-ํ˜„์žฌ๋ฒ„์Šค๋…ธ์„  ์Šคํ‚ต
		-์ด์ „ ๋ฒ„์Šค๋…ธ์„ ์ด 0์„ ์ง€๋‚˜์น˜์ง€ ์•Š์Œ
			-์ด์ „ ๋ฒ„์Šค๋…ธ์„ ์„ ์ง€์šฐ๊ณ , ํ˜„์žฌ ๋ฒ„์Šค๋…ธ์„ ์„ ์ €์žฅ
	-์ถœ๋ฐœ์ ์ด ์ด์ „ ๋ฒ„์Šค๋…ธ์„ ๊ณผ ๋‹ค๋ฅธ๊ฐ€
		-ํ˜„์žฌ ๋ฒ„์Šค๋…ธ์„ ์ด 0์„ ์ง€๋‚˜์น˜๋Š”๊ฐ€
			-์ด์ „ ๋ฒ„์Šค๋…ธ์„ ์ด 0์„ ์ง€๋‚˜์น˜๊ณ , ํ˜„์žฌ ๋ฒ„์Šค๋…ธ์„ ์„ ๊ฐ์‹ธ๋Š”๊ฐ€
				-์Šคํ‚ต
			-๊ทธ ์™ธ
				-ํ˜„์žฌ๋ฒ„์Šค ๋…ธ์„ ์„ ๋„ฃ์—ˆ์„ ๋•Œ ์ง€์›Œ์ง€๋Š” ๋…ธ์„ ์„ ์ „๋ถ€ ์ง€์›€
				-์ด์ „ ๋ฒ„์Šค๋…ธ์„ ์ด ์ง€์›Œ์กŒ์œผ๋ฉด ์ด์ „ ์œ„์น˜์— ๋„ฃ๊ณ , ์•„๋‹ˆ๋ฉด ์ด์–ด์„œ ๋„ฃ์ž
		-ํ˜„์žฌ ๋ฒ„์Šค๋…ธ์„ ์ด 0์„ ์ง€๋‚˜์น˜์น˜ ์•Š๋Š”๊ฐ€
			-์ด์ „ ๋ฒ„์Šค๋…ธ์„ ์ด 0์„ ์ง€๋‚˜์น˜์ง€ ์•Š๊ณ , ํ˜„์žฌ ๋ฒ„์Šค๋…ธ์„ ์„ ๊ฐ์‹ธ์ง€ ์•Š์„ ๋•Œ
				-ํ˜„์žฌ ๋ฒ„์Šค๋…ธ์„ ์„ ์ด์–ด์„œ ๋„ฃ์Œ
			-๊ทธ ์™ธ ์Šคํ‚ต
4. ๊ฒ€์‚ฌ ๋๋‚˜๊ณ , ๋ฒ„์Šค๋…ธ์„  ์ธ๋ฑ์Šค๋“ค๋กœ๋ถ€ํ„ฐ ๋‚จ์€ ๋ฒ„์Šค๋…ธ์„ ์˜ ๋ฒˆํ˜ธ๋“ค์„ ์ถ”์ถœํ•˜๊ณ , ๋ฒˆํ˜ธ๋“ค์„ ์ •๋ ฌํ•˜์—ฌ ์ถœ๋ ฅ.

๋‹ค๋ฅธ ํ’€์ด๋ฒ•

1. 0๋ฒˆ ์ •๋ฅ˜์žฅ์„ ์•ˆ์ง€๋‚˜๋Š” ๊ทธ๋ฃน์„ A, ์ง€๋‚˜๋Š” ๊ทธ๋ฃน์„ B๋ผ๊ณ  ํ•˜์ž.
2. A๊ทธ๋ฃน ๋จผ์ € ๋‚ด ๋ฐฉ์‹๋Œ€๋กœ ์ •๋ ฌ ํ›„ ๊ฒน์น˜๋Š” ๊ฑฐ ์žˆ๋Š”์ง€ ํ™•์ธ ํ›„ ์ง‘์–ด๋„ฃ์–ด ๊ธฐ๋ก
3. B๊ทธ๋ฃน์„ ์ ์ ˆํ•˜๊ฒŒ ์ •๋ ฌ ํ›„ ๊ฒ€์‚ฌ -> A๊ทธ๋ฃน์„ ํฌํ•จํ•˜๋Š”์ง€, ๊ฐ™์€ B๊ทธ๋ฃน ๋‚ด ๋‹ค๋ฅธ ๋…ธ์„ ์„ ํฌํ•จํ•˜๋Š”์ง€ ํ™•์ธํ•˜์—ฌ ๊ธฐ๋ก.

์ฝ”๋“œ

//busLine.java
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
 
public class BusLine {
	private int numOfBusStop;
	private BusLineInfo[] busLines;
 
	private class BusLineInfo implements Comparable<BusLineInfo> {
		int num;
		int start;
		int end;
 
		public BusLineInfo(int num, int start, int end) {
			this.num = num;
			this.start = start;
			this.end = end;
		}
		@Override
		public int compareTo(BusLineInfo info) {
			// TODO Auto-generated method stub
			int temp = this.start - info.start;
			return temp != 0 ? temp : (this.end - info.end);
		}
	}
 
	public BusLine() {
		getProperties();
	}
 
	private void getProperties() {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			this.numOfBusStop = Integer.parseInt(br.readLine());
		} catch(Exception e) {
			e.printStackTrace();
		}
 
		int numOfBusLine = 0;
		try {
			numOfBusLine = Integer.parseInt(br.readLine());
		} catch(Exception e) {
			e.printStackTrace();
		}
 
		this.busLines = new BusLineInfo[numOfBusLine];
		try {
			for(int i = 0; i<numOfBusLine; i++) {
				String[] str = br.readLine().split(" ");
				this.busLines[i] = new BusLineInfo(i+1, Integer.parseInt(str[0]), Integer.parseInt(str[1]));
			}
		} catch(Exception e) {
			e.printStackTrace();
		}
	}
 
	public int[] deleteDuplicateLine() {
		LinkedList<Integer> lineAfterDelete = new LinkedList<Integer>();
 
		Arrays.sort(this.busLines);
 
		lineAfterDelete.add(0);
		for(int i = 1; i<this.busLines.length; i++) {
			int beforeIndex = lineAfterDelete.getLast();
			boolean isBeforeExceed0 = this.busLines[beforeIndex].end < this.busLines[beforeIndex].start;
			boolean isCurrentExceed0 = this.busLines[i].end < this.busLines[i].start;
 
			if(this.busLines[i].start == this.busLines[beforeIndex].start) {
				if(isBeforeExceed0 && !isCurrentExceed0)
					continue;
				else if(isBeforeExceed0 && isCurrentExceed0) {
					lineAfterDelete = deleteAnyCan(lineAfterDelete, i);
				}
				lineAfterDelete.removeLast();
				lineAfterDelete.add(i);
			}
			else {
				if(isCurrentExceed0) {	//์ถœ๋ฐœ์ง€์ ์ด ๋” ๋‚˜์ค‘์ธ ๊ฒŒ 0์„ ๋„˜์„ ๊ฒฝ์šฐ
					//์ด์ „๊ฒŒ 0์„ ๋„˜๊ณ , ํ˜„์žฌ end๋ณด๋‹ค ์ด์ „ end์ด ๋” ํฌ๋ฉด ํ˜„์žฌ๊ฒŒ ์žก์•„๋จนํž˜. continue
					if(isBeforeExceed0 && this.busLines[beforeIndex].end >= this.busLines[i].end)
						continue;
 
					//์œ„๊ฐ™์€ ๊ฒฝ์šฐ๊ฐ€ ์•„๋‹ˆ๋ฉด, ์žก์•„ ๋จน์ง€ ์•Š์Œ. ํ˜„์žฌ๊ฐ€ ์ด์ „์— ๋จน์„ ๊ฒŒ ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๊ณ  ๋จน์€ ๊ฑด -1๋กœ ํ‘œ์‹œ
					lineAfterDelete = deleteAnyCan(lineAfterDelete, i);
 
					//๋ฐ”๋กœ ์ด์ „์— -1๋กœ ํ‘œ์‹œ๋˜์—ˆ๋‹ค๋ฉด ์ด์ „์œ„์น˜์— ํ˜„์žฌ ์œ„์น˜๋ฅผ ์ง‘์–ด๋„ฃ๊ณ , ์•„๋‹ˆ๋ฉด ํ˜„์žฌ์œ„์น˜์— ๋„ฃ๊ณ  1์ฆ๊ฐ€
					lineAfterDelete.add(i);
				}
				else {		//์•ˆ๋„˜์„ ๊ฒฝ์šฐ
					//์ด์ „์— ๋„˜์œผ๋ฉด ๋ฌด์กฐ๊ฑด ์žก์•„๋จนํž˜
					//๋„˜์ง€์•Š์œผ๋ฉด ์ด์ „ end๊ฐ€ ํ˜„์žฌ end๋ณด๋‹ค ํด๋•Œ ์žก์•„๋จน์Œ.
					//์•„๋‹ˆ๋ฉด ํ˜„์žฌ๊ฑธ ๊ธฐ๋ก.
					if(!isBeforeExceed0 && this.busLines[i].end > this.busLines[beforeIndex].end)
						lineAfterDelete.add(i);
				}
			}
		}
 
		int[] numsLine = new int[lineAfterDelete.size()];
		for(int i = 0; i<numsLine.length; i++)
			numsLine[i] = lineAfterDelete.get(i);
 
		Arrays.sort(numsLine);
 
		return numsLine;
	}
 
	private LinkedList<Integer> deleteAnyCan(LinkedList<Integer> lineAfterDelete, int current) {
		int currentEnd = this.busLines[current].end;
		LinkedList<Integer> temp = new LinkedList<Integer>();
 
		for(int i = 0; i<lineAfterDelete.size(); i++) {		//ํ˜„์žฌ์˜ end๊ฐ€ ์–ด๋–ค ๊ฒƒ์˜ start์™€ end๋ณด๋‹ค ํฌ๋ฉด -1๋กœ ๋ฐ”๊ฟˆ. ์ด๋•Œ ์–ด๋–ค ๊ฒƒ์€ 0์„ ๋„˜์ง€ ๋ง์•„์•ผํ•œ๋‹ค.
			int currentIndex = lineAfterDelete.get(i);
			if(currentEnd >= this.busLines[currentIndex].end && this.busLines[currentIndex].end > this.busLines[currentIndex].start) {
				;
			}
			else
				temp.add(lineAfterDelete.get(i));
		}
 
		return temp;
	}
 
}
 
//Main.java
 
public class Main {
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BusLine test = new BusLine();
		int[] temp = test.deleteDuplicateLine();
		for(int i : temp)
			System.out.print(i + " ");
	}
 
}