2021 Kakao blind - 카드 짝 맞추기(bfs, recursion) - java 풀이
https://programmers.co.kr/learn/courses/30/lessons/72415 코딩테스트 연습 - 카드 짝 맞추기 [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16 programmers.co.kr - 2차원 배열 board의 크기가 4*4 이고, 카드 종류는 1~6, board에 존재하는 카드 페어는 무조건 1짝 씩 있다는 점이 주요 포인트이다. 카드의 갯수가 최대 12개 이고, 카드 1종류를 정해서 최단거리로 소거해나간다면 순회 순서를 순열로 만들어서 순회한다면 순열 복잡도 * bfs 복잡도 = O(n! * V^2) = 6! * 16^2 = 18만 연산으로..
2022. 4. 24.
2021 Kakao internship - 표 편집(링크드리스트, 이진트리) java 풀이
https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr - 제한조건을 유심히 보고 구현해야 될 문제이다. 행의 갯수가 최대 100만이기 때문에 만약 인덱스 0번 row와 '100만'번 row 사이를 이동하는 케이스라면 cmd의 갯수 20만 * 100만번을 이동해야될 수 있다. 그런데 up, down 연산시 나오는 행 이동 X의 총 합이 최대 100만이므로 삭제된 행들..
2022. 4. 18.
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.
