20200430 알고리즘
1. 기능개발
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
- 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
- 작업 진도는 100 미만의 자연수입니다.
- 작업 속도는 100 이하의 자연수입니다.
- 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
입출력 예
| progresses | speeds | return |
|---|---|---|
| [93,30,55] | [1,30,5] | [2,1] |
입출력 예 설명
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다. 두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다. 세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.
따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.
Solution
function solution(progresses, speeds) {
const answer = []
let s = 0
while (s < progresses.length){
for (let i=s; i<progresses.length; i++){
progresses[i] += speeds[i]
}
let cnt = 0
while (progresses[s] >= 100){
s += 1
cnt += 1
}
if (cnt > 0) answer.push(cnt)
}
return answer
}2. 여행경로
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 공항 수는 3개 이상 10,000개 이하입니다.
- tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
입출력 예
| tickets | return |
|---|---|
| [[ICN, JFK], [HND, IAD], [JFK, HND]] | [ICN, JFK, HND, IAD] |
| [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] | [ICN, ATL, ICN, SFO, ATL, SFO] |
입출력 예 설명
예제 #1
[ICN, JFK, HND, IAD] 순으로 방문할 수 있습니다.
예제 #2
[ICN, SFO, ATL, ICN, ATL, SFO] 순으로 방문할 수도 있지만 [ICN, ATL, ICN, SFO, ATL, SFO] 가 알파벳 순으로 앞섭니다.
Solution
def solution(tickets):
tickets.sort(key=lambda x: (x[1]))
ch = [0]*len(tickets)
dis = [0]*len(tickets)
answer = list()
is_stop = False
def DFS(L, e):
nonlocal is_stop
if L == len(tickets):
tmp = list()
for j in range(len(dis)):
tmp.append(tickets[dis[j]][0])
if j == len(dis)-1:
tmp.append(tickets[dis[j]][1])
answer.append(tmp)
is_stop = True
else:
for i in range(len(tickets)):
if not is_stop and ch[i] == 0 and tickets[i][0] == e:
ch[i] = 1
dis[L] = i
DFS(L+1, tickets[i][1])
ch[i] = 0
DFS(0,'ICN')
return answer[0]3. 네트워크
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
제한사항
- 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
- 각 컴퓨터는 0부터
n-1인 정수로 표현합니다. - i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
- computer[i][i]는 항상 1입니다.
입출력 예
| n | computers | return |
|---|---|---|
| 3 | [[1, 1, 0], [1, 1, 0], [0, 0, 1]] | 2 |
| 3 | [[1, 1, 0], [1, 1, 1], [0, 1, 1]] | 1 |
Solution (BFS)
from collections import deque
def solution(n, computers):
ch = [0] * len(computers)
answer = 0
for i in range(len(ch)):
if ch[i] == 0:
ch[i] = 1
dQ = deque()
dQ.append(computers[i])
while dQ:
for _ in range(len(dQ)):
cur = dQ.popleft()
for j in range(n):
if cur[j] == 1 and ch[j] == 0:
ch[j] = 1
dQ.append(computers[j])
answer += 1
return answerSolution (DFS)
function solution(n, computers) {
const ch = new Array(n).fill(0)
let answer = 0
function DFS(idx){
for (let j=0; j<n; j++){
if(computers[idx][j] == 1 && ch[j] == 0){
ch[j] = 1
DFS(j)
}
}
}
for (let i=0; i<n; i++){
if (!ch[i]){
ch[i] = 1
DFS(i)
answer += 1
}
}
return answer
}
![[HongDongUk]](/static/a60d793d17c3aad0361c9192a3b51381/a12fc/profile.png)