백준 #1138 한 줄로 서기

이번 문제는 문제를 아무리 읽어도 이해하기 힘듭니다.  국어 문제?  난이도는 Silver I인데, 문제를 해석하는데 어려움이 많았습니다.  예제라도 많았다면 유추를 했을텐데, 예제만 가지고 유추하는 것도 힘들었죠.

 

stand a line

 

https://www.acmicpc.net/problem/1138

1138번: 한 줄로 서기

 

문제를 재해석한다면 다음과 같습니다.

 

키가 1부터 N까지 사람들이 있습니다.  이들이 어떤 순서로 줄을 섭니다.  키를 그 사람의 번호라고 한다면, 4명의 사람들이 3 1 2 4 로 서 있다고 해보죠.  그러면 1번 사람부터 4번 사람까지 자기 왼쪽에 몇명이 본인보다 큰 사람들이 서 있는지 적습니다.  1번 사람은 1, 2번 사람도 1, 3번 사람은 0, 4번 사람도 0입니다.  그러면 그것을 순서대로 나열하면 1 1 0 0 이 됩니다.  이 나열된 숫자들이 주어지면, 이 나열된 숫자들을 만든 N명의 사람들 순서를 알아내는 문제입니다.

 

이건 정렬의 반대되는 개념입니다.  구현하는 방법으로는 선택정렬의 반대로 할 것이냐 아니면 삽입정렬의 반대로 할 것인가입니다.

전 처음 방법을 선택해서 풀었습니다.

 

주어진 숫자들이 2 1 1 0 이라고 해보죠.

 

2가 들어오면, 세번째 빈칸을 찾아서 1을 적습니다.

( 1 )

그 다음 1이 들어왔으니까, 두번째 빈칸을 찾아서 2를 적습니다.

( 2 )

1

그 다음에 1이 들어왔으니까, 두번째 빈칸을 찾아서 3을 적습니다.

2

1

( 3 )

마지막으로 0이 들어왔으니까, 첫번째 빈칸을 찾아서 4를 적습니다.

( 4 )

2

1

3

 

삽입정렬의 반대는, 거꾸로 진행합니다.  일단 1부터 4까지 적습니다.

1

2

3

4

4를 옮겨가야 하는데, 0이므로 무시합니다.

3을 오른쪽으로 한칸 옮겨갑니다.

1

2

4<--

-->3

2를 오른쪽으로 한칸 옮겨갑니다.

1

4<--

-->2

3

1을 오른쪽으로 두칸 옮겨갑니다.

4<--

2<--

-->1

3

 

둘다 비슷한 방법입니다.  결과도 같을 수밖에 없고요.  편하신 방법으로 구현하시면 될 듯 합니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//--------------------------------------------------------------------
//  baekjoon #1138 - Stand on a line
//    - by Aubrey Choi
//    - created at 2019-07-04
//--------------------------------------------------------------------
#include <stdio.h>

int main()
{
  int n, s, v[10] = {0, }, k, i;
  scanf("%d%d", &n, &s);
  v[s] = 1;
  for(v[s]=1, i=2; i <= n; i++)
  {
    scanf("%d", &s);
    for(k = 0; s >= 0; k++) if(!v[k]) s--;
    v[k - 1] = i;
  }
  for(i=0; i<n; i++) printf("%d ", v[i]); putchar('\n');
}