HackerRank Java Sequence Equation

문제 풀기 : https://www.hackerrank.com/challenges/permutation-equation/problem

Given a sequence of  integers,  where each element is distinct and satisfies . For each where , find any integer  such that  and print the value of  on a new line.

For example, assume the sequence . Each value of  between  and , the length of the sequence, is analyzed as follows:

1. , so 
2. , so 
3. , so 
4. , so 
5. , so 

The values for  are . 

Function Description

Complete the permutationEquation function in the editor below. It should return an array of integers that represent the values of . 

permutationEquation has the following parameter(s): 

• p: an array of integers 

Input Format

The first line contains an integer , the number of elements in the sequence. 
The second line contains  space-separated integers  where .

Constraints

• , where .
• Each element in the sequence is distinct.

Output Format

For each  from  to , print an integer denoting any valid  satisfying the equation  on a new line.

Sample Input 0

3
2 3 1

Sample Output 0

2
3
1

Explanation 0

Given the values of , , and , we calculate and print the following values for each  from  to :

1. , so we print the value of  on a new line.
2. , so we print the value of  on a new line.
3. , so we print the value of  on a new line.

Sample Input 1

5
4 3 5 1 2

Sample Output 1

1
3
5
4
2

문제요약 : 첫 번째 줄에는 배열의 길이가 주어지고, 두 번째 라인에는 배열이 주어진다.

Sample input1, Sample Output1을 보면
p(p(y)) 에서 y를 구하면 된다.

1 = p(4) = p(p(1)) = 1            1은 배열의 4번째 인덱스에 위치하고 4는 1번째 인덱스에 위치한다 .
2 = p(5) = p(p(3)) = 3          2는 배열의 5번째 인덱스에 위치하고 5는 3번째 인덱스에 위치한다.
3 = p(2) = p(p(5)) = 5          3은 배열의 2번째 인덱스에 위치하고 2는 5번째 인덱스에 위치한다.
4 = p(1) = p(p(4)) = 4          4는 배열의 1번째 인덱스에 위치하고 1은 4번째 인덱스에 위치한다.
5 = p(3) = p(3(2)) = 2          5는 배열의 3번째 인덱스에 위치하고 3은 2번째 인덱스에 위치한다.


첫 번째 접근법 : 무식하게 while문을 계속 돌면서 1 ~ n 까지의 위치를 찾고 다시 찾은 인덱스의 위치를 찾는 방식을 생각 했었으나 시간복잡도 O(n^2) 너무 오래 걸릴거 같다고 생각했다. 답은 찾겠지만 배열의 길이가 길어질수록 속도는 어마어마하게 차이가 날 것으로 생각했다. 그래서 Pass~!

두 번째 접근법 : 문제 해결 과정에서 총 두 단계를 거치기 때문에 단계마다 Cache기법을 사용하면 될 것 같았다. 그래서 아래와 같이 시간복잡도 O(n)으로 코드를 짜고 문제를 해결했다.

p(x) 단계의 배열  firstCache를 만들어 주고
result 배열에 p(p(y))를 담아주고 리턴해주었다.