[JS - 알고리즘] 01. 문자열 해싱

 

21.10.28 오타, 내용 수정

 

1. 문자열 해싱

01. 문자열 압축

• 처음 접근:
  • 해당 idx와 그 다음 idx 값이 같을 때, cnt의 개수를 for문으로 구해주고 answer에 str[i]와 String(cnt)를 붙여주는 방식으로 하려 했다. 하지만 계속 원치 않는 문자열이 추가가 됐다.
• 풀이 :
  • 어느 부분에서 오류가 발생하는지 생각하기 어려웠다. 그 이유는 입력받은 문자열에서 직접 몇 번째 idx에 접근하는지를 처리하려고 하니 어려웠던 것 같다. 대신 cnt만 세주고 문자가 달라질 때, 새로운 문자열에 넣는 방식으로 생각하니 for문에서 처리하는 로직이 간단해졌다. JS에서는 새로운 배열에 필요한 값만 넣는다고 생각하면 쉽다.
• 내 풀이

function solution(str) {
    let answer = '';

    for (let i = 0; i < str.length; i++) {
        let cnt = 1;
        if (str[i] === str[i + 1]) {
            for (let j = i + 1; j < str.length; j++) {
                if (str[i] === str[j]) cnt++;
            }
            console.log('cnt', cnt);
            if (cnt > 1) {
                answer += str[i];
                answer += cnt;
                i += cnt;
                cnt = 1;
            }
        } else answer += str[i];
    }
    return answer;
}

• 풀이

function solution(str) {
    let answer = '';
    str = str + ' ';
    let cnt = 1;
    for (let i = 0; i < str.length - 1; i++) {
        if (str[i] === str[i + 1]) {
            // 문자열이 앞 뒤가 같을 때 cnt++을 해준다.
            cnt++;
        } else {
            // str[i] 와 str[i + 1]이 달라질 때, 현재의 i번 idx까지 같은 Char
            answer += str[i];
            if (cnt > 1) answer += String(cnt);
            cnt = 1;
        }
    }
    return answer;
}

 

 

02. 숫자만 추출 (정규식, parseInt())

정규식을 만드는 두 가지 방법이 있다. 정규식 리터럴(슬래쉬 "/"로 감싸는 패턴)을 사용하는 방법은 다음과 같다.

let re = /ab+c/;
let re = new RegExp("ab+c");

02.1. 정규식

• \ : /a*/ 에서의 특수 문자 *는 0개 이상의 'a' 문자가 등장함을 나타냅니다. 이와는 다르게, 패턴 /a \*/ 는 *이 특별하지 않다는 것을 나타내며, 'a*'와 같은 문자열과 대응될 수 있습니다.
• ^ : 입력의 시작 부분에 대응. 만약 다중행 플래그가 참으로 설정되어 있다면, 줄 바꿈 문자 바로 다음 부분과도 대응됩니다. /^A/ 는 "an A" 의 'A'와는 대응되지 않습니다, 그러나 "An E" 의 'A'와는 대응된다. 그리고 [^abc] 패턴안에서의 ^ 는 부정셋을 의미한다.
• $ : /t$/ 는 "eater" 의 't'에는 대응되지 않습니다, 그러나 "eat" 과는 대응됩니다.
• * : 앞의 표현식이 0회 이상 연속으로 반복되는 부분과 대응됩니다. {0,} 와 같은 의미입니다.
• + : 앞의 표현식이 1회 이상 연속으로 반복되는 부분과 대응됩니다. {1,} 와 같은 의미입니다. 예를 들어, /a+/ 는 "candy"의 'a'에 대응되고 "caaaaaaandy" 의 모든 'a'들에 대응되지만, "cndy" 내의 어느 부분과도 대응되지 않습니다.
• ? : 앞의 표현식이 0 또는 1회 등장하는 부분과 대응됩니다. {0,1} 와 같은 의미입니다. 예를 들어, /e?le?/ 는 "angel"의 'el' 에 대응되고, "angle"의 'le' 에 대응되고 또한 "oslo" 의 'l'에도 대응됩니다.
• . : 개행 문자를 제외한 모든 단일 문자와 대응됩니다. 예를 들어, /.n/는 "nay, an apple is on the tree"에서 'an'과 'on'에 대응되지만, 'nay' 에는 대응되지 않습니다.
• [xyz] : 문자셋(Character set) 입니다. 이 패턴 타입은 괄호 안의 어떤 문자(이스케이프 시퀀스까지 포함)와도 대응됩니다. 점(.) 이나 별표 (*) 같은 특수 문자는 문자셋 내부에서는 특수 문자가 아닙니다. 따라서 이스케이프시킬 필요가 없습니다. 하이픈을 이용하여 문자의 범위를 지정해줄 수 있습니다.
• 예를 들어, 패턴 [a-d] 는 패턴 [abcd] 와 똑같이 동작하며, "brisket"의 'b' 에 일치하고, "city"의 'c' 에 일치합니다. 패턴 /[a-z.]+/와 /[\w.]+/ 는 "test.i.ng" 전체 문자열이 일치합니다.
• [^xyz] : 부정 문자셋(negated character set) 또는 보충 문자셋(complemented character set)입니다. 괄호 내부에 등장하지 않는 어떤 문자와도 대응됩니다. 하이픈을 이용하여 문자의 범위를 지정할 수 있습니다. 일반적인 문자셋에서 작동하는 모든 것은 여기에서도 작동합니다.
• 예를 들어, 패턴[^abc]는 패턴[^a-c]와 동일합니다. 두 패턴은 "brisket"의 'r', "chop."의 'h' 에 대응됩니다.
• [\b] : 백스페이스

• \b : 단어 경계, 단어 경계는 다른 '단어 문자'가 앞이나 뒤에 등장하지 않는 위치에 대응됩니다. 단어의 경계는 대응 결과에 포함되지 않는다는 사실에 주의하세요. 다른 말로는, 단어의 경계에 대응되는 문자열의 길이는 항상 0입니다. (패턴 [\b]와 혼동하지 마세요.)
• 이해하기가 좀 어려움.

02.2. 정규식에 쓰이는 메소드

• exec : 대응되는 문자열을 찾는 RegExp 메소드입니다. 정보를 가지고 있는 배열을 반환합니다. 대응되는 문자열을 찾지 못했다면 null을 반환합니다.
• test : 대응되는 문자열이 있는지 검사하는 RegExp 메소드 입니다. true 나 false를 반환합니다.
• match : 대응되는 문자열을 찾는 String 메소드입니다. 정보를 가지고 있는 배열을 반환합니다. 대응되는 문자열을 찾지 못했다면 null을 반환합니다.
• search : 대응되는 문자열이 있는지 검사하는 String 메소드 입니다. 대응된 부분의 인덱스를 반환합니다. 대응되는 문자열을 찾지 못했다면 -1을 반환합니다.
• replace : 대응되는 문자열을 찾아 다른 문자열로 치환하는 String 메소드입니다.
• split : 정규식 혹은 문자열로 대상 문자열을 나누어 배열로 반환하는 String 메소드입니다.

02.3. parseInt()

parseInt(string, radix);

인풋 값 string 이 "0"으로 시작한다면, radix 는 8(8진)이거나, 10(십진)입니다. 정확히 이 선택된 radix 는 구현 의존적적입니다. ECMAScript 5 는 10(십진)이 사용되는 것을 명시하지만, 모든 브라우저가 아직 이렇게 되지 않습니다. 이러한 이유로 항상 parseInt를 사용할 때는 radix 값을 명시해야 합니다.

• 처음 접근:
  • 정규식 사용 없이 숫자만 사용하기 위해서 if문에 a-z, A-Z 조건문을 일일이 쓰려 했다. 하지만 정규식을 공부하고 나니 굉장히 쉽게 처리할 수 있었다.
• 풀이

function solution(str) {
    let answer = '';
    for (let x of str) {
        if (!isNaN(x)) answer += x;
    }
    return pasrseInt(answer);
}

function solution2(str) {
    let answer = str.replace(/[^0-9]/g, ' ');
    return pasrseInt(answer);
}

 

 

03. 접미사 정렬

arr.sort([compareFunction])

• sort() : 정렬한 배열. 원 배열이 정렬되는 것에 유의하세요. 복사본이 만들어지는 것이 아닙니다. 파라미터 compareFunction이 생략되면 유니코드 순서에 따라서 오름차순으로 정렬된다. (참고)
• 문자열일 경우에만 정렬이 된다. 숫자일 경우에는 compareFunction을 추가해줘야 한다.

answer.sort((a, b) => a - b);

• 이 원리는 compare 함수의 형식을 살펴봐야 한다.
• compareFunction(a, b)이 0보다 작은 경우 a를 b보다 낮은 색인으로 정렬합니다. 즉, a가 먼저옵니다.
• compareFunction(a, b)이 0보다 큰 경우, b를 a보다 낮은 인덱스로 소트합니다.
• 즉, compare함수가 -1을 return시 a가 b보다 낮은 색인 인식. 1을 return 했을 때, a가 b보다 큰 색인으로 인식.

function compare(a, b) {
  if (a < b by some ordering criterion) {
    return -1;
  }
  if (a > b by the ordering criterion) {
    return 1;
  }
  // a must be equal to b
  return 0;
}

• 풀이

function solution(str) {
    let answer = [];
    for (let i = 0; i < str.length; i++) {
        answer.push(str.substring(i, str.length));
        answer.sort((a, b) => a - b);
    }
    return answer;
}
console.log(solution('kseaedu'));

 

 

04. 회문 문자열

• 내 풀이

function solution(str) {
    let left = 0,
        right = str.length - 1;
    str = str.toLowerCase();
    console.log(str);
    while (left < right) {
        if (str[left] === str[right]) {
            left++;
            right--;
        } else return 'NO';
    }
    return 'YES';
}
console.log(solution('gaaaooaaaG'));

• 풀이
• split(' ', 3) : 처음 3개의 문자열을 반환한다. 주어진 문자열을 separator마다 끊은 부분 문자열을 담은 Array.

let answer = 'YES';
str = str.toLowerCase();
if (str.split('').reverse().join('') != str) return 'NO';
return answer;

 

 

05. 특정 문자 뒤집기

• 풀이

function solution(str) {
    str = str.split('');
    const isAlpha = /[a-zA-Z]/;
    let left = 0,
        right = str.length - 1;
    while (left < right) {
        if (!isAlpha.test(str[left])) left++;
        if (!isAlpha.test(str[right])) right--;
        if (isAlpha.test(str[left]) && isAlpha.test(str[right]))         {
            let temp = str[left];
            str[left] = str[right];
            str[right] = temp;
            left++;
            right--;
        }
    }
    return str;
}
console.log(solution('a#b!GE*T@S'));

 

 

06. 회문 문자열2

str.substring(indexStart[, indexEnd])

• indexStart : 반환 문자열의 시작 인덱스
• indexEnd : 옵션. 반환 문자열의 마지막 인덱스 (포함하지 않음.)

내 코드에서 문제점은 while문을 빠져나가는 명령어가 필요했는데, "NO"인 경우에 대해 생각을 해주지 못했다. 따라서 left, right idx 변경도 없기 때문에 무한 루프에 빠져버렸다. 따라서 아래 풀이와 같이 substring한 문자열을 각각 비교해줘서 해결할 수 있었다.

• 풀이

function solution(str) {
    let answer = 'NO';
    let left = 0,
        right = str.length - 1;
    while (left < right) {
        if (str[left] === str[right]) {
            left++;
            right--;
        } else {
            let temp = str.substring(left, right);
            let temp2 = str.substring(left + 1, right + 1);
            if (
                temp === temp.split('').reverse().join('') ||
                temp2 === temp2.split('').reverse().join('')
            ) {
                return 'YES';
            } else return 'NO';
        }
    }
    return answer;
}

 

 

07. 공통 문자가 없는 단어

• indexOf : 배열에서 지정된 요소를 찾을 수 있는 첫 번째 인덱스를 반환하고 존재하지 않으면 -1을 반환합니다.

function solution(str) {
    let answer = 0;
    str.sort((a, b) => a.length - b.length);
    for (let i = 0; i < str.length - 1; i++) {
        for (let j = i + 1; j < str.length; j++) {
            if (isUniq(str[i], str[j])) {
                let temp = str[i].length * str[j].length;
                answer = Math.max(temp, answer);
            }
        }
    }
    function isUniq(short, long) {
        for (let x of short) {
            if (long.indexOf(x) > 0) return false;
        }
        return true;
    }
    return answer;
}
console.log(solution(['skudy', 'kstue', 'time', 'back', 'good']));

 

 

08. 학급 회장

• Set은 하나의 값만을 가지게 만드는 자료형.
• Map은 key-value를 가지는 자료형
• for ... of : String, Array iterable한 객체를 포함해서 loop를 돌 수 있다. (in은 )
• null check 관련글 https://helloworldjavascript.net/pages/160-null-undefined.html
• undefined와 ||연산을 했을 때 정리하기. (null, undefined)
• has(key) : key를 가지고 있는지 확인해주는 메소드.
• contacts.has('Jessie') // true : key값을 가지는지 확인하는 메소드.
• [...hash].sort((a,b) => b[1] -a[1]) : 이와 같이 hash안의 key와 value들을 정렬할 수 있다.

function solution(str) {
    let answer = '';
    let hash = new Map();
    for (let x of str) {
        console.log(hash.get(x));
        hash.set(x, (hash.get(x) || 0) + 1);
        //undefined가 나왔을 땐, 0으로 입력된다.
    }
    let max = Number.MIN_SAFE_INTEGER;
    for (let [key, val] of hash) {
        if (val > max) {
            max = val;
            answer = key;
        }
    }
    hash.get(max);
    return answer;
}
console.log(solution('BACBACCACCBDEDE'));

 

 

프로그래머스 문제 (숫자 문자열과 영단어)

• join('') 메서드는 배열의 모든 요소를 연결해 하나의 문자열로 만듭니다. 파라미터를 주지 않으면 기본값은 ,가 들어간다.
• 요소가 undefined 또는 null이면 빈 문자열로 변환합니다.

function solution(s) {
    let answer = 0;
    let arr = s;
    const numbers =['zero','one','two','three','four','five','six','seven','eight','nine','ten'];
    for (let i = 0; i < 11; i++){
        arr = arr.split(numbers[i]).join(i);
    }
    answer = parseInt(arr)
    return answer;
}

 

 

09. 아나그램(Anagram)

• Map 메소드 (Hash table)

const contacts = new Map()
contacts.set('Jessie', {phone: "213-555-1234", address: "123 N 1st Ave"})
contacts.has('Jessie') // true
contacts.get('Hilary') // undefined
contacts.set('Hilary', {phone: "617-555-4321", address: "321 S 2nd St"})
contacts.get('Jessie') // {phone: "213-555-1234", address: "123 N 1st Ave"}
contacts.delete('Raymond') // false
contacts.delete('Jessie') // true
console.log(contacts.size) // 1

/* for문에서의 이용 */
for (let [key, val] of hash) {
    console.log(hash.size);
    console.log(hash2.get(key));
    if (hash2.has(key)) {
        if (val === hash2.get(key)) {
            continue;
        } else {
            answer = 'NO';
            break;
        }
    }
}

• 내 풀이

function solution(str1, str2) {
    let answer = 'YES';
    let temp;
    let hash = new Map();
    let hash2 = new Map();

    for (let i = 0; i < str1.length; i++) {
        hash.set(str1[i], (hash.get(str1[i]) || 0) + 1);
    }
    for (let i = 0; i < str2.length; i++) {
        hash2.set(str2[i], (hash2.get(str2[i]) || 0) + 1);
    }

    for (let [key, val] of hash) {
        if (hash2.has(key)) {
            if (val === hash2.get(key)) {
                continue;
            } else {
                answer = 'NO';
                break;
            }
        }
    }
    return answer;
}
console.log(solution('abaCC', 'Caaab'));

09.1 Filter

function solution(arr) {
    return arr.filter((val) => {
        // 참 거짓을 return 해야한다.
        for (let i = 2; i * i <= val; i++) {
            if (val % i == 0) return false;
            else return true;
        }
    });
}

 

 

10. 문자열 구분하기

Array.prototype.slice()

slice() 메서드는 어떤 배열의 begin부터 end까지(end 미포함)에 대한 얕은 복사본을 새로운 배열 객체로 반환합니다. 원본 배열은 바뀌지 않습니다.

• begin Optional음수 인덱스는 배열의 끝에서부터의 길이를 나타냅니다. slice(-2) 는 배열에서 마지막 두 개의 엘리먼트를 추출합니다.begin이 배열의 길이보다 큰 경우에는, 빈 배열을 반환합니다.
• begin이 undefined인 경우에는, 0번 인덱스부터 slice 합니다.
• 0을 시작으로 하는 추출 시작점에 대한 인덱스를 의미합니다.
• end Optional예를 들어, slice(1,4)는 두번째 요소부터 네번째 요소까지 (1, 2 및 3을 인덱스로 하는 요소) 추출합니다.end가 생략되면 slice()는 배열의 끝까지(arr.length) 추출합니다.
• 만약 end 값이 배열의 길이보다 크다면, silce()는 배열의 끝까지(arr.length) 추출합니다.
• 음수 인덱스는 배열의 끝에서부터의 길이를 나타냅니다. 예를들어 slice(2,-1) 는 세번째부터 끝에서 두번째 요소까지 추출합니다.
• 추출을 종료 할 0 기준 인덱스입니다. slice 는 end 인덱스를 제외하고 추출합니다.

Array.prototype.splice()

splice() 메서드는 배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 추가하여 배열의 내용을 변경합니다.

array.splice(start[, deleteCount[, item1[, item2[, ...]]]])

• start
• 배열의 변경을 시작할 인덱스입니다. 배열의 길이보다 큰 값이라면 실제 시작 인덱스는 배열의 길이로 설정됩니다. 음수인 경우 배열의 끝에서부터 요소를 세어나갑니다(원점 -1, 즉 -n이면 요소 끝의 n번째 요소를 가리키며 array.length - n번째 인덱스와 같음). 값의 절대값이 배열의 길이 보다 큰 경우 0으로 설정됩니다.
• deleteCount OptionaldeleteCount를 생략하거나 값이 array.length - start보다 크면 start부터의 모든 요소를 제거합니다.
• deleteCount가 0 이하라면 어떤 요소도 제거하지 않습니다. 이 때는 최소한 하나의 새로운 요소를 지정해야 합니다.
• 배열에서 제거할 요소의 수입니다.
• item1, item2, *...* Optional반환 값
• 제거한 요소를 담은 배열. 하나의 요소만 제거한 경우 길이가 1인 배열을 반환합니다. 아무 값도 제거하지 않았으면 빈 배열을 반환합니다.
• 배열에 추가할 요소입니다. 아무 요소도 지정하지 않으면 splice()는 요소를 제거하기만 합니다.

 

• 내 풀이

function solution(s, m) {
    let answer;
    for (let i = m; i > 0; i--) {
        for (let j = 1; j < s.length; j++) {
            s[j - 1] = s[j] - s[j - 1];
        }
    }
    s = s.slice(0, s.length - m);
    console.log(s);

    return answer;
}

console.log(solution([5, 3, 7, 9, -2], 1));
console.log(solution([5, 3, 7, 9, -2], 2));

Set 자료형

var mySet = new Set();

mySet.add(1); // Set { 1 }
mySet.add(5); // Set { 1, 5 }
mySet.add(5); // Set { 1, 5 }
mySet.add('some text'); // Set { 1, 5, 'some text' }
var o = {a: 1, b: 2};
mySet.add(o);

mySet.add({a: 1, b: 2}); // o와 다른 객체를 참조하므로 괜찮음

mySet.has(1); // true
mySet.has(3); // false, 3은 set에 추가되지 않았음
mySet.has(5);              // true
mySet.has(Math.sqrt(25));  // true
mySet.has('Some Text'.toLowerCase()); // true
mySet.has(o); // true

mySet.size; // 5

mySet.delete(5); // set에서 5를 제거함
mySet.has(5);

mySet.size; // 4, 방금 값을 하나 제거했음
console.log(mySet);// Set {1, "some text", Object {a: 1, b: 2}, Object {a: 1, b: 2}}