Tasks
작은 개구리는 강 건너편에 가고 싶어합니다. 개구리는 처음에 강의 한 강둑(위치 0)에 있으며 반대편 강둑(위치 X+1)에 도달하려고 합니다. 나뭇잎이 나무에서 강 표면으로 떨어집니다.
낙엽을 나타내는 N개의 정수로 구성된 배열 A가 주어집니다. A[K]는 초 단위로 측정된 시간 K에서 하나의 잎이 떨어지는 위치를 나타냅니다.
목표는 개구리가 강 건너편으로 점프할 수 있는 가장 빠른 시간을 찾는 것입니다. 개구리는 1에서 X까지 강 건너 모든 위치에 잎이 나타날 때만 건너갈 수 있습니다(즉, 1에서 X까지 모든 위치가 잎으로 덮이는 가장 빠른 순간을 찾고 싶습니다). 강의 흐름 속도는 무시할 정도로 작다고 가정할 수 있습니다. 즉, 나뭇잎이 강에 떨어지면 위치가 바뀌지 않습니다.
예를 들어 다음과 같은 정수 X = 5와 배열 A가 주어집니다.
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
두 번째 6에서 리프는 위치 5로 떨어집니다. 이것은 리프가 강 건너 모든 위치에 나타나는 가장 빠른 시간입니다.
함수 작성:
함수 솔루션(X, A);
N개의 정수와 정수 X로 구성된 비어 있지 않은 배열 A가 주어지면 개구리가 강 건너편으로 점프할 수 있는 가장 빠른 시간을 반환합니다.
개구리가 강 건너편으로 절대 점프할 수 없다면 함수는 -1을 반환해야 합니다.
예를 들어 X = 5이고 배열 A가 다음과 같이 주어진 경우:
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
함수는 위에서 설명한 대로 6을 반환해야 합니다.
다음 가정에 대한 효율적인 알고리즘을 작성하십시오 .
N 및 X는 범위 [ 1 .. 100,000 ] 내의 정수이고;
배열 A의 각 요소는 [ 1 .. X ] 범위 내의 정수입니다 .
팁!
set은 length가 아닌 size로 set의 길이를 판별
팁2
set을 정렬할 땐 배열로 바꿔서 정렬 후 다시 넣던
아니면 sorting한 배열로 이루어진 set을 다시 만들면 된다.
내 풀이
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(X, A) {
let ans = new Set()
let res = 0;
A.map( (v, i) => {
if (A[i] <= X && !(ans.has(A[i])) ) {
ans.add(A[i])
res = i
}
})
return res ? res : -1
}위에처럼 풀었는데 에러가 발생했다. 아무래도 에러처리를 잘못 해준 모양이다
이것을 처리하기 위해서 map을 for문으로 고쳤다 (바로 i값을 return 해주기 위해)
81%
고친 풀이
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(X, A) {
let ans = new Set()
for (i=0; i<A.length; i++) {
ans.add(A[i])
if (ans.size === X) {
return i
}
}
return -1
}
더욱 간단ㄷ하고 쉽게 풀었떤 것 같다.
어차피 X보다 작은수로 값이 주어지니 조건문을 없앴고
그냥 돌면서 하나하나 넣어주다가 set의 사이즈가 X와 같다면 그떄에 i값을 return 해준다.
이렇게 된다면 A의 길이가 1이더라도, 처리할 수 있고
for문에 속하지 않으면 자연스럽게 -1을 리턴해준다.
