Dev.baelanche

30의 배수인지를 확인하려면 두가지를 검사하면 된다. 1. 수에 0이 적어도 1개 있어야 한다. 2. 각 자리수의 합이 3의 배수여야 한다. 위 두가지를 만족한다면 각 자리수를 내림차순으로 정렬하여 출력해주면 된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); char c[] = sc.next().toCharArray(); Integer a[] = new Integer[c.length]; for(int i=0; i

각 문자열의 인덱스를 뒤로 미루면서 최소값을 구해야 한다. 예제로 풀면 다음과 같다. a d a a b c a a b a b b c 0 +1 +1 0 0 +1 A의 길이만큼 각 문자열을 비교했다. 각 인덱스가 일치하지 않으면 +1을 하였고 이 경우에는 3 이 나왔다. a d a a b c a a b a b b c 0 +1 0 +1 0 0 A를 한칸 미루어서 비교했다. 마찬가지로 일치하지 않을시 카운트하였고 앞의 경우보다 문자열이 더 일치하므로 답이 되겠다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String a = sc.next(); String b = sc.next()..

2 : 1 의 페어로 나가야 하므로 n/2 와 m 을 비교하여 큰쪽에서 인턴쉽에 나가게 한다. 출력할때는 n/2 와 m 중 작은쪽을 출력해주면 되겠다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int k = sc.nextInt(); for(int i=k; i>0; i--) { if(n/2 >= m) n--; else m--; } System.out.println(n/2 < m ? n/2 : m); } }

회의실배정 문제와 유사한데 조금 더 꼬아낸 문제다. 모든 수업이 가능해야 하므로 배열 정렬은 시작 시간에 대해 오름차순으로 정렬한다. 진행중이던 강의가 끝나면 그 강의실을 재사용할 수 있으므로 강의 정보를 담을 자료구조가 필요하다. 처음에는 큐를 이용하여 풀었는데 큐에서도 끝나는 시간이 빠른것을 우선으로 비교해야 하므로 우선순위 큐로 구현했다. 진행은 다음과 같다. 1. 강의 정보를 시작 시간에 따라 오름차순으로 정렬한다. 2. 강의 종료 시간을 우선순위 큐에 담는다. 3. 큐의 front 와 현재 강의 정보의 시작시간과 비교하여 시작시간이 크거나 같다면 큐를 pop 한다. (강의실이 비었다) 4. 마지막에 큐의 개수를 센다. 강의 정보를 구조체나 클래스로 구현하여도 되지만 회의실배정 때 소스를 끌어다가..

그리디 알고리즘 문제로 정렬 기준을 잘 잡아야 한다. 회의 정보에 대하여 1. 회의가 끝나는 시간이 가장 빠른순으로 오름차순 정렬한다. 2. 회의가 끝나는 시간이 같은 회의가 있다면 회의 시작시간이 빠른 것을 앞으로 한다. 많은 정렬 방법이 있겠지만 Comparator 를 구현하여 정렬했다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[][] = new int[n][2]; for(int i=0; i

예제 1, 6, 9, 3, 6, 7 로 설명해보겠다. (집중국 개수 k=2) 1. 오름차순으로 정렬한다. (1, 3, 6, 6, 7, 9) 2. 새로운 배열 m을 만들어 각 센서 사이의 거리 정보를 담는다. (2, 3, 0, 1, 2) 3. m의 값 중 가장 큰 수를 뺀다. (필자는 0을 대입하는 방식으로 했다.) 4. 3번을 k-1 번 반복한다. 5. m배열의 모든 값을 더하여 출력한다. 채점 99% 에서 계속 런타임에러가 발생했는데, n = 1 일때에 대한 예외가 발생해서였다. 아래 코드에서 n = 1이면 m 배열의 길이가 0이어서 예외처리를 해주었다. 마찬가지로 n

public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); char a[][] = new char[n][m]; for(int i=0; i

그리디 알고리즘 문제는 모두 최대값 구하는 방법만 찾아내면 된다. 입력이 40, 20, 30, 10 일때를 예로 들어보겠다. 1. 로프 중량을 오름차순으로 정렬한다. => 10, 20, 30, 40 2-1. 4개 로프를 모두 사용했을때 10 로프는 10*4의 무게를 들 수 있다. 2-2. 10을 제외한 3개 로프를 사용했을때 20 로프는 20*3의 무게를 들 수 있다. 2-3. 10, 20을 제외한 2개 로프를 사용했을때 30 로프는 30*2의 무게를 들 수 있다. 2-4. 40 로프만 사용했을때 40*1의 무게를 들 수 있다. 3. 위 경우 중 최대값을 출력한다. public class Main { public static void main(String[] args) { Scanner sc = new ..