[softeer] 통근버스 출발 순서 검증하기 - python, java

📖문제

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

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

✨핵심 내용

nums[i] < nums[j] and nums[i] > nums[k] 를 만족하는 배열을 찾아 개수를 세기

제약 조건: 3 <= N <= 5000 인 정수

🤔해결 아이디어 

1. 3중 for 문 사용 (시간 초과)

모든 가능한 조합을 만들고, if 문으로 문제 조건을 판단 -> O(n^3) 시간 복잡도로 시간 초과!

 

2. 백트레킹 (시간 초과)

배열의 조합을 백트래킹을 활용하여 만들고 조건 판단 -> O(n^3) 시간 복잡도로 시간 초과!

 

3. 누적합 (정답)

제약 조건이 3 <= N <= 5000으로 걸려 있기에 O(n^2) 이하 풀이 법을 생각해야 한다.

 

i와 k의 조합을 기준으로 nums[i]와 nums[k] 사이의 nums[i] 보다 큰 값의 개수를 세는 방법을 사용할 수 있다. 

 

1. nums[i] < nums[k] 라면
nums[k] < nums[i] < nums[j] 라는 조건에는 맞지 않으나
i 이후에 등장하는 nums[i] 보다 큰 수에 해당한다. (bigger += 1)



2. nums[i] > nums[k] 라면
문제의 조건의 일부에 해당한다.
그러나 i 와 k 사이에 등장한 nums[i] 보다 큰 수 (bigger)를 더해 값(ans)을 갱신하는 과정을 통해 문제의 조건을 모두 만족시킬 수 있다. 

 

✅정답 코드 (python)

import sys
n = int(input())
nums = list(map(int, input().split()))
ans = 0

for i in range(n):
    bigger = 0
    for k in range(i + 1, n):
        if nums[i] < nums[k]: # 조건에 안맞음, a[i] 보다 큰 수라는 것만 체크
            bigger += 1
        else: # 조건에 맞음 - 기존에 세었던 a[i] 보다 큰 값들 더해주기
            ans += bigger

print(ans)

 

✅정답 코드 (java)

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

public class Main {
    static int n;
    static int[] nums;
    static int bigger;
    static long ans; // 자료형 주의!
    
    public static void main(String[] args) throws IOException{
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        
        nums = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < n; i++){
            nums[i] = Integer.parseInt(st.nextToken());    
        }

        // 누적합
        for(int i = 0 ; i < n; i++) {
            bigger = 0;
            for (int k = i + 1; k < n; k++) {
                if (nums[i] < nums[k]) // 조건에 안맞음, a[i] 보다 큰 수라는 것만 체크
                    bigger += 1;
                else // 조건에 맞음 - 기존에 세었던 a[i] 보다 큰 값들 더해주기
                    ans += bigger;
            }
        }

        // output
        System.out.println(ans);
    }
}