프로그래머스#17684. [3차]_압축: 구현 / lv2

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/17684

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

[유형] : 구현

문제에서 주어진 LZW(Lempel–Ziv–Welch) 압축을 구현하는 문제이다.

1. 단어 길이 =1 로 사전 초기화 

idx = 정수값 : 단어
2.사전에서 현재 입력과 일치하는 가장 긴 문자열 찾기 w

3. w 에 해당하는 사전 idx 번호 출력하고 , 입력에서 w 을 제거
4. 입력에서 처리되지 않은 다음 글자 (c)가 남았으면 , w+c 에 해당하는 단어를 사전에 등록

2. 로 돌아간다.

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

1 . 길이 1 인 사전 초기화를 위해,

• dict 형식의 변수 , dict 을 정의한다
• ASCII 을 적용하여 A - Z 까지 값과 인덱스 값을 key : value 로 추가함

1. 탐색할 입력 단어의 범위를 포인터 w_s 와 변수 w_l 로 초기화한다.

   • w_s = 0 : 입력 단어 중 탐색을 위한 일부 단어 시작 위치
   • w_l = 1 : 입력 단어 중 현재 탐색하는 글자 개수

2. 입력 단어 전체를 반복문을 사용해 탐색하기 (w_s + w_l ≤ len(입력단어)

   1. 탐색 단어(word[w_s : w_s + w_l] 가 사전에 존재하면

      → 최대 길이 w 단어 인덱스(prev_idx)을 사전 속 인덱스 값으로 업데이트

      → continue

   2. 사전에 존재하지 않으면

      1. w+c 까지 단어 사전 등재하기
      2. 탐색 포인트 w_s와 w_l 을 다음 글자로 업데이트
      3. 출력 리스트 answer 에 바로 직전 사전 인덱스 값 pre_idx을 추가하기

3. 마지막 사전 인덱스 출력 리스트 answer 추가하기(예외처리)

🚩제출한 코드