(BOJ) 1849 순열 / 1777 순열복원

<1849 순열>

문제: https://www.acmicpc.net/problem/1849

푸는 방법:

예제) A[1]=5, A[2]=0, A[3]=1, .......

-> 1은 왼쪽에서부터 5번째에 넣고, 2번은 왼쪽에서부터 0번째에 값을 넣는다

(왼쪽에서 오른쪽으로 가면서 자리를 찾아갈 때 이미 차있는 곳은 넘어간다)

자리	1	2	3	4	5	6	7	8
번호	2	7	3	5	4	1	8	6

 result[6]=1 -> result[1]= 2  -> result[3]=3  -> result[3]=4 -> ..... 

어느 위치에 숫자가 존재하여 그만큼 넘어가야할지를 세그로 찾음

숫자가 들어간 위치에는 update() 함수를 통해 0을 넣는다. (원래는 각 자리에 1 들어있음)

소스코드:

https://gist.github.com/hovy1994/7d9134b9a9122e553c39d28d5a7e5b01#file-1849

<1777 순열복원>

문제: https://www.acmicpc.net/problem/1777

푸는 방법:

위 문제와 거의 같다.

위와 반대로 

예제) A[8]=0, A[7]=2, A[6]=1, .... 순으로 보면서

오른쪽에서 왼쪽으로 숫자를 채워 넣는다 

 result[8]=8 -> result[5]= 7  -> result[6]=6  -> result[3]=5 -> ..... 

소스코드: 

 https://gist.github.com/hovy1994/7d9134b9a9122e553c39d28d5a7e5b01#file-1777

-> 벡터로 푼 사람들이 많길래 풀어봤더니 

    시간이 776ms가 걸렸다...  (위에 세그로 풀면 52ms)