안녕하세요. 오늘 풀어볼 문제는 프로그래머스의 보석 쇼핑문제입니다. 이 문제는 2020 카카오 인턴십에서 출제되었습니다.
1) 문제 링크
https://programmers.co.kr/learn/courses/30/lessons/67258
2) 문제 풀이
✔ gems 배열에 저장된 보석들의 종류 구하기 : set 이용
우선, gems 배열에 저장된 보석들 종류가 몇 가지인지 구해야 합니다. set은 원소를 중복하지 않고 저장하기 때문에, set을 선언해서 해당 set에 gems배열 값들을 넣으면 구할 수 있습니다.
✔ 투포인터 문제 : left, right 두 개의 포인터 사용하기
이 문제는 투포인터 문제입니다. 투포인터 알고리즘은 리스트(혹은 배열)에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘입니다. 문제에서는 left, right 변수를 이용해서 두 개 점의 위치를 기록한다음, right-left 결과값이 가장 작은 left와 right포인터를 출력하는 문제입니다.
✔ while 로직 흐름 설명
문제 풀이 코드에서 left, right 포인터를 이용한 로직은 다음과 같습니다.
○ 포인터 흐름을 담는 map 선언
key가 String이고 value가 Integer인 map을 선언합니다. 이 때 value값은 map에 저장된 String의 갯수입니다. 예시로, 아래 그림에서 right포인터가 3번까지 이동하면, DIA가 2개, RUBY가 2개 이므로 map에는 {DIA=2, RUBY=2}가 저장됩니다.
① right 포인터 이동
right포인터가 이동되면 선언된 map에 해당 내용을 저장합니다. set size(gems 배열에 선언된 보석 종류의 수)와 map size가 같을 때까지 right 포인터를 이동합니다.
② left 포인터 이동
right포인터가 6까지 이동되었을 때, map에는 {DIA=3, RUBY=2, EMERALD=1, SAPHIRE=1}가 저장되어 있습니다.(순서는 다를 수 있음) map의 size도 4, set의 size도 4로 서로 같으므로, 이번엔 left포인터가 이동합니다. left포인터는 이동할 때마다 map의 Integer value값을 하나씩 삭제합니다. 만약 map의 value가 0이면 해당 key를 map에서 아예 삭제합니다.
map size와 set size가 계속해서 서로 같으면, right-left를 계산한 후 distance변수에 저장하고, 이전 distance보다 작으면 right포인터 값과 left포인터 값을 저장합니다.
③ right 포인터 이동
left포인터가 3까지 이동되면, map에는 {DIA=2, EMERALD=1, SAPHIRE=1}이 저장되어 있습니다.(순서 다를 수 있음) 이제 더이상 map size와 set size가 같지 않으므로, 이번에는 right 포인터를 이동합니다. 아까 ①처럼 right포인터가 이동할 때마다 map의 value값을 하나씩 올려줍니다.
④ right 포인터가 gems배열 끝에 도달
right 포인터가 gems배열 끝에 도달했으므로, 해당 로직을 종료합니다. ②에서 계산하고 저장한 right포인터와 left포인터값을 출력해주면 됩니다.
3) 전체 코드
import java.util.*;
class Solution {
public int[] solution(String[] gems) {
int[] answer = new int[2];
Set<String> gemSet = new HashSet<>();
Collections.addAll(gemSet, gems);
Map<String, Integer> map = new HashMap<>();
int gemSize = gemSet.size();
int arrSize = gems.length;
//움직이는 변수들 길이 저장하는 변수
int distance = Integer.MAX_VALUE;
//움직이는 변수(left, right)
int right = 0;
int left = 0;
//정답 위한 변수(start, end)
int start = 0;
int end = 0;
while (true) {
if (map.size() == gemSize) { //left가 움직일 차례, map에 있는 원소 빼는 역할
String leftGem = gems[left];
map.put(leftGem, map.get(leftGem) - 1);
if (map.get(leftGem) == 0) {
map.remove(leftGem);
}
left++;
} else if (right == arrSize) {
break;
} else { //right가 움직임, map에 원소를 더하는 역할
String rightGem = gems[right];
map.put(rightGem, map.getOrDefault(rightGem, 0) + 1);
right++;
}
if (map.size() == gemSize) {
if (right - left < distance) {
distance = right - left;
start = left + 1;
end = right;
}
}
}
answer[0] = start;
answer[1] = end;
return answer;
}
}4) 느낀점
✔ map getOrDefault의 이용
map.getOrDefault(a, b)의 a 자리에 들어가는 건 "KEY" 그 자체였다. 나는 key가 아니라 map.get(key)한 value값이 들어가야 하는줄 알고 잘못 짰었다. 이 메서드는 많이 쓰일 것 같으니 꼭!! 기억해둬야겠다.
✔ 투포인터 문제 풀어본 소감
투포인터 문제는 처음 풀어봤는데, 생각보다 재미있게 풀었다. 내 벨로그를 보면 bfs/dfs문제 풀이가 다른 알고리즘 기법들에 비해 많은데, 편파적으로 풀지 말고 투포인터나 이진탐색 등 다양한 문제를 풀어봐야겠다.
