문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/17684
코딩테스트 연습 - [3차] 압축
TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34]
programmers.co.kr
개인적으로 문제가 난해하다고 느꼈지만 예시대로 진행하면 쉽게 풀 수 있는 문제였습니다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <string> | |
#include <vector> | |
#include <map> | |
#include <iostream> | |
using namespace std; | |
const int MAX = 26; | |
int visitedIdx = 1; | |
map<string, int> visited; | |
void init() | |
{ | |
char c = 'A'; | |
for (int i = 0; i < MAX; i++) | |
{ | |
string temp(1, c++); | |
visited[temp] = visitedIdx++; | |
} | |
} | |
vector<int> solution(string msg) { | |
init(); | |
vector<int> answer; | |
for (int i = 0; i < msg.length(); i++) | |
{ | |
string cur, next; | |
for (int j = 0; j < msg.length() - i; j++) | |
{ | |
cur = msg.substr(i, j + 1); | |
next = msg.substr(i, j + 2); | |
if (visited.count(cur)) | |
{ | |
if (cur == next) | |
{ | |
answer.push_back(visited[cur]); | |
i += j; | |
break; | |
} | |
if (visited.count(next)) | |
{ | |
continue; | |
} | |
answer.push_back(visited[cur]); | |
visited[next] = visitedIdx++; | |
i += j; | |
break; | |
} | |
} | |
} | |
return answer; | |
} | |
int main(void) | |
{ | |
vector<int> answer = solution("TOBEORNOTTOBEORTOBEORNOT"); | |
for (int a : answer) | |
{ | |
cout << a << " "; | |
} | |
cout << "\n"; | |
return 0; | |
} |

개발환경: Programmers IDE
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > programmers' 카테고리의 다른 글
[Programmers] 올바른 괄호 (0) | 2022.03.01 |
---|---|
[Programmers] [3차] 파일명 정렬 (0) | 2022.02.25 |
[Programmers] 가장 큰 정사각형 찾기 (0) | 2022.02.23 |
[Programmers] 방금그곡 (0) | 2022.02.16 |
[Programmers] 캐시 (0) | 2022.02.14 |