[커뮤러닝 - 테스트] 그리디/정렬/이분탐색/시뮬레이션

🔎 개념

배열 초기화

        boolean[] visited = new boolean[n+1];
        Arrays.fill(visited, false);

문자열 아스키 값을 기준으로 정렬

Arrays.sort(배열,comparator)에서 comparator의 값이
음수인 경우 : 오름차순
양수인 경우 : 내림차순

이때 comparator인자에 compareTo 함수를 이용하여 음수/양수 리턴 가능, 이에따라 정렬 종류 설정

		// 오름차순
        Arrays.sort(str,(a,b)->{
        	return (a+b).compareTo(a+b);
        });
        
		// 내림차순
        Arrays.sort(str,(a,b)->{
        	return (b+a).compareTo(a+b);
        });

compareTo. : 숫자/문자열 비교

:compareTo는 두 값을 비교하여 int로 반환하는 함수.

• 숫자 : 비교대상 과 동일/보다 작을때/ 보다 클때 각각 0/-1/1 반환
• 문자열 비교시 비교 대상이 포함된 경우 문자열 길이차 반환/ 그 외의 경우 아스키 코드값 차 반환

---

📚 기지국 설치 - 그리디

수정 전

public class Java0708_1 {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;

        boolean[] visited = new boolean[n+1];
        Arrays.fill(visited, false);
        
        // statins내 통신되는 구역 방문 true
        for(int i:stations) {
        	
        	visited[i] = true;
        	for(int j=1;j<=w;j++) {
        		if(i-j>=0)
        			visited[i-j]=true;
        		if(i+j<=n)
        			visited[i+j] = true;
        	}
        }
        
        int start=0,end=0;
        boolean check=false;
        
        for(int i=1;i<=n;i++) {
        	if(check==false&&!visited[i]) {
        		start =i;
        		check=true;
        		
        		continue;
        	}
        	else if(visited[i]&&check) {
        		end = i;
        		answer+=ceil_fun(end-start,w); 
        		// 필요한 기지국 갯수 추가 
        		
        		check = false;
        	}
        	else if(check&&i==n) {
           		end = i+1;
           		answer+=ceil_fun(end-start,w);
        	}
        }

        return answer;
    }

	public int ceil_fun(int d,int w) {
		
		int x=d/(2*w+1);
		
		if(d%(2*w+1)!=0) // 올림 
			x++;
		
		return x;
	}
  
}

수정 후

현 기지국의 중심점을 기준으로 연산

public class Java0708_1 {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int start =1;
        
        for(int s:stations){
            if(start<s-w){
                int end = s-w;
                int length = end-start;                 
                
                answer += ceil_fun(length,w);
            }
            start = s+w+1;	// 기지국 추가할 구간의 다음 시작점
        }
        
        // 만약 마지막 기지국 + w 뒤에 또 기지국 설치할 구간이 있다면
        if (start<=n){
            int end = n+1;
            int length = end-start;
            
            answer += ceil_fun(length, w);
        }
        return answer;
    }
    
	public int ceil_fun(int d,int w) {
		
		int x=d/(2*w+1);
		
		if(d%(2*w+1)!=0) // 올림 
			x++;
		
		return x;
	}
}

📚 가장 큰 수(lv2)

public class Java0708_2 {
    public String solution(int[] numbers) {
        String answer = "";
        String[] str = new String[numbers.length];
        
        for(int i=0;i<numbers.length;i++) {
        	str[i] = String.valueOf(numbers[i]);
        	// or str[i] = numbers[i] + "";
        }
        
        Arrays.sort(str,(a,b)->{
        	return (b+a).compareTo(a+b);
        });
        // 내림차순 정렬, compareTo.: 배열에서 특정기준으로 정렬
        // 예) 30 과 3 을 정렬 할 때, 3 30 순서가 돼야 함
       	// 두 수 a,b를 순서를 번갈아가며 합친 수(330,303) 중 큰 값을 앞으로 정렬하겠다     
        
        for(String s:str) answer+=s;
        // answer = String.join("",str);
        
        return answer.charAt(0) == '0' ? "0":answer;
        // {0,0,0,0...} 일 경우 0 출력
    }
}

📚 숫자 게임

import java.util.Arrays;

public class Java0708_3 {
    public int solution(int[] A, int[] B) {
        int answer =0;
        
        // 오름차순 정렬한 뒤
        Arrays.sort(A);
        Arrays.sort(B);
        
        // 큰 수부터 비교하기 위해 뒤에서 부터 탐색
        // A보다 큰 B찾기
        int b_idx = A.length-1;
        for(int a_idx=A.length-1; a_idx>=0;a_idx--) {
        	if(B[b_idx] > A[a_idx]) {
        		answer++;
        		b_idx--;
        	}
        }
        
    return answer;
    }
    
}