[SW Expert] 4796. 의석이의 우뚝 선 산

생각

Github - https://github.com/hellojdh/Code/blob/master/src/swexpert/d4/Q4796.java

우뚝 선 산을 찾아라, 우뚝 선 산이란 다음과 같다.
1 3 2 의 산들이 있을경우 1->3->2 가 가능하므로 우뚝 선 산은 1개이다.

다음의 경우를 보자
1 4 3 2 의 산들이 있을 경우
1) 1-> 4 -> 3 이 가능하다
2) 1-> 4 -> 3 -> 2 도 가능하다.
따라서 우뚝 선 산은 2개가 된다.

모든 산은 다른 숫자를 가지고 있다. 우뚝 선 산을 출력하여라.

처음 생각

2중 반복문으로 앞에서부터 index를 +1 씩 해나가면서 우뚝선 산을 찾아주려고 하였다.

▶ 주어진 N이 최대 1억이므로 시간 제한 2초를 벗어날 가능성이 크다고 판단하였다.

다음 생각

문제에서 준 예제를 종이로 옮겨적으면서 보니 (커지는 숫자들 개수) * (작아지는 숫자들 개수)를 하면 우뚝 선 산을 만들 수 있는 모든 조건이 완성이된다. 따라서 한번만 쭉 훝은후에 각 개수를 찾아 결과값에 더해주고 반복문의 index도 숫자들의 개수만큼 더해주었다.

방안

1) BufferedReader를 사용시 채점 데이터에서 1번 채점 후 런타임 에러가 발생한다. Scanner를 사용해서 입력 받는 것을 수정하였다. 일단은 사이트에 오류 제보를 해놓았다.

package swexpert.d4;
 
import java.io.IOException;
import java.util.Scanner;
 
public class Q4796 {
    static int n;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        // Input 파일 문제로 Scanner 사용
        Scanner sc = new Scanner(System.in);
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        int tc = Integer.parseInt(br.readLine());
        int tc = sc.nextInt();
        for(int i=1;i<=tc;i++) {
//            n = Integer.parseInt(br.readLine());
            n = sc.nextInt();
//            StringTokenizer st = new StringTokenizer(br.readLine());
            arr = new int[n];
            for(int j=0;j<n;j++)
                arr[j] = sc.nextInt();
//                arr[j] = Integer.parseInt(st.nextToken());
 
            System.out.println("#"+i+" "+solve());
        }
    }
    
    private static int solve() {
        int result = 0;
        // 2중 반복문으로 전체를 봐도 되지만, n이 최대 1억이므로 시간 초과의 가능성이 있다.
        // 따라서 1 2 3 7 6 5 4 일경우 올라가는것 3개, 내려가는것 3개로 9개의 조합이 가능해진다.
        // 이 개수 만큼 + 를 시키면서 반복문을 진행해주자.
        
        for(int j=0;j<n;) {
            int num = arr[j];
            boolean flag = true;
            int cntUp = 1,cntDown = 0;
            for(int k=j+1;k<n;k++) {
                // true일 경우는 커저야한다.
                if(flag) {
                    // 커질경우
                    if(num<arr[k]) {
                        num = arr[k];
                        cntUp++;
                    }else {
                        // 작아질 경우
                        flag = false;
                        num = arr[k];
                        cntUp--;
                        cntDown++;
                    }
                }else {
                    // false일 경우는 작아저야한다.
                    if(num>arr[k]) {
                        cntDown++;
                        num = arr[k];
                    }else {
                        break;
                    }
                }
            }
            // 조합 계산
            result += (cntUp*cntDown);
            // j 값 idx 올려주기
            j += cntUp+cntDown;
        }
        return result;
    }
}