나는 못풀었던, 어려운 알고리즘 문제중 하나. 기억에 남기에 남겨본다.
코드카타: 중복되지 않은 가장 긴 문자열
* 문제
String 형인 str 인자에서 중복되지 않은 알파벳으로 이루어진 제일 긴 단어의 길이를 반환해주세요.
str: 텍스트
return: 중복되지 않은 알파벳 길이 (숫자 반환)
예를 들어,
str = "abcabcabc"
return은 3
=> 'abc' 가 제일 길기 때문
str = "aaaaa"
return은 1
=> 'a' 가 제일 길기 때문
str = "sttrg"
return은 3
=> 'trg' 가 제일 길기 때문많은 생각을 요했던 알고리즘 문제 였던 것 같다. 한가지 테스트는 끝까지 통과하지 못했다.
나의 풀이
- 빈 객체(newArry)를 생성한다.
- 중복되지 않은 문자들의 길이를 저장할 객체(newLength)를 생성한다.
- 주어진 스트링의 첫 문자를 빈 객체에 넣는다.
- 다음 문자가 newArry에 포함되는지 확인. 포함되지 않는다면 해당 문자를 newArry에 넣는다. 포함된다면, 중복이므로 newArry의 길이를 newLength에 저장. 그후, newArry를 빈 객체로 초기화 시킨다.
- 4번을 반복하면서 주어진 스트링의 문자를 전부 검사한다.
- newLength에서 max 값을 찾아 리턴한다.
위의 로직을 코드로 풀면 아래와 같다.
const getLengthOfStr = str => {
let toArry = str.split("");
let newArry = [];
let newLength = [];
if (toArry.length !== 0) {
// 최초 값 대입
newArry.push(toArry[0]);
newLength.push(1);
//중복 문자 체크
for (let i = 1; i < toArry.length; i++) {
if ((i === (toArry.length-1)) && (!newArry.includes(toArry[i]))) {
newArry.push(toArry[i]);
newLength.push(newArry.length);
} else if (newArry.includes(toArry[i])) {
newLength.push(newArry.length);
newArry = [];
newArry.push(toArry[i]);
} else if (!newArry.includes(toArry[i])) {
newArry.push(toArry[i]);
}
}
const max = Math.max(...newLength);
return max;
} else {
return 0;
}
}나의 풀이 문제점
나의 풀이는 abcabcd와 같은 단순한(?) 문자열에서는 문제없이 작동한다. 하지만, abcdefcighzh 와 같은 문자에서는 작동하지 않는다. 왜냐하면, 두번째 c에서 중복을 확인한 후, 다음 문자인 i에 대해서 중복문자 체크를 하기 때문. i가 아닌 앞쪽의 d로 이동하여 중복문자 체크를 재시작 하여야 한다. 내 풀이는 중복문자를 찾았을 때, 첫번째 문자로 이동하여 그 다음 문자부터 다시 체크를 시작하도록 하는 장치가 없었다.
모범 풀이
function getLengthOfStr(s) {
let strArr = [];
let prevStrArr = [];
for (let i = 0; i < s.length; i++) {
let ss = s.slice(i, i+1);
for (let j = 0; j < strArr.length; j++) {
if (ss === strArr[j]) {
if (prevStrArr.length < strArr.length) {
prevStrArr = strArr.slice();
}
strArr = strArr.splice(j+1, strArr.length);
break;
}
}
strArr.push(ss);
}
return Math.max(strArr.length, prevStrArr.length);
}모범 풀이의 접근은 아래와 같다.
- 체크하는 문자열이 저장될 배열(strArr)와 중복된 문자열을 찾았을 경우 그 전까지의 문자열을 기록할 배열(preStrArr)를 생성한다.
- 주어진 문자열의 문자를 하나씩 돌면서 체크를 한다. 중복 되지 않은 문자열의 경우 strArr에 저장한다.
- 중복되는 문자를 찾을 경우, 그 문자 전까지를 preStrArr에 저장한 후, 현재까지 체크된 문자열인 strArr에서 첫번째 문자 부터 중복문자의 앞쪽 문자까지를 잘라낸다.
- 이후 다음 문자부터 다시 2~3번을 반복한다.
- 이후에 또 다시 중복되는 문자를 발견했을 경우, 그 때까지의 문자열의 길이와 그 전에 발견된 중복되지 않은 문자열(preStrArr에 담겨있는)의 길이를 비교한다. 비교했을 때, 새로 발견된 문자열이 더 길 경우 preStrArr를 교체하고, 그렇지 않으면 교체하지 않는다.
- 5번까지의 프로세스를 반복 했을 경우, preStrArr에는 찾아낸 중복되지 않은 문자열 중 가장 긴 것이 저장되어 있을 것이고, strArr에는 나머지 문자(당연히 중복되지 않은)들이 담겨 있을 것이다. 마지막으로 그 둘을 비교하여, 더 긴 것을 리턴한다.
세상은 넓고 뛰어난 알고리즘 풀이는 어디나 존재한다. ^-^
