study/알고리즘
[프로그래머스] 프로그래머스 Level 3 순위 풀이 코드
kingjake
2019. 6. 7. 17:28
프로그래머스 Level 3 순위 풀이 코드
인터넷에 통과할 수 있는 코드가 없길래 써보는 코드
문제
n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.
선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.
입출력 예시
n: 5
results: {{4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}}
return: 2
풀이법
각 번호를 노드로 만들고, 각 노드가 이기는 노드를 win 리스트로, 지는 노드들을 lose 리스트로 저장.
각 노드들을 검사하여 A가 B한테 진다면, B가 이기는 노드들을 A가 이기는 노드 리스트에도 저장. 겹치지않게 HashSet으로 관리.
지는 노드들도 마찬가지로 해준다.
모든 노드들을 검사하는 반복문을 2번 돌려서 검사를 통과 했는데, 더 좋은 방법이 있을거 같은데 일단 생각이 안난다.
코드
|
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
|
class Solution {
public int solution(int n, int[][] results) {
int answer = 0;
ArrayList<RankNode> list = new ArrayList<>();
list.add(new RankNode(0));
for(int i=1; i<=n; i++) {
list.add(new RankNode(i));
}
for(int[] r : results) {
list.get(r[1]).lose.add(r[0]);
list.get(r[0]).win.add(r[1]);
}
for(int k=0; k<2; k++) {
for(int i=1; i<=n; i++) {
RankNode rn = list.get(i);
HashSet<Integer> tmp = new HashSet<>();
for(Integer win : rn.win) {
for(Integer w: list.get(win).win) {
tmp.add(w);
}
}
rn.win.addAll(tmp);
tmp = new HashSet<>();
for(Integer lose: rn.lose) {
for(Integer l: list.get(lose).lose) {
tmp.add(l);
}
}
rn.lose.addAll(tmp);
}
}
for(RankNode rn : list) {
int size = rn.win.size();
size += rn.lose.size();
if(size>=n-1) {
answer++;
}
}
return answer;
}
}
class RankNode{
int key;
HashSet<Integer> lose;
HashSet<Integer> win;
boolean isRank;
public RankNode(int k) {
key = k;
lose= new HashSet<>();
win= new HashSet<>();
isRank = false;
}
}
|
cs |