2019 카카오 개발자 겨울 인턴쉽 - 징검다리 건너기(이분 탐색, 슬라이딩 윈도우) - Java 풀이
https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr - 다리의 길이가 N = 20만이기 때문에 다리 길이에 대하여 한 번에 최대로 건널 수 있는 K 사이즈의 윈도우를 만들어서 O(N) 복잡도로 풀거나 혹은 모든 돌들의 원소값이 M = 1~2억 이므로 건너갈 수 있는 인원을 찾는 이분 탐색으로 접근하면 O(NlogM) 복잡도로 풀 수 있다. 최대한 사람들이 점프를 많이 해야 많은 사람들이 많이 건널 수 있다. 처음에는 1칸씩 뛰다가 돌이 0이 되면서 최대 K칸까지 점프할 수 있다. 따라서 이미 건널 사람을 정해놓고 이분탐색을 하..
2022. 3. 28.
2019 카카오 개발자 겨울 인턴쉽 - 튜플(문자열 파싱, 구현 ) - Java 풀이
https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr - 변수 제한사항 범위가 좁아서 딱히 복잡도 걱정을 안하고 푼 문제이다. 실무에서도 JSON 파싱 등을 할 때 종종 쓸만한 방법인 것 같다. },{ 단위로 쪼개는 String.split(String regex) 함수를 쓰려고 정규표현식을 한번 복습했다. 정규표현식에서 중괄호가 앞 문자의 반복을 나타내는 특수문자..
2022. 3. 28.
