🔎 문제
🧩 구현과정 및 코드
개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.
사용할 데이터 구조와 풀이 방향성
적용할 알고리즘 혹은 메서드
수영
구현
- LZW 압축 과정 순서대로 코딩
- 사전 초기화(dictionary 객체)
- 입력값(msg)와 일치하는 word 찾기
- 입력값(msg)와 일치하지 않는다면 사전 추가 필요⭐
- 추가 전, slice(0~word.length -1)까지 색인 번호 출력(answer)
- 사전 추가, word 초기화
- 마지막 글자 색인 번호 출력(answer)
코드
- for문으로 wordIndex 관리 하니 코드가 지저분해지고 if문 많아져서 다시..
- 풀이 참고, while문으로 풀이
function solution (msg) { const answer = []; const dictionary = {}; let indexNumber = 1; for(let i = 65; i < 65+26; i++) { dictionary[String.fromCharCode(i)] = indexNumber++; } const message = msg.split(''); let wordIndex = 0; let word = ''; while(message.length !== wordIndex){ word = word.concat(message[wordIndex]); if(dictionary[word]){ wordIndex++; } else{ answer.push(dictionary[word.slice(0,word.length - 1)]) dictionary[word] = indexNumber++; word = ''; } if(message.length === wordIndex){ answer.push(dictionary[word]); } } return answer; }
정은
구현
- 사전 초기화
- msg를 도는데, 사전에 없는 문자열을 찾을 때가지 인덱스+1
- 없다면 현재 문자열을 사전에 저장 & 현재 인덱스 직전까지 출력 & 현재 문자열 초기화
- msg 다 돌 때 까지 2,3 반복
- 마지막 문자열은 저장하지 못한채로 while문이 끝나므로 마지막에 추가해줌
코드
- 처음 푼 코드
def solution(msg): dictonary={} answer = [] #사전 초기화 for idx,alpha in enumerate('ABCDEFGHIJKLMNOPQRSTUVWXYZ'): dictonary[alpha]=idx+1 i=0 #현재 index w="" #현재 문자열 while i<len(msg): w+=msg[i] if not w in dictonary: #사전에 없다면, 추가할 수 있다. dictonary[w]=len(dictonary)+1 #사전에 추가 answer.append(dictonary[w[:-1]]) #w에서 현재 문자를 뺀 것 까지가 사전에 있는 가장 긴 문자열 i-=1 #다음 턴은 현재 문자에서 시작해야함, 밑에서 i+1을 해주므로 미리 빼줌 w="" #현재 문자열 초기화 i+=1 answer.append(dictonary[w]) #마지막 w 추가 return answer
실행 했을 때 결과값에 마지막이 다 빠져있는 채로 실패 하길래,
answer.append(dictonary[w]) 를 추가를 해줬더니 통과됐다.하지만 이건 때려 맞춘거지 규칙을 명확하게 인지한 것은 아니다.
후에 이유를 생각해보고 정리했다.
1)마지막 w가 사전에 있다면: 그냥 저장 안되고 while문이 종료 2)없다면: i-1까지 출력하고, 마지막 턴에서 w=알파벳 한 글자이므로 저장되지 않은 채로 종료 그래서 마지막 w는 무조건 저장해줘야 한다.
- 다른 풀이 참고 후 코드
종혁
구현
- A-Z까지의 알파벳 한글자를
dictionary객체에 초기화한다
start에는 조사할 index를 ,prev에는 전에 조사한 글자를 담아둔다
- prev + msg[start] 단어가 사전에 존재할 경우에는
prev += msg[start++]을 통해 다음 글자를 조사 - 존재하지 않을 경우에는 기존의
prev에 있던 단어의 색인 번호를 result에 push,prev+msg[start]단어는dictionary에 추가한다
- while문이 종료되고
prev에 남아있는 단어의 색인번호를 마지막으로result에 push
코드
function solution(msg) { const dictionary = {} const result = [] let index = 0 for(index;index<=26;index++){ dictionary[String.fromCharCode(64+index)] = index} let start = 0 let prev = '' while(start<msg.length){ if(prev + msg[start] in dictionary){ prev += msg[start++] }else{ result.push(dictionary[prev]) dictionary[prev+msg[start]] = index++ prev = '' } } result.push(dictionary[prev]) return result }
재웅
구현
- 주어진 문자열을 순차적으로 탐색, 본인과 본인 다음 값까지 포함한 단어를 사전에 있는지 확인
- 본인 다음값이 존재하지 않을 경우 → 사전에 추가, 그 때의 인덱스를 answer에 추가
- 본인 다음값이 존재할 경우 → 그 다음 요소도 추가하여 사전과 비교, (2)를 만족할 때까지 반복
- answer 반환
코드
function solution(msg) { const answer = [] // 알파벳 배열 초기화 const dic = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'.split('') const map = new Map() // 알파벳 Map구조화 dic.forEach((el,idx)=>{ map.set(el,idx+1) }) let currentInput = "" const str = msg.split('') // 입력 문자열 순회 str.forEach((el,idx)=>{ const next = str[idx+1] currentInput+=el if(!map.has(currentInput+next)){ map.set(currentInput+next,map.size+1) answer.push(map.get(currentInput)) currentInput="" } }) return answer }
✏️ 후기
문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.
수영
- for문 말고, while문
- 긴 문제는 아직 어렵다!
정은
- 처음에 문제 해석하는데 시간이 좀 걸려서 세번 정도 코드를 갈아 엎었다.
규칙을 여러번 읽고, 마지막에 예시로 규칙을 찾고 나서야 완벽히 이해가 됐다.
문제를 많이 풀어서 긴 문제에 익숙해져야겠다!
- 소요시간 : 56분
종혁
- slice를 통해서 구현하는 것이 가장 간단하긴 하지만, 시간을 조금 줄여보고자 사용을 안해봄
재웅
- 이전에 풀어봤던 문제라, 복기하듯 다시 풀어보았습니다.
- 구현이 메인이고, 이를 효율적으로 풀기 위해 해시를 부가적으로 사용한다는 느낌을 받았습니다.