프로그래머스 [3차] 압축(2018 KAKAO BLIND RECRUITMENT)

문제 URL : https://programmers.co.kr/learn/courses/30/lessons/17684

코딩테스트 연습 - [3차] 압축

 

문제 접근법 :  map이든 hashmap이든 어떤것을 이용하든 상관없습니다.

처음 A~Z까지 1~26을 부여하고

string s가 ABCDE일때

인덱스0번부터시작해서 접미사 부분문자열중 가장 긴것이 map안에 존재하는지 확인하여

몇번째 인지 answer값에 넣어주면 되는문제입니다.

ABCDE일때

첫 ABCDE,ABCD,ABC,AB 는 map안에 존재안하게 되고

w는 A가 될때 1번이 그 다음인덱스는

0번에서 w의사이즈만큼 증가시면됩니다. 그렇다면 그다음 인덱스는 1이되고 가리키는것은

B일테니  c = b가되어

w+c= AB가 됩니다. 이것을 끝날때까지 반복하면됩니다.

소스코드 :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

//By 콩순이냉장고 #include <bits/stdc++.h> using namespace std; vector<int> solution(string msg) {     vector<int> answer;     unordered_map<string, int> dict;     for (int i = 0; i < 26; i++) {         string s(1, 'A' + i);         dict[s] = i + 1;     }     int cnt = 27;     for (int i = 0; i < msg.size(); ) {         string s = msg.substr(i);         for (int j = 0; j < s.size(); j++) {             string w = s.substr(0, s.size() - j);             if (dict.count(w)) {                 answer.push_back(dict[w]);                 i += w.size();                 dict[w + msg[i]] = cnt++;                 break;             }         }           }     return answer; } Colored by Color Scripter

cs

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.