문제 URL : https://programmers.co.kr/learn/courses/30/lessons/49191
코딩테스트 연습 - 순위
5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2
programmers.co.kr
문제 접근법:
플로이드 알고리즘을 사용하는 문제입니다.
사실 이문제는 백준에서 https://www.acmicpc.net/problem/2458
2458번: 키 순서
1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여
www.acmicpc.net
키순서와 거의 똑같은 문제를 풀었기때문에 이론적인 풀이가 완전히 똑같습니다.
단반향 그래프를 만든후 플로이드를 사용하게되면 행의 위치는 내가 이길수있는 번호들을 알수잇꼬
열들의 위치는 내가 질수있는 번호들을 알수있습니다. 그러니 그것들을 전부 전부 합해서 나자신만 제외한다면 n-1이라는 숫자가 나오게된다면 순위를 알수있습니다.
소스코드:
|
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
|
//By 콩순이냉장고
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;
int w[101][101];
void floyd(int n)
{
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (w[i][k] & w[k][j])
w[i][j] = 1;
}
}
}
}
int solution(int n, vector<vector<int>> results) {
int answer = 0;
for (int i = 0; i < results.size(); i++)
{
w[results[i][0]][results[i][1]] = 1;
}
floyd(n);
for (int i = 1; i <= n; i++)
{
int sum = 0;
for (int j = 1; j <= n; j++)
{
//w[i][j]는 이길수있고, w[i][j]질수있는수
sum += w[i][j] + w[j][i];
}
if (sum == n - 1)//그숫자가 자기자신을 제외한 n-1 이라면 몇순위인지 알수있음
answer++;
}
return answer;
}
|
cs |
이코드도 마찬가지로 백준 2458 키순서도 풀수있습니다.
궁금한점 혹은 모르는점 혹은 제생각에 틀린오류가 있다면 언제든지 댓글을 이용해주시길 바랍니다.
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 섬 연결하기 (0) | 2020.09.09 |
|---|---|
| 프로그래머스 [3차] 자동완성(2018 KAKAO BLIND RECRUITMENT) (0) | 2020.09.09 |
| 프로그래머스 [1차] 뉴스클러스터링(2018 KAKAO BLINED RECRUITMENT) (0) | 2020.09.09 |
| 프로그래머스 지형 이동(Summer/Winter Coding(2019)) (0) | 2020.08.30 |
| 프로그래머스 기지국설치 (0) | 2020.08.28 |
