Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 시뮬레이션
- 이분탐색
- 동적계획법
- 투 포인터
- 알고리즘
- 수학
- Effective Java
- 구현
- 에라토스테네스의 체
- 완전탐색
- mst
- JUnit 5
- BFS
- 플로이드-와샬
- dfs
- 백준
- 위상정렬
- 후니의 쉽게 쓴 시스코 네트워킹
- swea
- 그리디
- CS
- Kotlin
- Network
- 프로그래머스
- 유니온 파인드
- 문자열
- 백트래킹
- java
- 스택
- 세그먼트 트리
Archives
반갑습니다!
[프로그래머스] 압축 본문
풀이
LZW 알고리즘을 구현하는 문제이다. map<string, int>
를 사용해서 사전을 구현해서 해결하였다.
코드
C++
#include <string>
#include <vector>
#include <map>
using namespace std;
// 알파벳 미리 세팅
void setting(map<string, int>& m) {
for (int i = 0; i < 26; i++) {
string tmp = "";
tmp += (char)('A' + i);
m[tmp] = i + 1;
}
}
vector<int> solution(string msg) {
vector<int> answer;
map<string, int> m;
// 사전 초기화
setting(m);
// msg의 인덱스
int idx = 0;
// 사전에 없는 글자가 나올 때 매핑해줄 값
int mapping = 27;
// msg를 다 탐색할 때까지 반복
while(idx < msg.length()){
string tok;
// idx 위치에서 길이가 짧아지는 순서로 문자열 자르기
for (int i = msg.length(); i > idx; i--) {
tok = msg.substr(idx, i - idx);
// 사전에 등록된 문자열을 발견한 경우
if (m.find(tok) != m.end()) break;
}
// 정수값 저장
answer.push_back(m[tok]);
// 인덱스 값 조정
idx += tok.size();
// 뒤에 글자가 남아있는 경우
if (idx < msg.length()) {
tok += msg[idx];
// 사전에 등록
m[tok] = mapping++;
}
}
return answer;
}
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
class Solution {
public int[] solution(String msg) {
ArrayList<Integer> arr = new ArrayList<>();
HashMap<String, Integer> map = new HashMap<>();
// 사전 초기화
for (int i = 0; i < 26; i++) map.put(String.valueOf((char) ('A' + i)), i + 1);
// msg의 인덱스
int idx = 0;
// 사전에 없는 글자가 나올 때 매핑해줄 값
int mapping = 27;
// msg를 다 탐색할 때까지 반복
while (idx < msg.length()) {
String tok = "";
// idx 위치에서 길이가 짧아지는 순서로 문자열 자르기
for (int i = msg.length(); i > idx; i--) {
tok = msg.substring(idx, i);
// 사전에 등록된 문자열을 발견한 경우
if (map.containsKey(tok)) break;
}
// 정수값 저장
arr.add(map.get(tok));
// 인덱스 값 조정
idx += tok.length();
// 뒤에 글자가 남아있는 경우
if (idx < msg.length())
// 사전에 등록
map.put(tok + msg.charAt(idx), mapping++);
}
int[] answer = new int[arr.size()];
for (int i = 0; i < arr.size(); i++) answer[i] = arr.get(i);
return answer;
}
}
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 2665 미로만들기 (0) | 2020.05.05 |
---|---|
[프로그래머스] 파일명 정렬 (0) | 2020.05.04 |
[백준] 14503 로봇 청소기 (0) | 2020.05.04 |
[백준] 1194 달이 차오른다, 가자. (0) | 2020.05.03 |
[백준] 16986 인싸들의 가위바위보 (0) | 2020.05.02 |