문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.
예를 들어, s="banana"라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.
- b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
- a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
- n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
- a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
- n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다.
- a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.
따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.
문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.
제한사항
- 1 ≤ s의 길이 ≤ 10,000
- s은 영어 소문자로만 이루어져 있습니다.
입출력 예
| s | result |
|---|---|
| "banana" | [-1, -1, -1, 2, 2, 2] |
| "foobar" | [-1, -1, 1, -1, -1, -1] |
입출력 예 설명
입출력 예 #1
지문과 같습니다.
입출력 예 #2
설명 생략
나의 풀이
function solution(s) {
let arr = [];
for(let i = 0; i < s.length; i++){
if(s.slice(0,i).includes(s[i])){
arr.push(i - s.slice(0,i).lastIndexOf(s[i]));
}
else{
arr.push(-1);
}
}
return arr;
}나는 한 글자씩 그 글자의 앞부분만 잘라서 검사해 주었다. 앞부분에 찾는 문자열이 있다면 현재 인덱스에서 잘린 앞부분 문자열의 마지막 인덱스를 뺀 값을 배열에 넣어주었고, 없다면 -1을 넣어 주었다.
참고할 풀이
function solution(s) {
const hash={};
return [...s].map((v,i)=>{
let result = hash[v] !== undefined ? i - hash[v] : -1;
hash[v] = i;
return result;
});
}해시 테이블을 사용하면 더 쉽게 구할 수 있었다. 이 풀이는 해시 테이블을 만든 뒤, 해시 테이블에서 값을 검색했을 때 있으면 i-hash[v] 값을, 없다면 -1을 result 변수에 넣어주었다. 그리고 각 문자열은 나올 때 마다 문자열 키값에 인덱스 값을 넣어 준다. 이렇게 하면 결국 중복으로 나오는 문자열이 있다면 현재 인덱스에서 중복 문자열의 인덱스를 뺀 값을 리턴할 수 있다.
hash는 map처럼 key와 value를 저장한다는 것은 같지만, map이 조금 더 고급 방법을 지원한다. 중요한 차이점은 다음과 같다.
-
키: 맵의 키는 모든 값(개체 및 함수 포함)이 될 수 있는 반면 해시의 키는 문자열 또는 기호만 될 수 있다.
-
순서: Map의 요소는 삽입된 순서를 유지하지만 Hash의 요소는 그렇지 않다.
-
반복: for...of 루프를 사용하여 맵의 키와 값을 반복할 수 있는 반면 for...in 루프는 해시의 키를 반복하는 데만 사용할 수 있다.
-
크기: map에는 크기 속성이 있지만 해시에는 그러한 속성이 없다.
-
빌트인 메서드 : 맵에는 데이터를 조작하기 위한 set(), get(), has(), clear(), delete() 등과 같은 더 많은 기본 제공 방법이 있지만 Hash에는 이러한 방법이 없다.
그래서 사실상 hash를 굳이 사용하기보다는 map을 사용하면 될 듯 하다.
