알고리즘 (12) 썸네일형 리스트형 프로그래머스 Java Lv3 양과 늑대 https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 해당 문제는 "앞으로 갈 수 있는 노드들"을 포인트로 생각하면 생각보다 쉽게 풀 수 있다. 이 문제는 루트 노드에서 출발하여 각 노드를 돌아다니고 양과 늑대를 모으게 된다.노드는 자유롭게 이동할 수 있으므로 이동 순서에 대한 관리는 필요 없게 된다.따라서 현재 상태에서 앞으로 갈 수 있는 노드들만 관리하면 된다. 현재 노드에서 다른 노드로 이동하는 경우를 생각해보자.현재 내가 갈 수 있는 노드가 [1.. 프로그래머스 Java Lv3 주사위 고르기 https://school.programmers.co.kr/learn/courses/30/lessons/258709 해당 문제는 다음 2가지 포인트만 잘 생각하면 풀 수 있는 문제이다. 1. 모든 주사위 조합을 구하고, A 와 B의 경우를 매칭하는 것 2. 주사위 조합에 따라 나올 수 있는 점수 조합의 수를 구하고 압축하는 것 문제에서 주어진 n개의 주사위 중 절반의 주사위를 가져갈 때 승리할 확률이 가장 높도록 주사위를 선택해야한다. 그러므로 우선 생각해야할 것은 나올 수 있는 주사위 조합의 경우이다. 주어진 조건에 따르면 주사위의 수 n은 2 ~ 10 사이의 짝수 이다. n = 2 인 경우, 주사위 [ 1, 2 ] 가 있다면 다음과 같은 경우가 존재한다. 1. 주사위 "1" 을 고른 경우 2. 주사위.. 프로그래머스 Java Lv1 가장 많이 받은 선물 https://school.programmers.co.kr/learn/courses/30/lessons/258712 해당 문제는 단순 구현으로 쉽게 풀 수 있는 문제이다. 규칙은 단순하다. 1. 주고 받은 적이 있고, 그 정도에 차이가 있다면 많이 준 사람이 선물을 하나 받는다. 2. 주고 받은 적이 없거나, 그 정도가 같다면 선물 지수를 비교한다. 3. 선물 지수도 같다면 선물을 주고 받지 않는다. 이러한 규칙에 따라서 다음 달 받을 선물의 수를 계산하기 위해서 다음과 같은 변수가 필요하다. 1. 주고 받은 선물 내역을 저장할 변수 2. 선물 지수를 저장할 변수 3. 다음달 받는 선물의 수를 저장할 변수 다음과 같은 데이터를 저장하기 위해서 각각 다음과 같은 자료형이 필요하다. 1. 이차원 정수형 배열.. 프로그래머스 Java Lv3 야근 지수 https://school.programmers.co.kr/learn/courses/30/lessons/12927 해당 문제는 우선순위 큐를 이용하면 간단하게 풀 수 있다. 이 문제는 남은 시간 n과 각 일에 대한 작업량 works 가 주어진다. 야근 피로도는 각 일에 대한 작업량의 제곱의 합 이므로 이를 최소화하기 위해서는 가장 많이 남은 일부터 처리하면 된다. 즉, 내림차순으로 정렬된 우선순위 큐를 이용하면 가장 많이 남은 일을 쉽게 구할 수 있고, n번 반복을 통해 가장 많이 남은 일을 처리하면 된다. 간단한 예를 통해 확인해보자. 남은 일이 [7, 1, 1] / [5, 2, 2] / [3, 3, 3] 인 3가지 경우를 생각해보자. 3가지 경우 모두 남은 일의 총합은 9이다. 다만 각각의 일에 대해.. 프로그래머스 Java Lv2 숫자 블록 https://school.programmers.co.kr/learn/courses/30/lessons/12923 해당 문제는 숫자 블록이 배치되는 규칙성을 찾으면 쉽게 풀 수 있는 문제이다. 숫자 n이 적힌 블록들이 n*2, n*3, n*4, ... 위치에 배치된다. (배치 위치) 또한 숫자 n은 1 부터 시작하여 10,000,000 (천만)까지 이며, (증가 순서 ,크기 제한) 뒤에 배치되는 블록이 먼저 배치된 블록 대신 배치되게 된다. (갱신) 이러한 규칙으로 블록을 배치하게 되면 어떠한 위치 a에 배치되는 숫자는 "어떠한 위치 a 의 약수 중 자신을 제외한 가장 큰 수" 이다. 예를 들어 10번 째 위치를 생각해보자. 10번 째 위치에 배치될 수 있는 숫자 블록은 1, 2, 5 이다. 1을 10번.. 프로그래머스 Java Lv2 의상 https://school.programmers.co.kr/learn/courses/30/lessons/42578 이 문제는 주어진 의상의 종류와 각 종류 별로 몇 개의 의상이 존재하는지만 구별한다면 쉽게 해결 할 수 있는 문제이다. 본인의 경우 HashMap을 이용하여 의상의 종류를 구분하고 종류 별 개수를 구하였다. 입력된 이차열 배열 clothes에서 의상의 종류만을 추출하여 HashMap 에 저장한다. 아직 HashMap에 저장된 적이 없다면 종류와 1을 저장. 이미 저장되어 있다면 저장된 값을 1 증가 시키면 된다. 이제 저장된 의상의 종류와 그 수로 가능한 조합의 수를 계산해보자. 그럼 일단 경우를 나누어 생각해보겠다. (의상의 종류 별로 개수를 a, b, c, ... 라고 하겠다.) 1) 의.. 프로그래머스 Java Lv2 두 원 사이의 정수 쌍 https://school.programmers.co.kr/learn/courses/30/lessons/181187 해당 문제는 원의 방정식과 사분면을 이용하면 간단하게 풀 수 있다. 문제에서 요구하는 두 원 사이의 공간에서 x좌표와 y좌표가 모두 정수인 점들은 각 사분면에 대칭하는 것을 볼 수 있다. 그러므로 하나의 사분면에 존재하는 점들의 수를 구한뒤, 4를 곱하여 모든 점의 수를 계산할 수 있다. 그렇다면 하나의 사분면에 존재하는 점들의 수는 어떻게 구할까? x좌표와 y좌표가 모두 정수인 점들이므로, x좌표가 정수인 경우 가능한 y좌표의 범위를 구하여 계산을 하였다. 이 때, 가능한 y좌표의 범위를 구하기 위해 원의 방정식을 이용하였다. 중심이 (a, b)인 원의 방정식 : (x-a)² + (y-b.. 프로그래머스 Java Lv2 구명 보트 https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 PriorityQueue를 이용하여 해결하였다. PriorityQueue에 값을 한번 넣을 때 마다 하나의 구명 보트가 추가 된다고 생각하였다. 이 때, PriorityQueue에 저장되는 값은 1명의 인원이 구명 보트에 타고 남은 무게 제한(kg) 이다. *PriorityQueue - 이하 PQ 전체적인 흐름은 다음과 같다. 우선, 사람들의 몸무게를 담은 배열을 오름차순으로 정렬하였.. 이전 1 2 다음
