[백준] 1337_올바른배열 / 투포인터

 

 

Sliver

 

문제

 

올바른 배열이란 어떤 배열 속에 있는 원소 중 5개가 연속적인 것을 말한다.

(연속적인 것이란 5개의 수를 정렬했을 때, 인접한 수의 차이가 1인 것을 말한다.)

예를 들어 배열 {6, 1, 9, 5, 7, 15, 8}은 올바른 배열이다. 왜냐하면 이 배열 속의 원소인 5, 6, 7, 8, 9가 연속이기 때문이다.

배열이 주어지면, 이 배열이 올바른 배열이 되게 하기 위해서 추가되어야 할 원소의 개수를 출력하는 프로그램을 작성하시오.

 

 

입력

 

첫째 줄에 배열의 크기 N이 주어진다.

N은 50보다 작거나 같은 자연수이다.

둘째 줄부터 N개의 줄에 배열의 원소가 한 줄에 하나씩 주어진다.

원소는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다. 배열에 중복되는 수는 없다.

 

 

출력

 

첫째 줄에 입력으로 주어진 배열이 올바른 배열이 되게 하기 위해서 추가되어야 할 원소의 최소 개수를 출력한다.

 

---

 

풀이

 

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr= new int[n];
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
		
        // 입력받은 값을 오름차순 정렬 
        Arrays.sort(arr);
        
        int l=0, r=1;
        int min=4; // 필요한 최소 추가 숫자 수
        while(l<=r){
            if(r==n) break;
            if(arr[r]-arr[l]<=4){
                min = Math.min(min,5-(r-l+1));
                r+=1; // 윈도우를 확장
            }
            else{
                l+=1;// 윈도우를 축소
            }
        }
        
        
        System.out.println(min);
    }
}

 

해결방법

• 값을 입력받아 배열에 저장하고 오름차순으로 정렬한다.
• 투포인터 알고리즘을 활용해 필요한 최소 문자 min을 찾는다.
  - 필요한 문자의 최대 갯수는 4개 이므로 min을 4로 초기화한다. 
  - 두 포인터l(왼쪽)은 맨 처음값, r(오른쪽)는 그다음값으로 초기화한다. 
  - l과r의 차이가 4보다 같거나 작으면, min을 현재 저장된 최소문자 수와 l과 r사이에 필요한 숫자의 개수 중 최솟값으로 업데이트한다.  이후 다음 탐색을 위해 r을 증가시켜 윈도우를 확장시킨다. 
  - l과r의 차이가 4보다 크면 두 포인터 사이를 줄이기 위해 l을 증가시킨다. 
  - l이 r보다 커지거나, r이 배열의 크기를 초과했다면 탐색을 종료한다.
• min에 저장된 값이 필요한 최소 문자의 수이다. 

 

 

투 포인터 알고리즘의 활용 

 

투 포인터 알고리즘은 두 개의 포인터를 사용하여 배열이나 리스트를 순회하면서 특정 조건을 만족하는 부분 배열이나 쌍을 찾는 효율적인 방법이다. 

 

• 정렬된 배열에서 특정 합이나 차이를 찾을 때:
• 부분 배열이나 부분 문자열의 길이 또는 값을 최적화할 때:
  • 일정 조건을 만족하는 가장 짧거나 가장 긴 부분 배열을 찾는 문제.
  • 연속된 요소들이 특정 조건을 만족하는 최대 길이의 부분 문자열을 찾는 문제.
  • 이런 문제에서 투 포인터를 사용하면 하나의 포인터가 조건을 만족할 때까지 확장하고, 조건을 만족하면 다른 포인터를 줄이면서 최적의 길이를 찾을 수 있다. 
• 교차하는 두 배열을 비교할 때:
• 특정 범위 내의 요소들을 관리할 때:

 

(출처 GPT)

---

https://www.acmicpc.net/submit/1337/86634474