오픈 채팅방 안 C++ 풀이 및 정답 코드
카카오뱅크는 세상에 존재하지 않았던 은행을 만들어가고 있습니다. 금융과 IT의 차이를 존중하며 수평적으로 소통합니다. 모든 과정과 정보는 수평성과 존중을 기반으로 공유되고 혁신의 즐거움을 경험하실 수 있을 것입니다. 카카오뱅크는 불가능을 가능하게 만들기 위해 논의하고 합심하는 공간입니다. 카카오뱅크에 재미 있으신 분들은 아래 채용공고 참고바랍니다. 채용공고 보러 가기 기업의 경영관리 공시자료, 공공기관의 오픈 자료, 보도자료 등을 토대로 산출한 평균 연봉으로 실제 연봉과 차이가 있을 수 있으니 참고 부탁드립니다.
시공간 복잡도
n을 문자열 배열 record의 크기라고 할 때 시간 복잡도 On 공간 복잡도 ???이거 생각해봤는데. c string vector 메모리 할당 방식에 따라 갈릴 것 같다. 런타임에 동적으로 할당해서 1D string vector를 2D string vector로 바꾸더라도 유의미한 메모리 할당은 늘어나지 않을지, 아니면 정적 사이즈를 할당하고 필요시 느는 방식인지 궁금합니다. 전자이면 On일 것이고 후자이면 OMW일 것입니다.
문제 풀이
1. 미리 알파벳을 선언하고 2. 들어온 msg를 하나씩 before 변수에 추가해줍니다. 3. 만약 before가 미리 정의해둔 words에 해당 문자가 없으면 4. 새로 들어온 문자 전까지의 문자열사전에 있는 문자의 인덱스를 구해서 1을 더하고 해당 추가된 인덱스 정보를 answer에 푸시합니다. 5. words에서 현재 입력과 일치하는 가장 긴 문자열을 찾아 해당 색인번호를 출력하고, 입력에서 해당 문자를 제거합니다.
6. 새로운 단어를 words에 등록해주고 7. 다음으로 현재 입력된 문자부터 for문을 반복 적용합니다. 8. 이후 before가 남아있다면, words에 있는 단어가 걸러지지 못한 것이므로 인덱스를 찾고 1을 더해 푸시해줍니다.