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))를 담아주고 리턴해주었다.




댓글

이 블로그의 인기 게시물

About JVM Warm up

About idempotent

About Kafka Basic

About ZGC

sneak peek jitpack

Spring Boot Actuator readiness, liveness probes on k8s

About Websocket minimize data size and data transfer cost on cloud

About G1 GC

대학생 코딩 과제 대행 java, python, oracle 네 번째