[20211116]알고리즘 풀이

모든 아나그램 찾기(해쉬, 투포인터, 슬라이딩 윈도우)
 S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하 세요. 아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.
▣ 입력설명
첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다. S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다.
▣ 출력설명
S단어에 T문자열과 아나그램이 되는 부분문자열의 개수를 출력합니다.
▣ 입력예제 1
bacaAacba abc
▣ 출력예제 1
3
출력설명: {bac}, {acb}, {cba} 3개의 부분문자열이 "abc"문자열과 아나그램입니다.

function compareMaps(map1, map2){
    if (map1.size !== map2.size) return false
    for (let [key, value] of map1) {
        if (!map2.has(key) || map2.get(key) !== value) return false
    }
    return true
}
function solution(s, t){
    let map1 = new Map()
    let map2 = new Map()
    let lt = answer = 0;
    for (let item of t) {
        if (map2.has(item)) map2.set(item, map2.get(item) + 1)
        else map2.set(item, 1)
    }
    for (let i = 0; i < 2; i++) {
        if (map1.has(s[i])) map1.set(s[i], map1.get(s[i]) + 1)
        else map1.set(s[i], 1)
    }
    for (let i = 2; i < s.length; i++) {
        if (map1.has(s[i])) map1.set(s[i], map1.get(s[i]) + 1)
        else map1.set(s[i], 1)
        if (compareMaps(map1, map2)) answer++
        map1.set(s[lt], map1.get(s[lt]) - 1)
        if (!map1.get(s[lt])) map1.delete(s[lt])
        lt++
    }
    return answer;
}

let a="bacaAacba";
let b="abc";
console.log(solution(a, b));

올바른 괄호
 괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다. (())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.
▣ 입력설명
첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다.
▣ 출력설명
첫 번째 줄에 YES, NO를 출력한다.
▣ 입력예제 1
(()(()))(()
▣ 출력예제 1
NO

function solution(s){
    let answer="YES";
    let arr = []
    for (let item of s) {
        if (item === '(') arr.push('(')
        else {
            if (arr.length === 0) answer = "NO"
            else arr.pop()
        }
    }
    if (arr.length > 0) answer = "NO"
    return answer;
}

let a="(()(()))(()";
console.log(solution(a));

 

괄호문자제거
입력된 문자열에서 소괄호 ( ) 사이에 존재하는 모든 문자를 제거하고 남은 문자만 출력하는 프로그램을 작성하세요.
▣ 입력설명
첫 줄에 문자열이 주어진다. 문자열의 길이는 100을 넘지 않는다.
▣ 출력설명
남은 문자만 출력한다.
▣ 입력예제 1
(A(BC)D)EF(G(H)(IJ)K)LM(N)
▣ 출력예제 1
EFLM

function solution(s){
    let answer="";
    let arr = [];
    for (let item of s) {
        if (item === '(') arr.push(item)
        else if (item === ')') {
            arr.pop()
        }
        if ( item !== '(' && item !== ')' && arr.length === 0) answer += item
    }
    return answer;
}

let str="(A(BC)D)EF(G(H)(IJ)K)LM(N)";
console.log(solution(str));