본문 바로가기

Algorithm/프로그래머스 고득점 Kit

[동적계획법] N으로 표현 - Java 코드 ★★★(★★)
2021. 8. 2. https://programmers.co.kr/learn/courses/30/lessons/42895?language=java 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제 이해 DP는 메모이제이션이 필요하다. 해당 문제에서 이전단계에 대한 메모이제이션을 위해서는 각각의 N을 사용하여 만들어지는 모든 경우의 수를 만들어 저장하고, 그렇게 저장한 이전의 경우들을 바탕으로 이후에 단계를 만들어가는 풀이가 필요하다. 풀이 메모이제이션을 위해 Set배열을 만들어서 푼 풀이이다. 각각의 Set 배열에는 연산의 숫자로 만들어질 수 있는 모든 값들을 저장한다. 이후에 Set 배열의 낮은 인덱스에서부터 만들고자했던 목표값 number가 있는지 검사해주면, 최솟값 연산을 반환 할 수 있다. imp..
[그리디] 단속카메라 - Java코드 (프로그래머스 버그존재)
2021. 7. 30. https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 문제 항상 느끼는건데 문제가 참 상냥하지 못함. + 이번에는 문제 설명에 이상한점이 있음, 입출력의 설명 부분에서 -5, -15 지점을 지난다는 말은 틀린말이 아니지만, 사람들에게 혼동을 줄 수 있는 말들임 로직상 통과하는 부분에 카메라를 설치해주어야 최소값을 찾을수 있을것으로 보인다. 올바른 로직으로 구현했을때 카메라는 제일 먼저 빠져나가는 3번 차량의 -13에서 카메라가 설치되어 1번, 2번 을 같이 찍고, 그외에 포함되지않는 4번차량의 범위내에 한번더 설치되어 ..
[그리디] 섬 연결하기 - Java코드 ★★★ (크루스칼, 신장트리)
2021. 7. 29. https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 문제 설계 일단 최속밧을 찾기위해서는 Costs로 오름차순 정렬은 필수이다. Costs가 1이거나 작다고 해서 불필요하게 무작정 연결해서는 안된다. 모든섬 하나 이상의 선이 연결되어도 전체 통행에 대한 연결이 안됬을 수 있다. 선이 이어지는지 여부를 체크하기위한 부분이 필요하다. 이 문제는 신장 트리 구조를 알고 트루스칼 알고리즘을 사용해야하는 문제이다. 트루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하는 알고리즘이다. 연결해야 하는 노드수만큼의 배열..
[그리디] 구명보트 - Java코드 ★★
2021. 7. 29. https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 문제 설계 정렬된 자료에서 몸무게가 높은 순서로 뽑으면서 Count하되, 제일작은 사람과의 합이 limit을 넘지않으면 같이 뽑을 수 있도록, Deque 자료구조를 활용하여, 정렬된 자료에서 앞뒤로 poll()을 해주도록 하였다 풀이 public static int solution(int[] people, int limit) { int..
[그리디] 큰 수 만들기 - Java코드 ★★★
2021. 7. 28. https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr https://hsin.hr/coci/archive/2011_2012/ Croatian Open Competition in Informatics hsin.hr 문제 출처이자 다양한 테스트케이스를 볼 수 있음 (4번의 테스트 다운후, kerk 폴더내 in, out 파일 참고) 문제 나의 접근법 (오답) number 문자열안에 가장 큰수인 9 ~ 0까지 순서대로 반복문을 돌면서, 해당수를 문자열 내에 큰수를 가장 먼저 만나는 부분에서 문자열을 잘라서, 가장 작은숫자부터 차례차례 제거하는 연산을 해서 반복해서 답을 구하려했지만, 테스트케이스 3..
[그리디] 조이스틱- Java코드 ★★★
2021. 7. 27. https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 문제 이해 문제 설명이 조금어렵다. 이해가 중요하다. AAA 시작해서 위아래로 알파벳이동은 하나씩 움직인다. 그리고 또다른 움직임인 커서이동이 있다. 커서이동은 문자열에 자리 이동이다. 첫번째 문자를 목표하는 값으로 셋팅하였으면, 다음 두번째 문자로 이동할 수 있다. 그런데 문제에서는 다음 두번째 문자는 이미 A이므로 좌측이동이아닌 우측이동으로 맨끝지점으로 한번에..
[그리디] 체육복 - Java코드
2021. 7. 27. https://programmers.co.kr/learn/courses/30/lessons/42862?language=java 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 문제 접근법 전체사람 중, 잃어버린 사람을 제외하고, 그들중, 빌릴 수 있는 경우마다 count해서 정답을 반환해주어야겠다. 나는 리스트를 이용하면 빌려준 사람들의 요소를 삭제할수있기 때문에 좋을것같다는 바보같은 생각을 했다. 포인트 예제에는 존재하지 않지만, 잃어버린 사람들중 여벌을 가지고 있을수 있다. 그런 경우를 대비하여, 잃어버린 ..
[완전탐색] 카펫 - Java 풀이
2021. 7. 27. https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 문제 접근법 들어온 두 값의 합이 카펫의 수이고, 카펫수를 인수분해하여 경우의 수를 검사하여 가로세로 크기를 맞춰야 한다. 풀이 public static int[] solution(int brown, int yellow) { int[] answer = {0,0}; int sum = brown+yellow; for(int x=2; x
[완전탐색] 소수찾기 - Java 풀이, 순열 포인트,★★
2021. 7. 27. https://programmers.co.kr/learn/courses/30/lessons/42839?language=java 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 문제 접근법 이것은 순열이 필요해 보인다. 모든 경우에 수로 순열로 만들고, 중복을 제거 해야 한다. (HashSet에 담으면 해결될것 같음) 중복 제거된 리스트에서 소수를 찾아서 count 해주면 끝! 포인트 1. 순열을 만드는 메소드의 구현 (그동안 순열 조합 코드를 안해봐서 이번기회에 외울 예정) 2. 소수검사는 아리..
[완전탐색] 모의고사 - Java 풀이
2021. 7. 27. https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 문제 접근법 완전탐색, 브루트포스는 결국 모든 경우에 수를 따져야하는 알고리즘이이다. 풀기 위해서는 무식해보이는 코딩을 할 수 밖에 없다. 1. 학생별로 반복되는 패턴을 배열에 담아서 맞춘수를 카운트해주고, 2. 맞춘수 중에서 Math.max를 이용해 최댓값을 구해, 제일 많이 맞춘 학생들을 추려내서 배열에 넣어준다. 3. 배열은 크기를 지정해야하는 특성상 정답..
[정렬] H-Index - Java 풀이
2021. 7. 24. https://programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 문제 접근 H-Index는 발표한 N개의 논문중 h이상 인용된 논문이 h이상이여야 하므로, 해의 범위가 0 ~ N 이다. 나는 역순정렬후 H-index를 N부터 0까지로 순회하면서 H-index 이상 인용된 논문이 H개 이상인지를 확인후 루프를 탈출하도록 구현해보았다. 풀이 import java.util.Arrays; import..
[정렬] 가장 큰 수 - Java 풀이
2021. 7. 24. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근법 Comparator를 어떻게 잘 사용해야 값들을 서로 잘 비교하면서 정렬해줄수 있을까 고민하였다. 이 문제는 주어진 배열의 숫자를 문자열로 형변환후 서로 값들을 붙여서 비교후 내림차순 정렬하여 그 값들을 모두 붙여 문자열을 반환하는 문제이다. 방법 1. 서로의 값을 붙여 비교하기 위해 반드시 int array -> String Array 형변환 2. Comparator 를 이용해 정렬방식 재정의 + 마지막 반환시, 0,0,0,0... 과 같이 0 값들로만 들어 왔을 때, 0으로 반환 (TestCa..
[정렬] K번째 수 - Java 풀이
2021. 7. 24. https://programmers.co.kr/learn/courses/30/parts/12198 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 commands 를 통해 [ start, end, K ] 가 들어온다. command에 start, end 길이만큼 배열을 자른다. 자른 배열을 오름차순으로 기본 정렬한 후, K번째 수를 정답 배열에 저장 포인트 여기서 포인트는 , 반복하면서 주어진 배열을 자르는 방법이다. 자바에서 배열의 범위만큼 자르는 메소드로 쓰기 좋은것이 copyOfRange(Array, int startIndex, int La..
[Hash] 베스트 앨범 - Java 풀이★★★
2021. 6. 17. https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 문제 해당 문제를 잘 풀기 위해서는, 문제를 잘 이해하는게 제일중요하다. 일단, 장르별로 Play횟수를 sum한 값을 저장해주어서, sort후 해당 장르에서 2곡씩 뽑아주어야 하는 문제이다. 장르별 Sum값은 Map을 이용하면 되지만, 곡의 가지는 정보는 id(인덱스), 장르, Play횟수 총 3가지 정보를 가지고 있으며, 각각의 속성별로 우선순위를 가지게 정..
[Hash] 위장 - Java 풀이
2021. 6. 16. https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 문제 풀이 조합과 경우의 수는 다르다. 이 문제는 모든 경우의 수에서 한가지의 경우(모든 종류에 옷을 입지 않는 경우)만 제외시키면 된다. import java.util.HashMap; import java.util.Arrays; /*정확성 테스트 테스트 1 〉통과 (0.78ms, 76.7MB) 테스트 2 〉통과 (0.56ms, 77.2MB) 테스트 3 〉통과 (0.78ms, 73.2MB) 테스트 4 〉통과 (0.52ms, 79.1MB) 테스트 5 〉통과 (0.71ms, 78.9MB) 테스트 6 〉통과 (0.47ms, 73.8MB) 테스트 7 〉통..
[Hash] 전화번호 목록 - Java 풀이
2021. 6. 16. https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 문제 풀이 - HashSet 이용 import java.util.Arrays; import java.util.HashSet; public class 전화번호목록 { /* 정확성 테스트 테스트 1 〉통과 (0.51ms, 70.5MB) 테스트 2 〉통과 (0.71ms, 72.7MB) 테스트 3 〉통과 (0.54ms, 73.1MB) 테스트 4 〉통과 (0.60ms..
[Hash] 완주하지 못한 선수 - Java 풀이 (3가지 풀이 - map, set, 배열)
2021. 6. 16. https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 문제 풀이 해시맵, 배열, 해시셋 3가지 방법으로 각각 풀어보았다. 각각의 풀이는 결국 완주자배열에서 참여자이름이 없는 경우를 찾으면 되는 간단한 문제이다. 1) HashMap import java.util.HashMap; class Solution { /* 정확성 테스트 테스트 1 〉통과 (0.03ms, 77.6MB) 테스트 2 〉통과 (0..

티스토리툴바