[Java][자바][백준][1668번] 트로피 진열 - 탐색

문제 설명

민식이는 “오민식”이라는 팀이름으로 수없이 많은 로봇대회를 우승했다. 따라서 민식이의 집에는 트로피가 많다. 민식이는 트로피를 어떤 선반 위에 올려놨다. 이 선반은 민식이의 방문을 열고 들어가자마자 선반의 왼쪽이 보인다. 다른말로 하자면, 뒤의 트로피가 앞의 트로피에 가려져 있다는 말이다.

안타깝게도, 높이가 큰 트로피가 높이가 작은 트로피의 왼쪽에 있다면, 높이가 작은 트로피는 큰 트로피에 가려서 보이지 않게 된다. 트로피는 자기의 앞에 (보는 사람의 관점에서) 자기보다 높이가 작은 트로피가 있을 때만 보이게 된다. 민식이는 선반을 180도 회전시켜서 트로피가 보이는 개수를 변하게 할 수도 있다.

선반위에 올려져 있는 트로피의 높이가 주어졌을 때, 왼쪽에서 봤을 때 보이는 개수와, 오른쪽에서 봤을 때 보이는 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 트로피의 개수 N (1 ≤ N ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 왼쪽의 트로피부터 차례대로 높이가 주어진다.

출력

첫째 줄에 왼쪽에서 봤을 때 보이는 개수, 둘째 줄에 오른쪽에서 봤을 때 보이는 개수를 출력한다.

 

생각

왼쪽과 오른쪽에서 각각 봐줘야한다. 

왼쪽에서 쳐다보는 예를 생각해보겠다. 가장 왼쪽에 있는 트로피가 가장 높다면 하나만 보일 것이다.

하지만 예를 들어 2 1 4 3 2 라고 해보면 1은 가려지지만 4는 보이고 그 뒤부터는 안보인다.

따라서 왼쪽부터, 혹은 오른쪽부터 탐색하면서 현재의 최댓값을 구해서 그 최댓값보다 크면 보이고 작으면 보이지 않는닥 판단하면 된다.

 

코드에 주석을 통해 더 설명을 하겠다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class Main {
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> arr = new ArrayList<Integer>();
        
        int n = Integer.parseInt(br.readLine());
        
        for(int i=0; i<n; i++) {
            arr.add(Integer.parseInt(br.readLine()));
        }
        
        int count1 = 1;
        int max1 = Integer.MIN_VALUE;
        int count2 = 1;
        int max2 = Integer.MIN_VALUE;
        
        //1번: 왼쪽에서 볼 때
        //각 과정마다 최댓값을 갱신해주고, 그 다음의 트로피가 최댓값보다 작거나 같다면
        //continue를 통해 넘어간다.
        for(int i=0; i<n-1; i++) {
            if(max1 < arr.get(i)) {
                max1 = arr.get(i);
            }
            
            if(max1 >= arr.get(i+1)) {
                continue;
            }
            count1++;
        }
        
        //2번 과정: 오른쪽에서 볼 때
        //방법은 동일하다.
        for(int i=n-1; i>0; i--) {
            if(max2 < arr.get(i)) {
                max2 = arr.get(i);
            }
            
            if(max2 >= arr.get(i-1)) {
                continue;
            }
            count2++;
        }
        
        System.out.println(count1 + " " + count2);
    }
}