본문 바로가기

Algorithm98

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 Kakao blind - 수식 최대화(정규표현식, 해싱) java 풀이 https://programmers.co.kr/learn/courses/30/lessons/42893 코딩테스트 연습 - 매칭 점수 매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀 programmers.co.kr - 카카오 코테문제들을 풀다보면 정규표현식을 사용할 줄 알면 편리한 문제들이 종종 있다. 물론 substring과 find 등을 이용해서 인덱스 범위를 찾아서 파싱하는 방식으로도 풀 수 있다. 실제 프로젝트에서 접할 수 있는 문제들을 간접적으로 경험할 수 있는 좋은 문제인 것 같다. - pages의 갯수가 20개, 각 페이지의 문자열의 길이는 1500이므로 별도의.. 2022. 4. 16.
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/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr - 방의 갯수가 최대 1e12 1조이고, 고객들이 요청하는 방 갯수는 20만이다. 고객들이 요구한 번호의 방 혹은 번호가 크면서 비어있는 방 중 가장 번호가 작은 방이라는 조건이 있기 때문에 해시맵으로 사용된 방과 사용할 수 있는 그 다음 방을 해쉬맵에 기록하는 방식으로 접근하였다. - 방을 길이 k의 1차원배열로 생각했을 때 방 정보를 업데이트 할 때마다 해당 방의 오른쪽으로 연결되어있는 방들에 대하여 다음 제공할 수 있는 방 정보에 대해 경로압축을 해놓으면 사용가능한 다음 방을 logM 혹은 a(M)안에 찾을 수 있다.(M은 시작지점으.. 2022. 3. 28.

티스토리툴바