SWEA 9088. 다이아몬드(Java)

9088. 다이아몬드

 

문제출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW7Oktj6WMQDFAWY&categoryId=AW7Oktj6WMQDFAWY&categoryType=CODE

SW Expert Academy

문제 조건 및 핵심 파악

- 1  ≤ 다이아몬드 크기 ≤ 10000

- 다이아 묶음 안의 모든 다이아몬드 크기 차이는 k이하여야 한다.
- 다이아 개수 : 1 ≤ N ≤ 1000, 크기차이: 0≤ K ≤ 10000)

=>다이아몬드 꾸러기를 구성한다 했을 때, 가장 많은 다이아를 줄 수 있는 다이아 최대개수 구하기

 

초기 소스 코드

package SWE;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class Ex_9088 {
	// SWE d4 9088. 다이아몬드

	// 최대 다이아 몬드 개수 반환 메소드
	static int maxDiamonds(ArrayList<Integer> arr, int n, int k) {
		int max = 1;
		for (int i = 0; i < n - 1; i++) {
			int count = 1;
			for (int j = i + 1; j < n; j++) {
				if (arr.get(j) - arr.get(i) <= k) {
					count++;
					if (max < count)
						max = count;
				}else
					break;
			}

		}
		arr.clear();
		return max;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(br.readLine());
		for (int test_case = 1; test_case <= T; test_case++) {
			// n과 k
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());

			ArrayList<Integer> arr = new ArrayList<Integer>();
			for (int i = 0; i < n; i++) {
				arr.add(Integer.parseInt(br.readLine()));
			}

			// 정렬
			arr.sort(null);

			// 검사
			int answer = maxDiamonds(arr,n, k);
			
			// 출력
			bw.write("#" + test_case + " " + answer + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}
}

/*
예시
2
2 0
1
1
3 3
1
6
4
*/

초기 코드 결과

솔직히 이 초기 코딩을 끝까지 완수하지 못했다. 
같이 스터디 그룹에서 공부하시는 허영운 님의 풀이가 내 초기 코딩과 비슷하여, 참고하여 완성했다.
(영운님 감사합니다. (꾸벅))

- 테스트 성공

- 풀이 법:

• ArrayList arr에 입력받은 다이아 크기들을 모두 저장. 그리고 정렬한다.
• for 루프를 2개를 돌리는데, i를 기준으로 그 뒤의 인덱스들을 하나하나 검사한다.
  뒤의 인덱스와의 차이가 k 이하면 count를 증가시킨다. 그렇지 않다면 뒤의 j값들은 k 넘게 차이나기 때문에 검사할 필요가 없다. 그러므로 break;
• i값(기준)이 바뀔 때마다 가장 큰 count를 찾기위해 변수 max에다 계속 갱신한다. max가 정답이 된다.  

- 실행시간은 다이아 모든의 개수가 적고 비교할 게 없으면 굉장히 빠른편이다.
- worst case일 경우 다이아가 10001개라면 비효율적인 코딩일 수 도 있다고 생각한다.

 

다른 사람 풀이 참조

 

 - 풀이 참조 ( https://ckddn9496.tistory.com/30)

 - 굉장히 참신하게도 배열의 index로 풀었다. 
 - 1부터 k+1까지의 다이아몬드 개수를 먼저 max에 저장한다. (1부터 k+1까지의 인덱스 개수는 k+1)
 - 저 k+1개의 몸뚱이를 length - k -1 번째 전까지 계속 이동 할 것인데 이때 i와 i + k + 1 의 자리를 계속 비교하면서
    k+1 몸뚱이가 이동할 때마다 커지는 지 계속 비교한다. max에다가 계속 갱신 해서 최댓값을 구한다.
 - 위의 초기코드와 비교했을 때, 이 경우는 worst case에서는 빠른 편에 속하겠지만, 다이아몬드 case가 적은 경우에도     똑같이 diamonsCounter.lenght - k 만큼 반복해야 하기 때문에, case가 적을 때는 비효율적일 수 있다.

 

static int[] diamondsCounter = new int[10001];
	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = sc.nextInt();
		int N, K;
		for (int test_case = 1; test_case <= T; test_case++) {
			N = sc.nextInt();
			K = sc.nextInt();
			
			Arrays.fill(diamondsCounter, 0);
			for (int i = 0; i < N; i++) {
				diamondsCounter[sc.nextInt()]++;
			}

			int max = 0;
			
			for (int j = 1; j <= 1 + K; j++) {
				max += diamondsCounter[j];
			}
			
			int sum = max;
			for (int i = 1; i < diamondsCounter.length - K - 1; i++) {
				sum = sum + diamondsCounter[i + K + 1] - diamondsCounter[i];
				if (max < sum)
					max = sum;
			}
			
			bw.write("#" + test_case + " " + max + "\n");
		}

		sc.close();
		bw.flush();
		bw.close();
	}
}

 

알게된 점

- 배열에 값을 넣는 것이 아닌, index에 하나씩 저장하여 index로 풀 수 있다는 점을 배웠다. 

- 이 과정에서

• Arrays.fill(배열이름, 채울요소)
• 배열이름[인덱스]++
• 위를 응용, 인덱스로 풀기: 배열이름[sc.nextInt()]++

등을 배웠다.