이 문제는 문제 풀면서 조금 짜증났던 문제였다. 처음에 문제를 읽고 알고리즘을 세우는 데에는 10분 가량?이었는데 세운 알고리즘대로 코드를 작성했더니 정확도가 60점이어서 왜 안되는지 이유를 몰라 30분 가량 이도저도 못하고 있었다. 그러다가 스터디 시간에 친구에게 왜 내 코드가 안되는지 모르겠다며 알고리즘을 설명해 주다가 깨달았고…^^ 코드를 한 줄만 더해주었더니 해결 되었다. 뭔가 허무하기도 했는데 정확한 이유를 깨닫고 그에 맞게 정확한 알고리즘을 세울 수 있어서 좋았다. 하지만 효율성은 마음에 들지 않는다 ^_^
1. 문제
n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다.
권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다.
심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다.
하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.
선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때
정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.
제한조건
- 선수의 수는 1명 이상 100명 이하입니다.
- 경기 결과는 1개 이상 4,500개 이하입니다.
- results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
- 모든 경기 결과에는 모순이 없습니다.
2. 알고리즘! 생각해보자
- 각 선수가 이긴 선수와 진 선수의 번호를 나타내는 맵
win과defeat을 생성한다. - 답을 나타내는 변수
answer를 0으로 초기화하여 생성한다. - 매개변수로 받은
results를 각win,defeat맵에 초기화 시켜준다. - 초기화된 맵을 기반으로 각 선수의 이긴 선수와 진 선수를 모두 찾아준다.
(1번 선수부터 n번 선수까지win맵을 돌면서 자신이 이긴 선수가 이긴 선수 또한 자신의 value 셋에 넣어준다.
defeat맵도 자신을 이긴 선수를 이긴 선수에게도 지기 때문에 마찬가지로 value 셋에 넣어준다.
이 작업을 n-1번 반복하는 이유는 각 선수의win,defeat맵의 업데이트가 진행된 결과가 다른 선수에게 반영이 되지 않는 경우가 있을 수 있기 때문이다.) - 각 선수의 이긴 선수
win맵과 진 선수defeat맵의 크기를 합하여 그 값이 n-1이면 확실히 등수를 알 수 있으므로answer를 증가시킨다. - 반복문이 끝나
answer값이 구해지면answer를 반환하다.
3. 해결코드
[C++]
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
#include <vector>
#include <map>
#include <set>
using namespace std;
int solution(int n, vector<vector<int>> results) {
map<int, set<int>> win;
map<int, set<int>> defeat;
int answer = 0;
for(auto result : results) {
win[result[0]].insert(result[1]);
defeat[result[1]].insert(result[0]);
}
int count = n;
while(--count) {
for(int i = 1; i <= n; i++) {
for(auto loser : win[i])
win[i].insert(win[loser].begin(), win[loser].end());
for(auto winner : defeat[i])
defeat[i].insert(defeat[winner].begin(), defeat[winner].end());
}
}
for(int i = 1; i <= n; i++)
if(win[i].size() + defeat[i].size() == n-1) answer++;
return answer;
}
4. 해결능력UP, 깊이 생각해보기
set에 다른set을 삽입하는 방법
5. 참고해서 문제해결 ٩( ᐛ )و
- std:set:insert http://cplusplus.com/reference/set/set/insert/
set에 다른set을 삽입할 때는set.insert()를 사용set1.insert(set2.begin(), set2.end())의 형태로set2를set1에 삽입 가능
1
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges