[알고리즘] 징검다리 건너기 (프로그래머스 Level3)
코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 우선 stones 배열의 최대 크기가 20만이기 때문에 O(N) 시간 만에 처리를 해야 한다. Solution 친구들이 뛰어넘을 수 있는 길이는 K만큼이라고 했으니 어느 구간이라도 연속 K개의 돌이 0이 되는 순간 친구들은 더 이상 다리를 건널 수 없다. 즉 배열에 존재하는 K 길이만큼의 구간들 중, 각 구간마다 포함하고 있는 돌의 최댓값이 모든 구간들 중 최솟값이 되는 경우를 찾아야 한다. 이게 무슨 말이냐면 위의 예시 문에서의 K는 3이다. 해당 배열에서 길이가 3인 구간은 총 8개가 나온다. Start Index Finish Index Max Value 0 2 5 1 3..
2020. 9. 9.
[알고리즘] 순위 (프로그래머스 Level3)
코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 그래프 탐색 문제이다. 순위라고 했으므로 현재 그래프 내에서의 각 노드들의 위치를 알아내야 하는 문제이다. 즉, 각 선수마다 해당 선수보다 강한 선수 + 약한 선수의 수를 구해서 합쳐서 n이 된다면 랭킹을 정확하게 구할 수 있는 선수이다. 예전에도 비슷한 문제를 풀어본 기억이 있는데 'DFS + 역그래프 + DP + Set'을 적절히 활용하면 쉽게 풀 수 있다. Solution 예시 input을 단방향 그래프로 그린 모습이다. 보다시피 2번 선수 뒤에는 1, 3, 4번, 앞에는 5번 선수가 있으므로 다른 모든 선수와의 관계를 명확히 할 수 있다. 5번 또한 본인 뒤에 ..
2020. 9. 7.
