-
카카오 2018 코테 문제2 LZW 압축 문제 (C++)C++ 2021. 10. 2. 02:17
카카오 2018 코테에서 나왔던 문제이고, 2번 문제이다. 카카오 사이트 확인해보니, 정답률이 95.8%로 가장 많은 지원자가 푼 문제라고 한다.
사담) 저 때 출제된 문제들 중 가장 쉬운 문제..? 나는..푸는데 2시간은 걸렸...
문제를 읽고 코딩 전에 설계한 부분은 다음과 같다.
- 알파벳을 저장할 변수 : 사전형이고 겹치는 일이 없으므로 map 자료구조 사용 (단어, 색인)형태
- 입력받은 string을 저장할 변수 : 한 글자씩 읽어야 하니까 그냥 쉽게 배열 사용
- 정답을 그냥 출력하는게 아니라 [ 1,2,3 ] 이런 형태로 맞춰야하므로 정답 저장용 vector를 사용
- 검색용 string(search)에 추가로 temp라는 임시변수가 필요할 것 같다. 사전에 있다면 다음글자도 읽어줘야하므로.
- while문으로 반복문을 돌리며 검색할건데, 조건은 배열에 담긴 문자열의 끝 '/0' 만날때까지로 하자.
- 읽은 글자가 사전에 있는 경우라면 temp에 현재 상태 저장해두고 search에 다음글자도 읽어서 추가
- 없는 경우 끝내야하므로 이전상태인 temp로 사전에 검색해서 index를 정답 벡터에 저장, temp와 search 초기화
- 마지막에 남은 글자처리를 반복문 바깥에 해줄 것 (ex. kakao면 o가 if문에 걸리고 else에 안들어가므로 answer에 저장되지 않는 문제가 있다) -> 이 작업 때문에 헤맸다(..)
위에서 생각해둔 걸 기반으로 코딩을 해보자.
#include <iostream> #include <ctype.h> #include <map> #include <algorithm> #include <string> #include <vector> using namespace std; map <string, int> dictionary; map <string, int> :: iterator iter;
0. 필요한 헤더파일
- map, string, vector 자료형 사용하고 편리한 사용을 위해 namespace std추가
- ctype.h는 혹시 input에 소문자 들어오는 경우 대문자로 바꿔주려고 toupper을 임의로 추가해놨다. (영문 대문자만 처리한다고 문제에서 나와있긴 하지만 공부용으로)
- 그 외에 map의 반복자랑 전역변수로 dictionary를 선언해뒀다..
//dictionary 초기화. 대문자 : 아스키코드 65~90 for(i=65; i<=90; i++) { temp = (char)i; dictionary.insert(make_pair(temp, i-64)); } size = dictionary.size(); temp = "";
1. dictionary 를 초기화하기
- 대문자의 아스키코드가 65~90인데, 이를 (char)형태로 변환하여 temp 변수에다가 넣는다. 이 알파벳들의 인덱스는 1~26이므로 dictionary에 insert할 때 i-64로 인덱스를 넣는다.
- size 변수는 문자열을 읽으면서 새롭게 만드는 단어들에게 인덱스를 줘야하므로 필요하다.
- temp변수는 밑에서 사용하므로 꼭 다시 초기화 해줄 것!
while(input[pos] != '\0') { search += toupper(input[pos]); //혹시 input에 소문자 있을 경우 대비 toupper적용. if (dictionary.find(search) != dictionary.end()) { temp = search; // 처음에 temp+=search로 실수했는데, 이러면 k가 kka로 중첩되어 버린다. pos++; } //search가 사전에 있는 경우 else { iter = dictionary.find(temp); answer.push_back((*iter).second); //temp에 있던 단어의 색인 dictionary.insert(make_pair(search, ++size)); //사전에 추가 temp = ""; search=""; } } //마지막에 if에 걸려서 끝나는 경우까지 answer에 넣어줌. iter = dictionary.find(temp); answer.push_back((*iter).second);
2. 사전(dictionary) 작업 및 문자열 분석
- 위의 아이디어 부분에서 적어둔 것들을 거의 그대로 가져다 썼다.
- search += toupper(input[pos]) 로 다음 읽은 글자들까지 search에 저장해둔다.
저 부분에서 처음에 temp += search로 해놨었는데 위에 써둔 주석처럼 중첩된다. 그냥 temp=search하면 되는데 생각이 없었다...
- dictionary.find(temp)를 사용하면 반복자 iterator를 리턴. answer에 넣을때는 인덱스값을 넣어야 하므로 (*iter).second로 넣어야한다.
- ++size로 넣는 이유는 size가 5라면 다음에 들어갈 단어의 인덱스는 6으로 들어가야 하기 때문
- else문에 걸려서 temp값 answer에 넣었으므로 다시 temp, search초기화 해줄 것.
//answer를 배열형태로 출력 cout<<"["; for(i=0; i<answer.size()-1; i++) { cout<<answer[i]<<", "; } cout<<answer[i]<<"]"<<endl;
3. 출력하기
- answer에 들어있는걸 배열 형태로 출력해야 한다.
- [ 기호 먼저 출력하고 answer.size()-1 까지 반복문을 돌린다. 이유는 맨 마지막 원소 뒤에는 반점이 없어야 하므로.
- 반복문을 빠져나오고 나서 마지막 원소와 닫는 대괄호 ] 를 출력해주면 된다.
4. 전체 코드
#include <iostream> #include <ctype.h> #include <map> #include <algorithm> #include <string> #include <vector> using namespace std; map <string, int> dictionary; map <string, int> :: iterator iter; int main() { string search = "", temp = ""; char input[1001]; vector <int> answer; int i, size, pos = 0; cin>>input; for(i=65; i<=90; i++) { temp = (char)i; dictionary.insert(make_pair(temp, i-64)); } size = dictionary.size(); temp = ""; while(input[pos] != '\0') { search += toupper(input[pos]); if (dictionary.find(search) != dictionary.end()) { temp = search; pos++; } else { iter = dictionary.find(temp); answer.push_back((*iter).second); dictionary.insert(make_pair(search, ++size)); temp = ""; search=""; } } iter = dictionary.find(temp); answer.push_back((*iter).second); cout<<"["; for(i=0; i<answer.size()-1; i++) { cout<<answer[i]<<", "; } cout<<answer[i]<<"]"<<endl; }
추가적으로 공부용으로 코드 돌아가는거 종이에 써가면서 while문 안쪽 코드 분석도 해봤다.
(input값으로 KAKAO가 들어갔을때)
pos 값 : 0 pos 값 : 1 pos 값 : 1 pos 값 : 2 search = K search = KA search = A search = AK if문에 걸림 else문에 걸림 if문에 걸림 else문에 걸림 temp = K
pos++;temp = K → answer에 11(K) 들어감
dictionary에 (KA, 27)temp = A
pos++;temp = A → answer에 1(A) 들어감
dictionary에 (AK, 28)pos 값 : 2 pos 값 : 3 pos 값 : 4 pos 값 : 4 search = K search = KA search = KAO search = O if문에 걸림 if문에 걸림 else문에 걸림 if문에 걸림 temp = K
pos++;temp = KA
pos++;temp = KA → answer에 28(KA) 들어감
dictionary에 (KAO, 29)temp = O
pos++;
→ '/0'만나서 반복문 끝그러고 나서 마지막에 temp = O였으므로 O를 사전에서 찾은 뒤, O의 인덱스값 15를 answer에 넣으면 된다.
위와같이 정답이 잘 나오는 것을 확인할 수 있다!
'C++' 카테고리의 다른 글
백준 13458번 시험감독 (0) 2021.12.11 백준 2503번 숫자야구 (0) 2021.12.11 연속된 자연수의 합 (백준 2018번 : 수들의 합 5) (0) 2021.09.11