반응형

코딩테스트/Java 109

[JAVA] 탐욕법(Greedy) "단속카메라"

각각의 자동차 진입 시간~ -18 ~ -13 -14 ~ ~ ~ -5 -5 ~ -3 -20 ~ ~ ~ ~ ~ ~ ~ ~ 15 1. 차량이 나간 시점을 기준으로 오름차순으로 정렬한다. -위의 표는 정렬한 순서이다. 2. 차량이 들어온 시점이 기존 카메라 위치보다 우측에 있으면 해당 차량이 나가는 지점에 카메라를 설치한다. -파랑색 표시 지점이 알고리즘에 따라 카메라를 설치한 지점이다. import java.util.Arrays; class Solution { public int solution(int[][] routes) { int answer = 0; int camera = -30001; Arrays.sort(routes, (a,b)->Integer.compare(a[1],b[1])); for(int[] ..

[JAVA] 탐욕법(Greedy) "섬 연결하기"

(크루스칼알고리즘)주어진 모든 간선을 비용을 기준으로 오름차순 정렬한다.(PriorityQueue사용) 간선의 부모 노드를 기록한다. 싸이클이 만들어지지 않게 부모노드를 체크하며 간선을 연결한다. => Union 알고리즘을 이용한다! import java.util.*; class Solution { class Edge implements Comparable { int from, to, cost; Edge(int from, int to, int cost){//간선문제는 from to를 만들어주는것이 좋다. this.from = from; this.to = to; this.cost = cost; } @Override public int compareTo(Edge o){ return this.cost - o...

[JAVA] 탐욕법(Greedy) "구명보트"

int[] 에서 Integer[]로 변환하는 테크닉은 stream으로도 가능하지만, 효율성이 매우 떨어지므로 for문으로 하자. List도 필요할때만 사용하도록 하자. 이 역시 stream으로 Array를 asList를 이용하여 변환하능하지만 효율성이 매우 떨어진다. List의 remove와 같은 메소드는 동적으로 메모리를 사용하므로 효율성 측면에서 불리하다. 이왕이면 배열에서 index값을 이용하여 해결하자. 정렬 오름차순은 int[] Integer[] 다 가능하지만, 내림차순은 Integer[]만 가능하다(int[]는 Integer[]로 변환해야함) =>내림차순 : Arrays.sort( 배열, Collections.reverseOrder()); 나의코드 : 현실의 벽을 느꼈다. import java..

[JAVA] 탐욕법(Greedy) "큰 수 만들기"

값을 구하는 방식에 대해서 아이디어를 생각해내는 것이 어려워서 다른 이들의 코드를 참고했다. String에 저장된 숫자를 int값으로 추출해내는 테크닉 : .charAt(i)메소드 사용 char 값에서 '0' 을 빼면 int값이 나오는 테크닉 : c - '0' Stack에서 배열처럼 가져오기 : .get(i)메소드 사용 char배열을 String으로 변환하기 : char[] result = new [~]; return new String(result); 위와 같은 테크닉을 배울 수 있었다. class Solution { public String solution(String number, int k) { char[] result = new char[number.length() - k]; Stack stac..

[JAVA] 완전탐색 "소수 찾기"

완전탐색을 이용하여 소수를 찾는 알고리즘이다. 이전에 String을 parseInt하는 부분도 포함되어있는 문제다. 그리고, Permutation순열을 이용하여 수학적으로 재귀탐색을 하는 방식이며, Set을 이용하여 중복 제거를 하는 방식으로 알고리즘을 풀어야 했다. 필자는 Permutation부분을 스스로 구현하기 어려워 다른 이의 코드를 참고하였다. codevang.tistory.com/299?category=827588 import java.util.ArrayList; import java.util.List; import java.util.TreeSet; class Solution { private static TreeSet set = new TreeSet(); private int count; p..

[JAVA] 정렬 "가장 큰 수"

너무 복잡하게 생각하여 문제풀이를 실패했다. 단순하게 Sort에서 Compare 메소드를 오버라이드할때, String o1, o2를 비교하면, o1+o2 와 o2+o1을 Integer로 변환해서 비교하여 정렬하는 방식으로 해야한다. 가장 이해하기 쉬운 코드리뷰이다. import java.util.Arrays; import java.util.Comparator; class Solution { public String solution(int[] numbers) { String[] nums = new String[numbers.length]; for (int i=0; iString으로 변환해준다. 이러한 경우 String값을 많이 사용하는 케이스어서 첫번째 코드보다 두번째 코드에서 9배가량의 속도차이가 났다...

[JAVA] 힙 "이중우선순위큐"

우선순위 큐를 두개를 이용해서 풀어야하는 강박관념에 아래와 같이 풀었다. import java.util.PriorityQueue; class Solution { public int[] solution(String[] operations) { int[] answer = new int[2]; //오름차순 우선순위큐 PriorityQueue incQ = new PriorityQueue((o1, o2) -> o1 - o2); //내림차순 우선순위큐 PriorityQueue decQ = new PriorityQueue((o1, o2) -> o2 - o1); for(String op : operations){ //공백기준 분리 String[] str = op.split(" "); System.out.println(..

[JAVA] 힙 "디스크 컨트롤러"

이 문제는 2가지를 고려하여 코드를 짜야한다. 1. '작업소요시간'이 짧은 작업부터 수행해야한다. 2. 단, 하나의 작업이 끝나는 시점을 기준으로, '그 이전까지 요청된' 작업들에 한하여 '작업소요시간'을 비교한다. 필자는 런타임에러로 인해 코드작성에 실패하여, 다른사람의 코드를 리뷰하겠다. 첫번째는, 람다식을 이용하여 풀이를 하는 방식이다. import java.util.Arrays; import java.util.PriorityQueue; class Solution { public int solution(int[][] jobs) { int answer = 0; int end = 0; // 수행되고난 직후의 시간 int jobsIdx = 0; // jobs 배열의 인덱스 int count = 0; //..

반응형