[코딩테스트] 프로그래머스 javascript 2단계 - 튜플,압축

튜플

https://school.programmers.co.kr/learn/courses/30/lessons/64065

프로그래머스

문제 설명

셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

• (a1, a2, a3, ..., an)

튜플은 다음과 같은 성질을 가지고 있습니다.

1. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)
2. 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)
3. 튜플의 원소 개수는 유한합니다.

원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.

• {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

와 같이 표현할 수 있습니다. 이때, 집합은 원소의 순서가 바뀌어도 상관없으므로

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
• {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}
• {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

는 모두 같은 튜플 (2, 1, 3, 4)를 나타냅니다.

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

문제풀이

- 1.튜플의 규칙 즉, 집합의 크기가 작은 것 부터 확인해서 튜플에 넣으면 된다.

- 2. 문자열에서 '{'를 없애고 ,로 나눠준다.

- 3. 전부 다 하나의 배열에 저장하고 이를 길이가 짧은 순서대로 확인해서 배열로 저장한다.

 

- 하루 전에는 못풀고 넘겼는데 오늘 풀어냈다~!!!

function solution(s) {
    var answer = [];
    let arr = s.split('}').filter(v=>v!=='')
    for (let i = 0; i<arr.length;i++){
        const cur = arr[i].replaceAll(/[{}]/g,'')
                .split(',').filter(v=>v!=='')
        answer.push(cur)
    }
    answer.sort((a,b)=>a.length-b.length)
    console.log(answer)
    let result = [];
    answer.forEach((v,j)=>{
        const tmp = v
        for(let i=0;i<tmp.length;i++) {
            if(!result.includes(tmp[i])) result.push(tmp[i]);
        }
    })
    return result.map(Number)
}

 

 

압축

https://school.programmers.co.kr/learn/courses/30/lessons/17684

프로그래머스

문제설명

신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다.

어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년 발표된 알고리즘으로, 이미지 파일 포맷인 GIF 등 다양한 응용에서 사용되었다.

LZW 압축은 다음 과정을 거친다.

1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
5. 단계 2로 돌아간다.

압축 알고리즘이 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다. 사전의 색인 번호는 정수값으로 주어지며, 1부터 시작한다고 하자.

 

문제풀이

 

- 틀린 코드 

: 테스트 1만 맞는 정확성 15점수 받은 코드이다.

Map에 word를 저장하고 word.has 메서드를 사용해서 str 존재 여부를 확인한다.

그러나 word의 개수가 늘어나면서 작동이 제대로 되고 있지 않다.

 

 

function solution(msg) {
    let word = new Map()
    let answer = []
    for(let i ="A".charCodeAt();i<="Z".charCodeAt();i++){
        word.set(String.fromCharCode(i), i-65+1)
    }
    
    for(let i=0;i<msg.length;i++){
        if (i===msg.length-1 ) {
             answer.push(word.get(msg[i]))}
        
        if(i!==msg.length-1){
            let str = msg[i]+msg[i+1]
            if (word.has(str)){
                i++;
                for(let j=i+2;j<msg.length-1;j++){
                   if(word.has(str+msg[j])){
                       i++; str += msg[j]
                   } 
                   else{
                        word.set(str,word.size+1)
                        break;
                    }
                }
                answer.push(word.get(str));
                     
                
            }
            else{
                word.set(str,word.size+1)
                answer.push(word.get(msg[i]))
            } 
        }
    }
    return answer
}

 

- 1. 먼저 알파벳 map을 생성해주자

let word = new Map()
    for(let i ="A".charCodeAt();i<="Z".charCodeAt();i++){
        word.set(String.fromCharCode(i), i-65+1)
    }

"A".charCodeAt()으로 알파벳의 아스키코드를 얻고,

String.fromCharCode(65)로 문자열을 얻을 수 있다. 

 

- 2. msg길이만큼 for문을 돌리고 while문으로 w의 길이를 증가한다.

while문을 반복하지 않아 위에 코드가 정상 작동되지 않았던 것 같다.

- 3. w를 최대로 늘린 후에 result에 저장하고, w+c를 word에 저장한다.

 

function solution(msg) {
    let word = new Map()
    for(let i ="A".charCodeAt();i<="Z".charCodeAt();i++){
        word.set(String.fromCharCode(i), i-65+1)
    }
    
    let  result = [];
    
    for (var i = 0; i < msg.length; i++) {

        let  w = msg[i];
        let c = msg[i+1];
        while (word.has(w+c) && i < msg.length - 1) {
            i++;
            w = w+c;
            c = msg[i+1];
        }

        result.push(word.get(w));

        word.set(w+c,word.size+1);
    }

    return result;

}

 

 

조건을 확인할 때는 while 문을 애용하자