[Array, Sorting] 문제 이름 : Picking Tickets

문제 설명

주어진 배열을 정렬시킨 후 조건을 만족하는 부분 배열의 최대 크기 구하기

조건

1. 부분배열의 원소들은 이어져 있어야 함

2. 모든 원소 j와 j+1의 값의 차이의 절대값은 0 이나 1 이어야 함 

 

1. 사용 알고리즘

배열 정렬 

 

2. 문제 해결 아이디어 

우선 주어진 리스트를 오름차순 정렬시킨 후, 첫번째 원소부터 시작하여 조건을 만족하지 않는 원소를 만날 때까지 반복하여 조건을 만족하는 부분 배열들을 구하고, 그 중 가장 큰 크기의 부분배열을 찾는다. 

 

3. 코드 

구현방식)

주어진 리스트 오름차순 정렬 -> Collections 클래스의 sort() 사용

첫번째 원소부터 조건 만족하는 부분 배열 찾기 -> 반복문 사용하여 각 리스트의 원소 접근 

//부분배열의 최대 크기 반환!
static int maxTickets(List<Integer> tickets) {
	 int maxSubSequenceSize = 0;
	 
     Collections.sort(tickets); //주어진 리스트 오름차순 정렬 
     
     int beforeVal = 0;
     int subSequenceSize = 1;
     beforeVal = tickets.get(0); //리스트의 첫 번째 원소부터 시작 
     for(int i = 1; i < tickets.size(); i++){
         int difference = tickets.get(i) - beforeVal; //j+1 - j
         beforeVal = tickets.get(i);
         if(difference <= 1) { //주어진 조건 만족 시
             beforeArrSize++; //부분배열 크기 증가 
         }
         else {
             if(maxSubSequenceSize < subSequenceSize)
                 maxSubSequenceSize = subSequenceSize; //부분 배열 최대 크기 업데이트 
             subSequenceSize = 1; //부분 배열 크기 초기화 
         }
     }
     return maxSubSequenceSize;
}

위의 작성 코드 개선)

-> 리스트의 index 값의 차이로 부분 배열의 크기 측정하기

-> Math 클래스의 max() 사용하기 

static int maxTickets(List<Integer> tickets) {
	int maxSubSequenceSize = 0;
	 
    Collections.sort(tickets); //주어진 리스트 오름차순 정렬 

    startIndex = 0;
    listSize = tickets.size();
    while(startIndex < listSize) {
    	int compareIndex = startIndex + 1;
    	while(compareIndex < listSize && tickets[compareIndex] - tickets[compareIndex-1] //주어진 조건 만족 시 <= 1)
    		compareIndex += 1;
    	maxSubSequenceSize = Math.max(maxSubSequenceSize, compareIndex - startIndex); //compareIndex - startIndex = 부분 배열의 크기 
    	startIndex = compareIndex;
    }
    
    return maxSubSequenceSize;
}