[소프티어] 통근버스 출발 순서 검증하기 자바 풀이 dp DP (HSAT 4회 정기 코딩 인증평가 기출)
https://softeer.ai/practice/6257
Softeer - 현대자동차그룹 SW인재확보플랫폼
softeer.ai
| JavaScript | 2초 | 1024MB |
| C | 1초 | 1024MB |
| C++ | 1초 | 1024MB |
| Java | 2초 | 1024MB |
| Python | 2초 | 1024MB |
현대자동차그룹 연구소에서는 임직원들의 편의를 위해 출퇴근 통근 버스를 제공하고 있다.
퇴근 시간이 되면 연구소 주차장에는 수 많은 버스들이 일렬로 주차되어 있다. 퇴근 버스는 번호순서 대로 출발해야 하는데, 주차장은 폭이 좁아 앞의 버스가 모두 나가야 뒤의 버스가 나갈 수 있는 구조로 되어 있다.
버스를 순서에 맞게 출발시키기 위해, 연구소 주차장의 맞은편에 임시 주차장을 추가로 건설하였다. 이렇게 만든 임시 주차장은 출입구가 하나밖에 없는 데다가, 폭이 좁아서 스택(Stack)처럼 맨 처음 들어간 버스는 맨 마지막에 나올 수 있다. 또한, 한 번 임시 주차장으로 이동했던 버스는 다시 원래의 주차장으로 이동할 수 없다.
위와 같은 상황에서 퇴근 버스를 번호 순서대로 출발시키는 문제는 스택 정렬로 모델링할 수 있다.
스택 정렬이란, a1, a2, ..., an을 정렬할 때, 앞에서부터 순서대로 스택에 Push하거나, 스택에서 Pop하여 출력하는 것을 골라서 반복하여, 정렬된 순서로 출력되도록 하는 것이다. Stack은 가장 나중에 들어간(Push) 자료가 가장 먼저 꺼내지는(Pop) 자료구조이다. 즉, 주어진 수가 3, 1, 2의 세개라면, 3을 Push (스택에 3만 저장됨), 1을 Push (스택에 3, 1이 저장됨), 스택에서 Pop 하여 출력 (스택에 가장 나중에 들어간 1이 Pop 되어 출력됨), 2를 Push, Pop하여 출력 (2가 출력됨), Pop하여 출력으로 마지막으로 3을 출력할 수 있다.
아래의 그림은 이러한 과정을 보여준다.
하지만, 모든 경우의 순열을 스택 정렬을 통해 순서대로 정렬할 수 있는 것은 아니다. 주어지는 입력에 따라 스택 정렬이 불가능한 경우도 있다.
임의의 자연수 i < j < k에 대해서, ai < aj이고 ai > ak인 경우가 하나라도 있으면 정렬이 불가능하다는 것이 증명되어 있다. 즉, 버스들의 번호가 a1, a2, …, an와 같이 주어질 때, 이와 같은 (i, j, k)의 사례가 있다면, (오름차순) 순서대로 스택 정렬이 불가능하다.
연구소에서 개발자로 일하고 있는 당신은, 연구소 주차장에 주차되어 있는 버스들이 임시 주차장을 활용하여 번호 순서대로(오름차순) 출발할 수 있는지 알아보는 프로그램을 만들어보려고 한다. 버스들이 번호 순서대로 출발하는 것이 불가능한 지 알아보기 위해, 그것을 증명할 수 있는 서로 다른 (i, j, k)의 케이스들을 몇 개나 찾을 수 있는 지 출력하여라. (만약, 출력값이 0이라면 버스들이 위의 과정을 통해, 순서대로 출발할 수 있음을 의미한다.)
3≤N≤5,000인 정수
버스 번호는 서로 중복되지 않는다.
첫 번째줄에 수열의 크기 N이 주어진다.
두 번째줄에 1부터 N까지의 정수가 재배열된 수열이 공백을 사이에 두고 주어진다.
문제에서 주어진 조건을 만족하는 서로 다른 (i, j, k) 순서쌍의 개수를 출력한다.
3 3 1 2
0
3 2 3 1
1
첫 번째 위치에는 2번 버스, 두 번째 위치에는 3번 버스, 그리고 세 번째 위치에는 1번 버스가 기다리고 있기 때문에(a1=2, a2=3, a3=1), 순서쌍이 (1, 2, 3)일 때, 문제의 조건에 따라 순서대로 출발이 불가능함을 증명할 수 있다.
4 4 3 1 2
0
5 4 2 5 3 1
4
순서쌍이 (1, 3, 4), (1, 3, 5), (2, 3, 5), (2, 4, 5)인 경우에 각각의 버스 번호들의 쌍이 [4번, 5번, 3번], [4번, 5번, 1번], [2번, 5번, 1번], [2번, 3번, 1번]이 되어, 버스를 순서대로 출발시킬 수 없음을 증명할 수 있다.
시간초과
정수 n은 5000까지이고
5000*5000*5000 = 1250억이니 시간초과 날 수 밖에...
그래도 문제를 이해하긴 했다는 증거 !
// 답은 맞지만, 시간초과 발생
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
int a = arr[i];
int b = arr[j];
if(a>b){
continue;
}
// a < b
for(int k=j+1; k<n; k++){
int c = arr[k];
if(a > c){
dap++;
// System.out.println(a + " " + b + " " + c);
}
}
}
}코드 보다시피
두 숫자를 찍어놓고 a<b가 성립하면
a>c가 성립하는걸 하나하나 다 체크했던게 문제다
이전의 결과값을 토대로 하는 점화식을 세워야한다.
핵심설명
A < B 조건은 일단 무시해라.
문제는 A > C 경우이다.
A > C를 구하기 위한 이차원 배열부터 설명하자면,
dp[i][j] 변수명을 가진 dp배열은 = "
(I번째 숫자A)와 (J번째 숫자C)를 볼건데,
(I번째 숫자A) > (J+1번째~n번째 C의 우측에위치한숫자들) 가 성립하는 개수
" 이다.
그리고 배열의 우측부터 계산해서 직전값 +1을 해주면 된다.
ex. 8 6 9 7 5 에서,
8과 9를 볼건데
9 우측에 존재하는 7,5가 둘다 8보다 작으니
2개인건 맞는데 일일이 체크하지 말고
8과 9를 볼껀데,
9 우측에 존재하는 7이 8보다 작으니
9 우측에 존재하는 7의 바로 우측에 위치한 5의 DP값+1을 해주자
수도코드로 나타내면
if ( arr[0]=8 > arr[2+1]=9 )
then dp[0][2] = dp[0][3]+1;
else dp[0][2] = dp[0][3];
시간초과 해결 DP 구현
A > C 인 경우 계산해주기
arr[i][j] = "C 보다 오른쪽에 있는 배열 값들에 대해, A보다 작은 수들의 개수"인 개수를 저장
arr[0][4] = "1 보다 오른쪽에 있는 배열 값들에 대해, 4보다 작은 수들의 개수"인 0개*를 저장
arr[0][3] = "3 보다 오른쪽에 있는 배열 값들에 대해, 4보다 작은 수들의 개수"인 1개를 저장
arr[0][2] = "5 보다 오른쪽에 있는 배열 값들에 대해, 4보다 작은 수들의 개수"인 2개를 저장
arr[0][1] = "2 보다 오른쪽에 있는 배열 값들에 대해, 4보다 작은 수들의 개수"인 2개를 저장
arr[0][0] = "4 보다 오른쪽에 있는 배열 값들에 대해, 4보다 작은 수들의 개수"인 3개를 저장
4 2 5 3 1
4 3 2 2 1 0개*
2 <- <- <-
5
3
1
전체코드
import java.io.*;
import java.util.*;
public class Main {
public static long dap = 0;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int arr[] = new int[n+2];
for(int i=1; i<n+1; i++){
int num = Integer.parseInt(st.nextToken());
arr[i] = num;
}
// 답은 맞지만, 시간초과 발생
// for(int i=0; i<n; i++){
// for(int j=i+1; j<n; j++){
// int a = arr[i];
// int b = arr[j];
//
// if(a>b){
// continue;
// }
// // a < b
// for(int k=j+1; k<n; k++){
// int c = arr[k];
// if(a > c){
// dap++;
// // System.out.println(a + " " + b + " " + c);
// }
// }
// }
// }
// 시간초과 해결 DP 구현
// A > C 인 경우 계산해주기
// arr[0][4] = "1 보다 오른쪽에 있는 배열 값들에 대해, 4보다 작은 수들의 개수"인 0개*를 저장
// arr[0][3] = "3 보다 오른쪽에 있는 배열 값들에 대해, 4보다 작은 수들의 개수"인 1개를 저장
// arr[0][2] = "5 보다 오른쪽에 있는 배열 값들에 대해, 4보다 작은 수들의 개수"인 2개를 저장
// arr[0][1] = "2 보다 오른쪽에 있는 배열 값들에 대해, 4보다 작은 수들의 개수"인 2개를 저장
// arr[0][0] = "4 보다 오른쪽에 있는 배열 값들에 대해, 4보다 작은 수들의 개수"인 3개를 저장
// 4 2 5 3 1
// 4 3 2 2 1 0개*
// 2 <- <- <-
// 5
// 3
// 1
// DP 저장
int dp[][] = new int[n+2][n+2];
for(int i=1; i<=n; i++){
for(int j=n-1; j>=1; j--){
if(arr[i] > arr[j+1]){
dp[i][j] = dp[i][j+1] + 1;
}else{
dp[i][j] = dp[i][j+1];
}
}
}
// DP 출력
// for(int i=1; i<=n; i++){
// for(int j=1; j<=n; j++){
// if(arr[i] < arr[j]){
// System.out.print("+" + dp[i][j]);
// }
// else{
// System.out.print(" " + dp[i][j]);
// }
// }
// System.out.println();
// }
// A < B 더해주기
for(int i=1; i<=n; i++){
for(int j=i+1; j<=n; j++){
if(arr[i] < arr[j]){
dap += dp[i][j];
// System.out.print("\t" + arr[i] + "," + arr[j] + "=" + dp[i][j]);
}
}
// System.out.println();
}
bw.write(String.valueOf(dap));
bw.flush();
bw.close();
return;
}
}
'알고리즘 단련장 > 소프티어' 카테고리의 다른 글
| [소프티어] 슈퍼컴퓨터 클러스터 자바 풀이 이진탐색 시간초과 해결 (HSAT 4회 정기 코딩 인증평가 기출) (0) | 2024.08.28 |
|---|---|
| [소프티어] 업무 처리 자바 풀이 이진트리 (HSAT 5회 정기 코딩 인증평가 기출) (0) | 2024.08.27 |
| [소프티어] 택배 마스터 광우 자바 풀이 dfs 쉽게 접근하기 (2) | 2024.08.26 |
| [소프티어] 플레이페어 암호 자바 풀이 시간초과 해결 완료 (HSAT 3회 정기 코딩 인증평가 기출) (0) | 2024.08.25 |
| [소프티어] 함께하는 효도 자바 풀이 dfs 쉽게 설명 쉬운 해설 (0) | 2024.08.25 |