알고리즘 50번 - 가장 가까운 같은 글자
URL : https://school.programmers.co.kr/learn/courses/30/lessons/142086
JS
문제
문제 설명
문자열 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 추가.
새 배열을 반환하기
참고, 풀이
findLastIndex() 사용법
const index = numbers.findLastIndex(num => num % 2 === 0);function solution(s) {
let arrS = [...s];
let arrAnswer = [];
let arrTemp = [];
arrS.forEach((v) => {
arrAnswer.push(arrTemp.findLastIndex((li) => li === v));
arrTemp.push(v);
});
console.log(arrTemp);
return arrAnswer;
}
//const index = numbers.findLastIndex(num => num % 2 === 0);
/**
* 입출력 예
s result
"banana" [-1, -1, -1, 2, 2, 2]
"foobar" [-1, -1, 1, -1, -1, -1]
*/
const b = "banana";
const f = "foobar";
console.log(solution(b)); // 오답 [ -1, -1, -1, 1, 2, 3 ]
console.log(solution(f));마지막 인덱스와 직전에 등장한 동일 문자 위치의 차를 arrAnswer에 추가해야 합니다.
function solution(s) {
let arrS = [...s];
let arrAnswer = [];
let arrTemp = [];
arrS.forEach((v, i) => {
// 현재 문자가 arrTemp에서 마지막으로 등장한 위치 찾기
let lastIndex = arrTemp.findLastIndex((char) => char === v);
arrAnswer.push(lastIndex === -1 ? -1 : i - lastIndex); // 인덱스 차이 계산
arrTemp.push(v); // arrTemp에 현재 문자 추가
});
console.log(arrTemp);
return arrAnswer;
}
TypeError: arrTemp.findLastIndex is not a function
최신버전이 아니라 사용 할 수 없는 것 같습니다.
답
function solution(s) {
let arrAnswer = [];
let lastIndexMap = {}; // 문자의 마지막 등장 위치를 저장
[...s].forEach((char, idx) => {
if (lastIndexMap[char] !== undefined) {
arrAnswer.push(idx - lastIndexMap[char]); // 현재 인덱스 - 마지막 등장 인덱스
} else {
arrAnswer.push(-1); // 처음 등장하는 경우
}
lastIndexMap[char] = idx; // 마지막 등장 위치 갱신
});
console.log(lastIndexMap);
return arrAnswer;
}코드 간략화하기
function solution(s) {
let lastIndexMap = {}; // 문자의 마지막 등장 위치 저장
return [...s].map((char, idx) => {
let distance = lastIndexMap[char] !== undefined ? idx - lastIndexMap[char] : -1;
lastIndexMap[char] = idx; // 마지막 등장 위치 갱신
return distance;
});
}다른사람 답
function solution(s) {
const map = new Map();
return [...s].map((char, i) => {
const result = map.has(char) ? i - map.get(char) : -1;
map.set(char, i);
return result;
});
}코드 설명
map 객체를 사용:
각 문자의 마지막 인덱스를 저장합니다.
키는 문자, 값은 해당 문자가 마지막으로 등장한 위치입니다.
map 메서드와 인덱스 계산:
문자열 s를 배열로 변환하고, map()을 사용해 각 문자를 처리합니다.
문자가 map에 존재하면 현재 인덱스와 저장된 인덱스의 차이를 계산합니다.
문자가 처음 등장하는 경우 -1을 반환합니다.
결과 업데이트:
현재 문자의 인덱스를 map에 저장해 다음에 동일 문자가 등장할 때 참조합니다.
const solution = (s) =>
[...s].map((char, i) => {
const count = s.slice(0, i).lastIndexOf(char);
return count < 0 ? count : i - count;
});
- 주요 동작: 문자열에서 각 문자에 대해 이전 등장 위치와의 차이를 계산.
- 코드의 특징: 간결하지만 긴 문자열에서는 성능 저하 가능 (O(n²)).
1. const solution = (s) => { ... }
- 문자열 s를 입력으로 받아 처리하는 함수.
- 화살표 함수와 map을 활용해 간결하게 구현.
2. [...s].map((char, i) => { ... })
- 문자열 s를 배열로 변환:
- 예: s = "hello" → [...s] = ['h', 'e', 'l', 'l', 'o'].
- map을 사용해 배열의 각 문자(char)와 인덱스(i)를 순회하며 결과 계산.
3. const count = s.slice(0, i).lastIndexOf(char);
- 문자 char가 현재 인덱스 i 이전에 마지막으로 등장한 위치를 계산:
- s.slice(0, i): 문자열의 0부터 i-1까지 자름.
- 예: s = "abca", i = 3 → s.slice(0, 3) = "abc".
- .lastIndexOf(char): 잘라낸 부분 문자열에서 문자 char가 마지막으로 등장한 위치를 반환.
- char가 없으면 -1 반환.
- 예: "abc".lastIndexOf('a') = 0, "abc".lastIndexOf('d') = -1.
- s.slice(0, i): 문자열의 0부터 i-1까지 자름.
4. return count < 0 ? count : i - count;
- count < 0: 이전에 문자가 등장하지 않았으면 -1 반환.
- 그렇지 않으면 i - count를 계산하여 반환.
- 예:
- count = -1 → return -1.
- count = 0 (문자가 이전에 등장) → return i - count.
- 예: