공부/2024 항해99코딩클럽
99클럽 3기 코테 스터디 25일차 TIL /[프로그래머스] 순위 자바
푸딩코딩
2024. 8. 16. 00:33
728x90
반응형
1. 오늘의 학습 문제
문제
https://school.programmers.co.kr/learn/courses/30/lessons/49191
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코드
import java.util.*;
class Solution {
static ArrayList<ArrayList<Integer>> defeat; //내가 이기는 선수
static ArrayList<ArrayList<Integer>> lose; //내가 지는 선수
//각 ArrayList를 BFS 탐색했을 때 방문한 노드의 수 합이 n이면 순위를 매길 수 있음
static int people;
public int solution(int n, int[][] results) {
int answer = 0;
people=n;
//선수 크기에 맞게 defeat, lose arrayList만들기 초기화
defeat = new ArrayList<>(n + 1);
lose = new ArrayList<>(n + 1);
for(int i = 0 ; i <= n ; i++) { //SubArraylist 추가하기
defeat.add(new ArrayList<>());
lose.add(new ArrayList<>());
}
for (int[] result : results) {
int me = result[0];
int opponent = result[1];
defeat.get(me).add(opponent); //내가 이긴 선수 추가
lose.get(opponent).add(me); //내가 지는 선수 추가
}
for(int i=0;i<=n;i++){ //선수 i에 대해 이기는 선수+지는 선수 합이 n-1이면 순위를 알 수 있음.
if(BFS(i, defeat) +BFS(i, lose)==n-1)
answer++;
}
return answer;
}
static public int BFS( int me, ArrayList<ArrayList<Integer>> array){
boolean []visit =new boolean[people+1];
Queue<Integer> q = new LinkedList<>();
int answer=0;
q.add(me); //큐에 추가
visit[me]=true; //방문처리
while(!q.isEmpty()){
int now=q.poll();//큐에서 원소 빼기
for(int opp:array.get(now)){
if(!visit[opp]){
q.add(opp);
answer++;
visit[opp]=true;
}
}
}
return answer;
}
}
#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL
728x90
반응형