Menu

Subscribe

[JAVA/SWEA] 9088: 다이아몬드

HEESOO on Swea

👀 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW7Oktj6WMQDFAWY

👊 도전

1. 설계

  1. N개 다이아몬드를 오름차순 정렬한다.
  2. 가장 큰 값과 가장 작은 값의 차이가 k이하인 경우에는 바로 N을 리턴한다.
  3. 아닌 경우, i번째 다이아몬드와의 차이가 k이하인 것을 일일이 찾는다.
  4. 이 중 가장 큰 값을 출력한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import java.util.*;
/**
 *
 * @author HEESOO
 *
 */
class Solution
{
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();

		for(int test_case = 1; test_case <= T; test_case++)
		{			
            int n=sc.nextInt();
            int k=sc.nextInt();
            int[] number=new int[n];
            int max=Integer.MIN_VALUE, min=Integer.MAX_VALUE;
            for(int i=0;i<n;i++){
                number[i]=sc.nextInt();
                max=Math.max(max, number[i]);
                min=Math.min(min, number[i]);
            }
                
            Arrays.sort(number);
            if(max-min<=k) {
                System.out.println("#"+test_case+" "+n);
                continue;
            }
            
            int answer=0;
            for(int i=0;i<n;i++){
                int cnt=1;
                for(int j=i+1;j<n;j++){
                    if(Math.abs(number[i]-number[j])<=k) cnt++;
                    else break;
                }
                answer=Math.max(answer, cnt);
            }
            System.out.println("#"+test_case+" "+answer);
		}
	}
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 다이아몬드의 max와 min의 차이가 k이하면 바로 N을 리턴한다
    • 이 경우 N개를 리턴하므로 굳이 아래 for문을 실행하지 않아도 된다. 따라서 return으로 끝낸다.
  2. i와 차이가 k이하인 j를 모두 찾는다
    • i로 모든 다이아몬드를 체크한다.
    • j로 i와 차이가 k이하인 것을 찾는다. 이때 (i, j) 비교와 (j, i) 비교는 같은 것이므로 오름차순으로 정렬한 후, j=i+1로 지정하여 중복 체크를 없앤다.
    • 오름차순으로 정렬했는데 i, j의 차이가 k이상이면 그 뒤의 j값들과도 무조건 k이상 차이가 나므로 break문을 통해 비교를 그만한다.
    • i에 관해 비교가 끝나면 cnt와 기존 answer중 더 큰 값을 answer에 저장하여 최댓값을 answer에 저장할 수 있게 한다.

👏 해결 완료!