[백준] 알고리즘 분류(그리디 알고리즘,JAVA)14659번, 한조서열정리하고옴ㅋㅋ

문제 링크

14659번: 한조서열정리하고옴ㅋㅋ

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 자신보다 높은 봉오리에 만났을 때 용은 더 이상 이동하지 못하고 처지하지도 못합니다.

2. 최고의 활잡이는 가장 많이 적을 처치하는 활잡이입니다.

3. 최고의 활잡이가 처치한 적의 숫자를 결과로 출력합니다.

4. 용은 항상 오른쪽으로만 나아갑니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 각 활잡이가 오른쪽으로 쏘았을 때 처치하는 횟수를 탐색합니다.

 

3. 최고의 활잡이를 찾은 후 처치한 적의 횟수를 결과로 출력합니다.

 

 

활잡이 처치 탐색

 

 

활잡이의 봉우리 정보를 저장한 배열을 이용해서

 

오른쪽으로 이동하여 자신의 봉우리보다 높은 봉우리를 만날 때까지 모두 처치합니다.

 

예를 들어.

 

7 4 8 6

 

1번째 봉우리에서 탐색할 때

 

7 4 8 6

 

파란색 부분까지 처치한 뒤 높은 봉우리를 만나므로 1명만 처리가 가능합니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N = 7

봉우리 정보

 

	봉우리 1	봉우리 2	봉우리 3	봉우리 4	봉우리 5	봉우리 6	봉우리 7
높이	6	4	10	2	5	7	11

 

2. 각 활잡이가 오른쪽으로 쏘았을 때 처치하는 횟수를 탐색합니다.

 

각 활잡이 탐색!

 

봉우리 1번 탐색

	봉우리 1	봉우리 2	봉우리 3	봉우리 4	봉우리 5	봉우리 6	봉우리 7
높이	6	4	10	2	5	7	11

1마리 처치!

 

봉우리 2번 탐색

	봉우리 1	봉우리 2	봉우리 3	봉우리 4	봉우리 5	봉우리 6	봉우리 7
높이	6	4	10	2	5	7	11

0마리 처치!

 

봉우리 3번 탐색

	봉우리 1	봉우리 2	봉우리 3	봉우리 4	봉우리 5	봉우리 6	봉우리 7
높이	6	4	10	2	5	7	11

3마리 처치!(최고의 활잡이)

 

 

봉우리 4번 탐색

	봉우리 1	봉우리 2	봉우리 3	봉우리 4	봉우리 5	봉우리 6	봉우리 7
높이	6	4	10	2	5	7	11

2마리 처치!

봉우리 5번 탐색

	봉우리 1	봉우리 2	봉우리 3	봉우리 4	봉우리 5	봉우리 6	봉우리 7
높이	6	4	10	2	5	7	11

1마리 처치!

 

봉우리 6번 탐색

	봉우리 1	봉우리 2	봉우리 3	봉우리 4	봉우리 5	봉우리 6	봉우리 7
높이	6	4	10	2	5	7	11

0마리 처치!

 

 

봉우리 7번 탐색

	봉우리 1	봉우리 2	봉우리 3	봉우리 4	봉우리 5	봉우리 6	봉우리 7
높이	6	4	10	2	5	7	11

0마리 처치!

 

3. 최고의 활잡이를 찾은 후 처치한 적의 횟수를 결과로 출력합니다.

 

최고의 활잡이가 처리한 숫자 : 3

 

3을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 봉우리 정보를 띄어쓰기 기준 나누었습니다.
• 각 봉우리가 오른쪽 방향 처치할 수 있는 횟수를 탐색하여 최고의 활잡이를 찾습니다.
• 최고의 활잡이가 처치한 횟수를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //봉우리 정보 저장
        for(int i=0;i<N;i++)
            arr[i] = Integer.parseInt(st.nextToken());
        int answer = Integer.MIN_VALUE;
        //각 봉우리에 활잡이 탐색
        for(int i=0;i<N;i++){
            int count = 0;
            int h = arr[i];
            for(int j=i+1;j<N;j++){
                if(h < arr[j])	//더 높은 봉우리 만났을 때 종료
                    break;
                else	//처치 성공!
                    count++;
            }
            //최고의 활잡이 비교하기
            answer = Math.max(answer, count);
        }
        bw.write(answer + "");	//BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}