알고리즘 - 가장 긴 문자열 찾기

dongha1992·2020년 11월 5일
0

문제

내 풀이

으... 어렵다.. 문자열의 요소 중 중복이 없는 가장 긴 문자열인데 중복이 생기면 중복 앞부터 쭉 세면 된다. 로직을 이상하게 짜서 실패..

다른 사람 풀이

은정님 풀이

현지님 풀이



const isValid = (size, str) => { //중복아닌게 하나라도있으면 true
    let s = 0,
        e = size - 1;
    let mymap = new Map();
    for (let i = 0; i <= e; i++) {
        if (mymap.has(str[i])) {
            let cnt = mymap.get(str[i]);
            mymap.delete(str[i]);
            mymap.set(str[i], cnt + 1);
        } else mymap.set(str[i], 1);
    }
    if (mymap.size === size) return true;
    while (e < str.length - 1) {
        e++;
        let cnt = mymap.get(str[s]);
        if (cnt === 1) mymap.delete(str[s]);
        else {
            mymap.delete(str[s]);
            mymap.set(str[s], cnt - 1);
        }
        s++;
        if (mymap.has(str[e])) {
            let tmpcnt = mymap.get(str[e]);
            mymap.delete(str[e]);
            mymap.set(str[e], tmpcnt + 1);
        } else mymap.set(str[e], 1);
        if (mymap.size === size) return true;
    }
    return false;
}
const getLengthOfStr = str => {
    let s = 0,
        e = str.length,
        mid, answer = 0;
    while (s <= e) {
        mid = Math.floor((s + e) / 2);
        if (isValid(mid, str)) {
            s = mid + 1;
            answer = (answer < mid) ? mid : answer;
        } else e = mid - 1;
    }
    return answer;
}
profile
글과 코드와 사람에 관해 생각합니다.

0개의 댓글