[HSAT 4회 정기 코딩 인증평가 기출] 통근버스 출발 순서 검증하기

https://softeer.ai/practice/6257/history?questionType=ALGORITHM

Softeer - 현대자동차그룹 SW인재확보플랫폼

처음 생각한 풀이과정은 for문을 세 번 쓰는 것 이었는데, O(n^3)이어서 시간초과가 발생하는 로직이었습니다.

풀이과정

i=0 을 기준으로 둡니다.

이때 배열의 끝에서 부터 비교해야 시간복잡도를 줄일 수 있습니다.

1과 3은 arr[0] 의 값 4보다 작으므로 1씩 누적해줍니다.

 

 

 

그 다음 원소 5는 arr[0] 보다 큽니다. 

따라서 1을 누적하지 않고 그대로 2를 입력합니다.

또한 arr[0]보다 5가 크기때문에, 스택정렬을 수행할 수 없는 경우 입니다.

answer 에 누적된 값 2를 누적해줍니다.

 

그 다음 원소 2는 arr[0]보다 작으므로 1을 누적해줍니다.

 

위 과정을 i=1, i=2, ... i=N-1 까지 반복합니다.

 

코드로 나타내면 다음과 같습니다.

static void solve(){

        for(int i=0;i<N;i++){ // map배열 초기화시키기 (map[i][j] = map[i][j+1] + 1을 하기 때문에 처음에 초기화를 시켜줘야 함)
            if(arr[i] > arr[N-1]){
                map[i][N-1] = 1;
            }
        }

        for(int i=0;i<N;i++){
            for(int j=N-2;j>=i+1;j--){
                if(arr[i] > arr[j]){
                    map[i][j] = map[i][j+1] + 1;
                }else if(arr[i] == arr[j]){
                    map[i][j] = map[i][j+1];
                }else if(arr[i] < arr[j]){
                    answer += map[i][j+1]; // map[i][j+1] 이 1000 정도라고 하자. 그러면 최악의 경우 5000 * 5000 * 1000 으로 20억을 넘어감 따라서 long자료형을 사용해야 함.
                    map[i][j] = map[i][j+1];
                }
            }
        }
        
    }

 

이때 answer을 int형이 아닌 long형으로 둬야합니다.

 

answer을 단순히 +1 시켜주는 것이 아닌 map배열의 원소값을 누적시켜주기 때문입니다.

5000 * 5000 = 25,000,000 으로 int형의 범위를 벗어나지 않습니다.

 

answer은 map배열의 원소값을 누적시켜 주기 때문에 long형으로 둬야 합니다.

map[i][j+1] 을 약 1000이라면, 최악의 경우 5000 * 5000 * 1000 으로 int형의 범위 20억을 넘어가기 때문입니다.

 

 

알게된 점

• 배열의 원소를 앞에서 탐색할 때 시간초과가 난다면, 뒤에서 부터 탐색 하는 경우를 떠올려보자.
• 반복문만 보고 자료형의 크기를 정하면 안된다는 것을 알았습니다. 반복문 안에 값을 누적시키는 경우 자료형의 크기를 벗어날 수 있습니다.
• 로직이 맞는데 자꾸 틀린다면, int형을 long으로 바꿔보자.

 

 

전체코드

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

public class Main {

    static int N;
    static int[] arr;
    static int[][] map;
    static long answer;

    static void solve(){

        for(int i=0;i<N;i++){
            if(arr[i] > arr[N-1]){
                map[i][N-1] = 1;
            }
        }

        for(int i=0;i<N;i++){
            for(int j=N-2;j>=i+1;j--){
                if(arr[i] > arr[j]){
                    map[i][j] = map[i][j+1] + 1;
                }else if(arr[i] == arr[j]){
                    map[i][j] = map[i][j+1];
                }else if(arr[i] < arr[j]){
                    answer += map[i][j+1]; // map[i][j+1] 이 1000 정도라고 하자. 그러면 최악의 경우 5000 * 5000 * 1000 으로 20억을 넘어감 따라서 long자료형을 사용해야 함.
                    map[i][j] = map[i][j+1];
                }
            }
        }
        
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        answer = 0;
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        map = new int[N][N];

        solve();

        System.out.println(answer);

        
        
    }
}