[알고리즘] 풍선 터트리기 (월간 코드 챌린지 시즌1 - 9월)
코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 월간 코드 챌린지 9월에 나온 레벨3 문제다. 9월 10월 둘 다 풀면서 느낀건 브루트 포스 문제보단 아이디어로 시간복잡도를 최소화 해가면서 푸는 방식을 원하는 것 같다. 이 문제 또한 N이 최대 1백만이기에 O(N ^ 2)으론 풀 수가 없다. Solution 먼저 파악해야할 것은 어떤 특정값이 최후까지 살아남는지 알아볼 때, 양쪽에 있는 수들은 서로 만날 수가 없다. 그렇기에 특정값을 기준으로 왼쪽 오른쪽으로 나누어서 살펴봐야 한다. 그리고 양쪽에서 최후까지 살아남을 수 있는 수는 각각 2가지가 되는데 '최소값, 최소값보다 한단계 더 큰 값'이 될 수 있다. 최소값은..
2020. 10. 9.
[알고리즘] 캐시 (2018 카카오)
코딩테스트 연습 - [1차] 캐시 3 [Jeju, Pangyo, Seoul, NewYork, LA, Jeju, Pangyo, Seoul, NewYork, LA] 50 3 [Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul] 21 2 [Jeju, Pangyo, Seoul, NewYork, LA, SanFrancisco, Seoul, Rome, Paris, Jeju, NewYork, Rome] 60 5 [Jeju, Pangyo, S programmers.co.kr 예전에 카카오 연습문제를 찾아보다가 한 번 풀었봤던 기억이 있는데 그 당시엔 프로그래머스를 몰라서 프로그래머스에서 푼게 아니라 그냥 이클립스에다가 돌리고 나와있는 테스트 케이스만 돌려봤었..
2020. 9. 11.
[알고리즘] 징검다리 건너기 (프로그래머스 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.
