HackerRank Java Sequence Equation
문제 풀기 : https://www.hackerrank.com/challenges/permutation-equation/problem
문제요약 : 첫 번째 줄에는 배열의 길이가 주어지고, 두 번째 라인에는 배열이 주어진다.
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))를 담아주고 리턴해주었다.
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:
- , so
- , so
- , so
- , so
- , 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 .
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 :
- , so we print the value of on a new line.
- , so we print the value of on a new line.
- , 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))를 담아주고 리턴해주었다.
댓글
댓글 쓰기