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

알고리즘/백준

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

코딍코딍 2022. 7. 18. 10:20

https://www.acmicpc.net/problem/14659

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

첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000) 둘째 줄에 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. (1 ≤ 높이 ≤ 100,000) 각각 봉우리의 높이는 중복 없이

www.acmicpc.net

문제

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader((new InputStreamReader(System.in)));
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(br.readLine());

        String srr[] = br.readLine().split(" ");
        int count=0;
        int max = count;
        int cnt=Integer.parseInt(srr[0]);
        
        for(int i=1;i<n;i++) {
            if(cnt>Integer.parseInt(srr[i])){
                count++;
            } else {
                cnt=Integer.parseInt(srr[i]);
                if(max<count) max=count;
                count=0;
            }
        }
        if(max<count) max=count;
        System.out.println(max);
    }
}

해결방법

활잡이는 자신보다 낮은 봉우리에 서있는 적들만 처치할 수 있으니 오른쪽으로 이동하면서 높은 봉우리에 있는 활잡이를 기준으로 세주면 된다.

슈도코드

입력받은 문자열 배열로 변환
n-1번 반복
1. 현재 봉우리(cnt)가 오른쪽의 봉우리보다 크다면 count++
2. 아니라면 현재 봉우리 재 설정, max값 갱신, count 초기화
max값 갱신을 하지 못하고 반복문이 종료될 수 있으므로 max 값 갱신
출력