10165 KOI 2014_Elementary
알고리즘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1. 각 버스노선의 출발점, 도착점, 번호를 기록한 구조체를 만들고, 출발점을 기준으로 정렬. 출발점이 같으면 도착점이 작은 것이 앞에 위치하도록함.
2. 버스노선인덱스를 저장하는 배열을 만들어, 버스노선을 하나씩 검사함.
-초기 : 첫번째 버스노선을 넣음
3. 검사내용
-출발점이 이전 버스노선과 같은가
-이전 버스노선이 0을 지나치고, 현재 버스노선도 0을 지나치는가 (정렬로 인해 자동으로 현재버스노선이 이전버스노선을 감싸는 형태가 됨.)
-현재버스 노선을 넣었을 때 지워지는 노선을 전부 지움
-이전버스노선도 지워졌으므로, 이전 버스노선인덱스 위치에 현재 버스노선의 인덱스를 넣음
-이전 버스노선이 0을 지나치지만, 현재 버스노선은 0을 지나치지 앟음
-현재버스노선 스킵
-이전 버스노선이 0을 지나치지 않음
-이전 버스노선을 지우고, 현재 버스노선을 저장
-출발점이 이전 버스노선과 다른가
-현재 버스노선이 0을 지나치는가
-이전 버스노선이 0을 지나치고, 현재 버스노선을 감싸는가
-스킵
-그 외
-현재버스 노선을 넣었을 때 지워지는 노선을 전부 지움
-이전 버스노선이 지워졌으면 이전 위치에 넣고, 아니면 이어서 넣자
-현재 버스노선이 0을 지나치치 않는가
-이전 버스노선이 0을 지나치지 않고, 현재 버스노선을 감싸지 않을 때
-현재 버스노선을 이어서 넣음
-그 외 스킵
4. 검사 끝나고, 버스노선 인덱스들로부터 남은 버스노선의 번호들을 추출하고, 번호들을 정렬하여 출력.
다른 풀이법
1
2
3
1. 0번 정류장을 안지나는 그룹을 A, 지나는 그룹을 B라고 하자.
2. A그룹 먼저 내 방식대로 정렬 후 겹치는 거 있는지 확인 후 집어넣어 기록
3. B그룹을 적절하게 정렬 후 검사 -> A그룹을 포함하는지, 같은 B그룹 내 다른 노선을 포함하는지 확인하여 기록.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
//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 + " ");
}
}