[백준 1668번] 트로피 진열

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

1668번: 트로피 진열

접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

트로피가 선반에 놓여있고, 각 높이가 주어진다.

오른쪽, 왼쪽에서 봤을 때 보이는 트로피의 갯수를 출력하시오

 

시간제한 : 2초

1 ≤ N ≤ 50 (트로피 갯수)

 

 

2. 나의 방식대로 문제를 재정의 하자.

왼쪽에서 봤을 때 방법을 오른쪽에도 그대로 적용하면 됨

앞쪽의 트로피가 더 높으면 뒤쪽의 트로피는 보이지 않는다는 점을 이용

앞에서 봤을 때, 이미 나온 트로피보다 클 경우만 보이게 되므로 이 경우만 카운트하면 된다.

 

 

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

Integer[] 배열에 주어진 트로피 값을 저장한다

 

 

4. 어떻게 계산할 것인가?

1) 입력

BufferedReader

 

 

2) 시간 복잡도 계산

O(n)

 

 

5. 주의할 점은 무엇인가?

트로피 높이가 같으면 보이지 않음

 

6. 풀이 과정

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

public class q1668 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    Integer N = Integer.parseInt(br.readLine()); //트로피 갯수
    Integer[] ary = new Integer[N];

    Integer resultL = 0;
    Integer high = 0;
    for (int i = 0; i < N; i++) {
      ary[i] = Integer.parseInt(br.readLine());
      if (high < ary[i]) {
        resultL += 1;
        high = ary[i];
      }
    }

    Integer resultR = 0;
    high = 0;
    for (int i = N - 1; i >= 0; i--) {
      if (high < ary[i]) {
        resultR += 1;
        high = ary[i];
      }
    }

    System.out.println(resultL+"\n"+resultR);
    br.close();

  }

}

 

7. 개선점

미리 풀이를 생각하고 코드를 작성하는 습관이 필요하다