고득점 Kit
-
프로그래머스 고득점 Kit) Hash, 전화번호 목록알고리즘/프로그래머스 고득점 Kit 2020. 7. 4. 00:55
전화번호 목록 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조�� programmers.co.kr 풀이 다른 사람 풀이를 구경하다가 좋은 메소드를 알게돼서 포스팅을 남긴다. 코득점 Kit의 Hash 문제라 처음에는 Hash를 이용해서 풀었었다. 오늘 다시 풀었을 때는 2중 포문과 substring을 이용해서 풀었다. 2중 포문으로 돌리는 법은 쉬운 방법이기 때문에 코드를 남기지는 않겠다. 다만, 코드 1에 남긴 코드가 너무 충격적이었다. String에 startsWith라는 메소드가 있다는 것을 처음 알았다. 파라메터로 입력한 값으로 시..
-
프로그래머스 Lv.3) 섬 연결하기알고리즘/프로그래머스 고득점 Kit 2020. 6. 5. 18:41
고득점 Kit - Greedy(탐욕법) 섬 연결하기 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 find - union가 부족하다고 판단되서, 다시 감을 잡고자 다시 풀었다. 풀이 방법은 처음 풀었을 때와 크게 차이점이 없었고, find 메소드와 union메소드만 잘 짜준다면 find - union문제는 무리 없이 풀 수 있을 것 같다. 로직 1. parents 배열을 선언 및 초기화한다. 2. 두 섬의 번호와 비용을 담을 class Island 를 선언한다. 3. 주어진 연결 정보를 담은 배열을 순회하면서, Island 변수를 만들어 우선순위 큐에 담아준다. ( 비용 오름차순 정렬) 4. Queu..
-
프로그래머스 Lv.3) 디스크 컨트롤러 (HEAP)알고리즘/프로그래머스 고득점 Kit 2020. 6. 5. 18:34
프로그래머스 고득점 Kit - HEAP 디스크 컨트롤러 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를�� programmers.co.kr 풀이 저번에 풀었을 때보다 더 빨리 풀기는 했지만, 이놈의 고질병인 문제를 대충 읽는다는게 발목을 계속 잡는다. 정말 중요한 부분인데, 사소한거 하나에 꼬이게 되면 정말 골치가 아프다... 문제 제발 꼼꼼하게 읽자... 문제에서 막혔던 부분을 떠올려보자면, 대기시간을 구하는 방법, 작업 간 공백이 있을 때 시간을 구하는 방법 정도가 되겠다. 대기시간은 몇 번 삽질끝에 쉽게 구했는데, 공백기도 대기시..
-
프로그래머스 Lv.3) 정수 삼각형 (DP)알고리즘/프로그래머스 고득점 Kit 2020. 6. 4. 16:33
정수 삼각형 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 DP를 푸는 방법 중 두 번 모두 bottom-up 방식으로 문제를 풀었다. 문제의 조건은, 삼각형 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 최대 값이 되는 것이다. 그래서 첫번째 풀었을 때는, 다른 분의 풀이를 보고 이해했던 것 같다. 첫번째 푼 방식은 위의 두 경로 중 최대 값을 같는 경로로 탐색하면서 마지막에 도착한 다음, 정렬을 통해 가장 큰 값을 리턴해주었다. 두번째 푼 방식은, 이 경우, out of idx 방지를 신경써주지 않아도 되고, sort를 따로 해주지 않아도 된다는 생각에서 풀이 ..
-
프로그래머스 Lv.2) 큰 수 만들기 (Greedy)알고리즘/프로그래머스 고득점 Kit 2020. 6. 3. 18:13
큰 수 만들기 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 풀이 고득점 Kit 중 greedy에 해당하는 문제다. 이 문제는 전에 풀었었는데, 다시 풀기에 실패한 문제다. Lv2지만 체감상 Lv3였다.. 도저히 모르겠어서 전에 풀었던 코드를 봤는데, 내 머릿속에서 나온 코드가 아닌 것 같다. 그래서 다른 분들의 풀이를 보고 다시 풀었다. 두 풀이 모두, 탐색 범위를 변경해가면서 가장 큰 갑을 넣어주는 로직이다. 가장 큰 값을 찾았을 때, 앞에 있는 수를 모두 지울 수 있다면 답에 더해주고, 아니면 범위를 재설정하는 방법이다. count를 소진할 때 까지 진행하면서, 답을 찾는다. start, end 그리고 max와 maxIdx를 설정해주는 이유는, 완전탐색의 경우 시간초과가 뜨기 때..