사용한 것
- 순서가 없고 중복을 허용하지 않는 자료구조 Set
풀이 방법
Result
클래스에 Set으로 win, lose 필드 생성
- Map<Integer, Result> 로 선수 별 결과를 저장
- A가 B를 이기면
- A win에 B, B win 추가
- B lose에 A, A lose 추가
- A lose들을 돌면서 B, B win 추가
- B lose들을 돌면서 A, A lose 추가
- win, lose 크기의 합이 n - 1이면 순위가 정해진 것
코드
class Solution {
public int solution(int n, int[][] results) {
Map<Integer, Result> map = new HashMap<>();
for (int[] result : results) {
int winner = result[0];
int loser = result[1];
if (!map.containsKey(winner)) {
map.put(winner, new Result());
}
if (!map.containsKey(loser)) {
map.put(loser, new Result());
}
Result winnerResult = map.get(winner);
Result loserResult = map.get(loser);
for (Integer winnersWinner : winnerResult.lose) {
Result winnersWinnerResult = map.get(winnersWinner);
winnersWinnerResult.win.addAll(loserResult.win);
winnersWinnerResult.win.add(loser);
}
winnerResult.win.addAll(loserResult.win);
winnerResult.win.add(loser);
for (Integer losersLoser : loserResult.win) {
Result losersLoserResult = map.get(losersLoser);
losersLoserResult.lose.addAll(winnerResult.lose);
losersLoserResult.lose.add(winner);
}
loserResult.lose.addAll(winnerResult.lose);
loserResult.lose.add(winner);
}
int answer = 0;
for (Integer key : map.keySet()) {
Result result = map.get(key);
if (result.win.size() + result.lose.size() == n - 1) {
answer++;
}
}
return answer;
}
}
class Result {
public Set<Integer> win = new HashSet<>();
public Set<Integer> lose = new HashSet<>();
}