오늘의 알고리즘 👍

📝 1. 괄호 회전하기

• 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

  • (), [], {} 는 모두 올바른 괄호 문자열입니다.
  • 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
  • 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

• 대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다.

• 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

▷ 입출력 예

solution("[](){}") // 3
solution("}]()[{") // 2
solution("[)(]") // 0
solution("}}}") // 0

▷ 해결 못함 ❌

• 시간 부족으로 해결하지 못했다.

▷ 수업 풀이

const numbering = {
  "[": 0,
  "]": 1,
  "{": 2,
  "}": 3,
  "(": 4,
  ")": 5,
};

function solution(s) {
  let answer = 0;

  for (let i = 0; i < s.length; i++) {
    const stack = [];
    s = s.slice(1) + s[0];
    for (let j = 0; j < s.length; j++) {
      // 열린 괄호인지, 닫힌 괄호인지 판단(열림:짝수,닫힘:홀수)
      if (numbering[s[j]] % 2 === 0) {
        // 열린 괄호만 찾아온다.
        stack.push(numbering[s[j]]);
        // 숫자로 넣는다.
      } else {
        // 닫힌 괄호라면, stack에 그 짝이 있는지 체크
        if (stack.includes(numbering[s[j]] - 1)) {
          const last = stack[stack.length - 1];
          if (last === numbering[s[j]] - 1) {
            stack.splice(stack.length - 1, 1);
          }
        } else {
          break;
        }
      }
      if (j === s.length - 1) {
        if (stack.length === 0) {
          answer++;
        }
      }
    }
  }
  return answer;
}

📝 2. 압축

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

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

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

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

▷ 입출력 예

solution("KAKAO") // [11, 1, 27, 15]
solution("TOBEORNOTTOBEORTOBEORNOT") // [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34]
solution("ABABABABABABABAB") // [1, 2, 27, 29, 28, 31, 30]

▷ 해결 못함 ❌

• 시간 부족으로 해결하지 못했다.

▷ 수업 풀이

function solution(msg) {
    // 글자들의 색인번호를 지정하기 위한 객체
    const dictionary = {};
    let index = 1;
    for(let i = 65; i <= 90; i++) {
        dictionary[String.fromCharCode(i)] = index;
        index++;
    }
    
    const answer = [];
    
    // 여러개의 글자를 담기 위한 변수
    let str = '';
    
    for(let i = 0; i < msg.length; i++) {
        str += msg[i];
        const next = str + msg[i + 1];
        
        if(!dictionary[next]) {
            // 만약 바로 뒤의 한 글자까지 포함한 색인번호가 없다면,
            if(msg[i + 1]) {
                dictionary[next] = index;
            }
            index++;
            
            answer.push(dictionary[str]);
            str = '';
        }
    }
    return answer
}

마무리 👍

• 알고리즘을 강제되는 시간은 없겠지만 알고리즘을 꾸준히 푸는 것이 중요하다.
• 알고리즘 마지막 시간 끝

출처: 프로그래머스
출처: 코드캠프