n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.
선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
선수의 수는 1명 이상 100명 이하입니다.
경기 결과는 1개 이상 4,500개 이하입니다.
results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
모든 경기 결과에는 모순이 없습니다.
입출력 예
n results return
5
[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]
2
입출력 예 설명
2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다. 5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.
문제푸는 방법:
1. 그래프를 사용해서 푸는 문제이다.
2. 대신 순서가 있다. 이긴 방향 그래프 / 진 방향 그래프
3. 이긴 방향 그래프를 통해 나보다 아래있는 노드의 '개수'를 파악한다.(최단 경로 이런 문제 아님)
4. 진 방향 그래프를 탐색하면서 나보다 위에 있는 노드의 '개수'를 파악한다.
5. 3번과 4번의 결과가 n-1개여야지 순서가 제대로 정해진 것이다.
6. 1~n까지 5에 해당하는 경우 result +=1 해준다.
7. result를 반환해준다.
정답 코드:
def solution(n, results):
arr = {}
arr2 = {}
for i in results:
if i[0] not in arr:
arr[i[0]] = [i[1]]
else:
arr[i[0]].append(i[1])
if i[1] not in arr2:
arr2[i[1]] = [i[0]]
else:
arr2[i[1]].append(i[0])
answer = 0
for i in range(1,n+1):
if bfs(arr,i) + bfs(arr2,i) == n-1:
answer += 1
return answer
def bfs(graph,start):
queue = [[start,0]]
visited = []
a = -1
while queue:
current = queue.pop(0)
if current[0] not in visited:
a += 1
visited.append(current[0])
if current[0] in graph:
arr = set(graph[current[0]]) - set(visited)
queue.extend([[i,current[1]+1] for i in arr])
return a
코드 최적화
as-is:
11줄의 코드를
arr = {}
arr2 = {}
for i in results:
if i[0] not in arr:
arr[i[0]] = [i[1]]
else:
arr[i[0]].append(i[1])
if i[1] not in arr2:
arr2[i[1]] = [i[0]]
else:
arr2[i[1]].append(i[0])
to-be:
6줄로 간결하게 만들어준다.
from collections import defaultdict
~~~~~~~
arr = defaultdict(set)
arr2 = defaultdict(set)
for i in results:
arr[i[0]].add(i[1])
arr2[i[1]].add(i[0])
프로그래머스를 풀면서 또 하나 느낀 점은 반드시 효율적인 코드를 짜는 것보다는
정확한 방법이 생각나면 일단 도전해보는 것이다.
도전해보면 의외로 프로그래머스에서 정확도만 채점하는 경우도 있기 때문이다.(이 문제같은 경우 그렇다.)
NHN 코딩테스트를 대비하여 Java 코드로도 풀어보았다.
푸는 방식은 위의 파이썬 설명과 같다.
import java.util.*;
class Solution {
public int solution(int n, int[][] results) {
int answer = 0;
ArrayList<ArrayList<Integer>> win = new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> lose = new ArrayList<ArrayList<Integer>>();
for(int i=0; i<n+1; i++){
win.add(new ArrayList<Integer>());
lose.add(new ArrayList<Integer>());
}
for(int[] i: results){
int a = i[0];
int b = i[1];
win.get(a).add(b);
lose.get(b).add(a);
}
int ans = 0;
for(int i=1; i<n+1; i++){
if(BFS(win,i,n)+BFS(lose,i,n) == n-1){
ans++;
}
}
return ans;
}
int BFS(ArrayList<ArrayList<Integer>> graph, int start, int n){
boolean[] visited = new boolean[n+1];
visited[start] = true;
Queue<Integer> q = new LinkedList<Integer>();
q.add(start);
int a = -1;
while(!q.isEmpty()){
int cur = q.poll();
a++;
for(int i:graph.get(cur)){
if(!visited[i]){
visited[i] = true;
q.add(i);
}
}
}
return a;
}
}
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(N, P, Q):
# write your code in Python 3.6
result = []
for a,b in zip(P,Q):
if b <= N:
c = b
else:
c = N
result.append(len(get_prime(N,a,c)))
#print(result)
return result
pass
def get_prime(num,a,b):
arr = []
if num <= 1:
return arr
arr2 = []
for i in range(2,num+1):
flag = True
for j in range(len(arr)):
if i%arr[j] == 0:
flag = False
break
if flag:
if a <= i**2 and i**2 <= b:
arr2.append(i*i)
arr2.extend([k*i for k in arr if a <= k*i and k*i <= b])
arr.append(i)
return arr2
구글링을 통해서 해답을 알게 되었다.
해답은 인덱스를 사용하여 계산을 하는 것이다.
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import math
def solution(N, P, Q):
# write your code in Python 3.6
# N+1의 개수를 가진 빈 배열을 만들어준다.
arr = [0]*(N+1)
semi_cnt = [0]*(N+1)
each_sum = 0
#1~N 까지의 범위의 수를 소수와 소수의 배수로 구분함
i = 2
while i <= math.sqrt(N):
if arr[i] == 0:
j = i*i
while j <= N:
arr[j] = i
j += i
i += 1
#print(arr)
# 인덱스를 통해서 문제를 풀어준다.(소수일때, 나누고 나눈 값이 다시 소수라면 +1)
for i in range(1,N+1):
if arr[i] != 0:
j = i//arr[i]
if arr[j] == 0:
each_sum += 1
semi_cnt[i] = each_sum
#rint(semi_cnt)
result = []
# 범위에 따라 소수의 개수를 차감하여 값을 배열에 넣어준다.
for i,j in zip(P,Q):
result.append(semi_cnt[j]-semi_cnt[i-1])
#print(result)
return result
pass
※ 공지 - 2020년 2월 3일 테스트케이스가 추가되었습니다. ※ 공지 - 2020년 5월 11일 웹접근성을 고려하여 빨간색을 노란색으로 수정하였습니다.
문제 푸는 방식:
완전 탐색 알고리즘을 사용하여 무식하게 for문을 통해 모든 경우를 살펴봐야한다.
실제로 네이버에서 면접을 볼때 완전탐색을 요하는 문제를 물어보았다.
우선 yellow의 값이 될 수 있는 가로*세로의 모든 경우을 고르고
모든 경우에서 brown의 개수가 충족되는 것을 찾아내었다.
정답 코드는 아래와 같다.
def solution(brown, yellow):
answer = []
a = measure(yellow)
for i in a:
if (i[0]+2)*2+(i[1]*2) == brown:
return [i[0]+2,i[1]+2]
return answer
def measure(num):
i = 1
result = []
while i*i <= num:
if num%i==0:
result.append([num//i,i])
i += 1
return result
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
numbers return
17
3
011
2
입출력 예 설명
예제 #1 [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
예제 #2 [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
11과 011은 같은 숫자로 취급합니다.
문제푸는 방법:
완전 탐색으로 풀 수 있다.
for문을 통해 모든 원소에 접근하여 소수인지 아닌지 판별한다.
정답 코드:
def solution(numbers):
from itertools import permutations
c = {}
answer = 0
arr = [i for i in numbers]
for i in range(1,len(arr)+1):
a = list(set(permutations(arr,i)))
for j in range(len(a)):
b = ""
for k in a[j]:
b += str(k)
if is_sosu(int(b)) and int(b) not in c:
c[int(b)] = 1
answer += 1
return answer
def is_sosu(num):
if num <= 1:
return False
for i in range(2,num//2+1):
if num%i == 0:
return False
return True
예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.
문제 푸는 방법:
BFS 알고리즘으로 한 칸씩 가면서 Count를 +1 씩 해주면된다.
마지막 Visited 리스트에서 Counter 함수를 통해 중복값끼리 모으고 Sorting 하여 최대값을 알아낸다.
정답 코드:
from collections import deque, Counter
def solution(n, edge):
answer = 0
graph = {}
for i in edge:
if i[0] in graph:
graph[i[0]].append(i[1])
else:
graph[i[0]] = [i[1]]
if i[1] in graph:
graph[i[1]].append(i[0])
else:
graph[i[1]] = [i[0]]
result = bfs(graph,1)
result = sorted(result.values(), reverse=True)
return list(Counter(result).values())[0]
def bfs(edge,root):
visited = {}
queue=deque([[root,0]])
arr = [[root,0]]
while queue:
current = queue.popleft()
if current[0] not in visited:
visited[current[0]] = current[1]
add = set(edge[current[0]]) - set(visited)
queue += ([[i,current[1]+1] for i in add])
return visited
나의 생각:
드디어 경로 문제의 첫 발을 띄었다.
항상 알고리즘 문제에서 경로 문제를 제일 어려워했는데,
프로그래머스의 Level 2의 조금 쉬운 문제로 시작했다.
생각보다 어려운 공식이 아니었다. 앞으로 경로 문제 풀 때 괜히 겁먹지 말자!
화이팅!!
NHN 코딩테스트를 대비하며 Java 로도 풀어보았다.
푸는 방식은 위의 파이썬 코드 설명과 같다. 화이팅!
import java.util.*;
class Solution {
public int solution(int n, int[][] edge) {
int answer = 0;
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
for(int i=0; i<edge.length; i++){
list.add(new ArrayList<Integer>());
}
for(int[] i:edge){
int a = i[0];
int b = i[1];
list.get(a).add(b);
list.get(b).add(a);
}
int[] cnt = new int[n+1];
cnt[0]=cnt[1] = 0;
boolean[] visited = new boolean[n+1];
visited[0]=visited[1] = true;
Queue<Integer> q = new LinkedList<Integer>();
q.add(1);// 시작점
while(!q.isEmpty()){
int cur = q.poll();
for(int v:list.get(cur)){
if(!visited[v]){
visited[v] = true;
cnt[v] = cnt[cur]+1;
q.add(v);
}
}
}
int max = 0;
int ans = 0;
for(int i: cnt){
if(max<i){
max = i;
ans = 1;
}else if(max == i){
ans += 1;
}
}
return ans;
}
}
