코딩 테스트
프로그래머스 - 정수삼각형 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 삼각형의 모양을 아래와 같이 생각하고 풀면 쉽게 풀린다. |\ | \ | \ ---- 1. 맨 왼쪽의 경로는 바로 위에서 오는 경로 뿐이므로 우선 계산한다. 2. 이후 맨 왼쪽과 맨위를 제외한 영역을 순회하면서 누적값을 구한다. - 바로 위와 왼쪽 대각의 값 중 높은 값과 본인을 합쳐서 계산 3. dp의 맨 마지막 줄 중에 가장 큰값을 리턴 // 프로그래머스 정수삼각형 문제 class Triangle { public int solution(int[][..
프로그래머스 - 이중우선순위 큐 문제 (자바)
programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 오름차순의 우선순위 큐와 내리차순의 우선순위 큐를 만들고 연산에 따라서 두개의 큐를 셋팅 한쪽 큐에서 꺼낸값으로 remove를 하면 해당 값을 제거함(중복값 인 경우 한개 만 제거) import java.util.Collections; import java.util.PriorityQueue; // 프로그래머스 이증우선순위 큐 class TwoPriorityQueue { public int[] solution(String[] operations) { PriorityQueue maxQ = new PriorityQueue(Collections.reverseO..
프로그래머스 - 구명 보트 문제 - 자바
programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 그리드 문제로 가장 작은 사람과 가장 큰 사람이 보트에 동시에 탈수있는지 없는지로 해결하는 문제 상당히 간단한 문제인데 저는 처음에 limit에서 가장 큰사람을 빼고 남은 무게에 가장 가까운 사람을 같이 태워 보내야한다고 생각을 했습니다. 사람의 무게가 1 2 3 4 6 7이고 제한이 10일때 (1, 7), (2, 6), (3, 4) (3, 7), ..
프로그래머스 - 섬 연결하기 문제 - 자바
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 최소 신장 트리를 묻는 문제로 우선순위 큐를 통해서 가장 비용이 적은 다리부터 설치해 가면서 유니온/파인드를 통해서 싸이클이 도는지 여부를 확인하고 부모를 합쳐서 문제를 풀수있다. import java.util.PriorityQueue; // 프로그래머스 섬 연결하기 문제 class Bridge implements Comparable { int a; int b; int cost; public Bridge(int a, int b, int cost) { this.a = a; t..
프로그래머스 - 가장 큰 수 문제 - 자바
programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 정렬 문제로 두 수를 문자로면 판단하여 앞뒤로 붙힌 값중 큰값이 먼저 오도록 정렬하고 문자를 만들면 끝난다. import java.util.Arrays; // 프로그래머스 가장 큰 수 문제 class BigNum { public String solution(int[] numbers) { StringBuilder ..
프로그래머스 - 베스트 앨범 문제 - 자바
programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 장르, 장르별 총재생횟수 장르, 장르에 속한 노래 이 두가지로 map을 만들고 셋팅한 뒤 장르, 장르별 총재생을 총재생에 따라서 정렬한 뒤 각 장르별 2개까지만 추출한다. 아래의 코드 중 조심해야하는 부분은 getOrDefault 메서더는 해당 키값이 이미 map에 존재하면 해당 값을 아니면 2번째 매개변수로 적은 기본값으로 설정한다. 아래의 코드에서는 기본값을 0으로 하였..
백준 17071 자바 - 숨바꼭질 5 문제
www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 숨바꼭질 5에서는 동생이 움직이며 범위가 50만으로 증가한 조건이 주어집니다. 동생이 움직이기때문에 동일한 시간에 동일한 위치에 있어야만 합니다. 숨바꼭질 문제로 풀게 될 경우 수빈 : 3 → 6 → 12 동생 : 6 → 7 → 9 → 12 수빈은 2초에 12자리에 가서 방문처리를 하게되면 동생이 3초에 12에 도달하면서 12의 방문처리가 되어 있기 때문에 3초를 반환하게 ..
백준 13913 자바 - 숨바꼭질 4 문제
www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 문제의 확장으로 이전 위치를 배열에 넣어놓고 stack을 통해서 출력하게 하면 됩니다. 숨바꼭질 문제 - wellbell.tistory.com/64 랑 차이점이 거의 없어서 쉽게 해결할수 있습니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; imp..