문제

풀이과정

이 문제는 좀 많이 삽질을 했던 문제이다. 주어진 원소들을 배열에 넣고 퀵 정렬을 해야 하는건가 싶었는데, 작년 알고리즘 수업 때 비슷한 유형의 문제가 있었다.
Storing Files on Tape 이 문제와 유사한 방식으로 풀 수 있을 것같았다.
Storing Files on Tape 문제는 그리디 알고리즘을 이용하여 푸는 문제였다.
그리디 알고리즘에 대한 자세한 설명은 예전 공부블로그 주소인 https://minime00.tistory.com/22 이글을 보면 된다.

Storing Files On Tape문제

• 마그네틱 테이프에 n개의 파일을 저장할려고 한다.
• 테이프이기 때문에 1차원 배열이라고 생각한다.
• n개 파일의 길이 : L[i] - i번째 파일의 길이
• 순서대로 저장한다면 k번째 파일에 접근하기 위해 필요한 cost는 앞에 있는 파일들의 길이의 합이다.
  
  일단 저장을 해놓고 나면 자기자신을 읽기 위해서는 내 앞에 있는 것까지의 시간이 추가로 걸린다.
• 저장하는 파일의 순서를 잘 조정하면 걸리는 시간을 줄일 수 잇을 것이다.
  1) 모든 파일이 다 같은 빈도만큼 acces 될 것이다.라는 가정을 해보자
  2) n개 중에서 랜덤으로 어느 파일을 접근 할 때 필요한 cost의 기댓값은
  
  3) 만약에 우리가 테이프에 저장되는 순서를 바꾼다면 어떻게 될까
  ㅠ(i)를 i번째 위치에 저장할 파일의 번호라고 하자
  
  ㅠ(1)=6
  • 파이가 곧 순서이다.
    파이 함수를 우리가 어떻게 설정하느냐에 따라서 cost가 달라진다.
    문제 : 그러면 어떤 순서로 정하는 게 cost의 값을 최소화할 수 있을까?
    어떤 순서가 최적일까?
    1번위치에있는 파일은 어느 위치에 있는 파일을 읽을려고 할때마다 1번위치에 있는 파일은 흝고 지나갈 수밖에 없다.
    즉 , 앞에 있는 파일은 여러번 지나가야 한다
    그러면 앞에 있는 파일을 길이가 짦은 놈으로 두면 되겠다. 그니깐 매번 많이 지나가야 될 놈이면 이왕 짦은거를 두는게 낫지
    그럼 길이가 증가하는 순서대로 놓으면 되겠다

이 문제도 위 문제와 비슷한 상황으로 생각하여 풀었다.
사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있는지만을 기억한다.
한 줄로 n 명의 사람을 세울려고 한다.
줄을 세울려고 할때, 자신의 왼쪽에 있는 사람의 수가 큰 사람을 뒤로 세우고, 앞에는 자신의 왼쪽에 있는 사람의 수가 작은 사람부터 줄 세우면 된다.

코드

 package backjoon;
import java.io.IOException;
import java.util.*;
public class lineup_1138 {
        Scanner sc=new Scanner(System.in);
        ArrayList<Integer>list=new ArrayList<>();
        int n;
        n=sc.nextInt();
        int a[]=new int[n+1];
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
        }
        for(int i=n;i>=1;i--){
            list.add(a[i],i);
        }
        for(int k:list){
            System.out.println(k);
        }
    }
    }