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 + " ");
}
}