🔗 문제 링크
[프로그래머스] 압축 / 2018 KAKAO BLIND RECRUITMENT(3차)
📝 풀이 과정
문자열을 반복해서 사전에 넣고 찾는 작업을 해야하고, String(문자열)과 int(색인 번호)를 동시에 저장할 수 있는 Map
을 사용하기로 했다. 길이가 1인 문자열을 모두 넣어주기 위해 반복문을 돌며 Map.put 해주었고, 입력 문자열을 하나씩 끊어 반복문을 돌며 탐색하였다.
map.containsKey
를 통해 만약 현재 key
가 사전에 없을 때까지 뒤에 덧붙이는 방식을 사용했다. 사전에 없는 문자열이 나왔다면 반복문을 탈출하고 현재 문자열 - 1은 사전에 존재했기 때문에 그만큼을 사전에서 꺼내 정답 List에 add하고, 없던 문자열은 새롭게 사전에 추가해주었다.
💻 코드
import java.util.*;
class Solution {
public int[] solution(String msg) {
List<Integer> ans = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();
// 모든 알파벳을 미리 Map에 넣어둠
for (int i = 0; i < 26; i++)
map.put((char) ('A' + i) + "", i + 1);
char[] arr = msg.toCharArray();
int idx = 1;
StringBuilder key = null; // Map에서 찾아볼 String
while (idx <= msg.length()) {
// --idx를 통해 이전에 put했던 문자열의 마지막 인덱스부터 시작
key = new StringBuilder(arr[--idx] + "");
while (++idx < msg.length() && map.containsKey(key.toString()))
key.append(arr[idx]);
// 이미 Map에 존재하면 key에 덧붙이고 없다면 새로 사전에 등록해야 하기때문에 탈출
if (idx == msg.length() && map.containsKey(key.toString()))
break;
ans.add(map.get(key.substring(0, key.length() - 1))); // 마지막에 없던거 나왔으니까 뒤에거 자르고 답에 추가
map.put(key.toString(), map.size() + 1); // 없던거 사전에 추가
}
ans.add(map.get(key.toString()));
return ans.stream().mapToInt(i -> i).toArray(); // List<Integer> to int array
}
}
'알고리즘 풀이 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 파일명 정렬 / 2018 KAKAO BLIND RECRUITMENT(3차) - JAVA (0) | 2021.01.25 |
---|---|
[프로그래머스] n진수 게임 / 2018 KAKAO BLIND RECRUITMENT(3차) - JAVA (0) | 2021.01.25 |
[프로그래머스] 방금그곡 / 2018 KAKAO BLIND RECRUITMENT(3차) - JAVA (0) | 2021.01.14 |
[프로그래머스] 캐시 / 2018 KAKAO BLIND RECRUITMENT(1차) - JAVA (0) | 2021.01.14 |
[프로그래머스] 프렌즈4블록 / 2018 KAKAO BLIND RECRUITMENT(1차) - JAVA (0) | 2021.01.11 |