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 |
Tags
- 9장
- BOJ
- 2166번
- 냄새와 휴리스틱
- Design Pattern
- 17장
- 10830번
- Adapater Pattern
- 11286번
- 자바의 정석
- DxTrace
- 11758번
- programmers
- springboot
- 가장 긴 증가하는 부분 수열2
- 클린코드
- 코딩 테스트
- 백준
- java의 정석
- Spring
- java
- SerialDate 리펙터링
- 코딩테스트
- 1043번
- 2206번
- 2156번
- Design Patterns
- 1300번
- Dxerr.h
- 프로그래머스
Archives
- Today
- Total
Don't give up!
[프로그래머스] 보석 쇼핑 (java) 본문
코딩테스트 연습 - 보석 쇼핑 | 프로그래머스 (programmers.co.kr)
어떻게 생각하고 문제를 풀었는가?
가장 짧은 구간을 구하기 위해서는 전체 보석의 종류를 알아야 하고, 어떤 위치에서 시작했을 때 구간의 길이가 몇인지 확인해야 합니다.
시작 위치는 1번째 보석부터 차례대로 이동하므로 FIFO인 자료구조 Queue에서 원소가 지워지는 과정과 비슷하게 볼 수 있으며, 순서대로 원소를 삽입하면서 Queue에 삽입된 원소의 종류가 전체 보석의 종류와 비슷한 순간을 확인하고 시작 위치를 이동시킬 수 있습니다.
Queue에서 원소를 삭제할 때 Queue에 담긴 보석의 종류가 보존되는지 확인이 필요합니다.
따라서 HashMap에 각 보석의 개수를 저장, 원소의 삭제마다 보석의 수를 차감하면서 이를 확인할 수 있습니다.
코드
import java.util.*;
class Solution {
public int[] solution(String[] gems) {
Queue<String> queue = new LinkedList<>();
HashMap<String, Integer> map = new HashMap<>();
int length = gems.length;
for(int i=0; i<gems.length; i++){
map.put(gems[i],0);
}
int maxkinds = map.size();
int start=0, answer=0, kinds=0;
for(int i=0; i<gems.length; i++){
int count = map.get(gems[i]);
if(count==0) kinds++;
map.put(gems[i],count+1);
queue.offer(gems[i]);
if(kinds!=maxkinds) continue;
String str = queue.peek();
while(map.get(str)>1){
map.replace(str,map.get(str)-1);
start++;
queue.poll();
str = queue.peek();
}
if(length > queue.size()){
answer = start;
length = queue.size();
}
}
return new int[] {answer+1, answer+length};
}
}
최대 구간의 길이는 주어진 입력 배열의 크기입니다.
for문으로 queue 삽입과 HashMap value값 증가를 하며 HashMap에 해당 문자열이 처음 카운트되었다면 종류를 카운트하는 방식으로 시작 위치를 옮겨도 되는지 확인할 수 있습니다.
Queue의 첫 원소를 key로 갖는 HashMap value값이 2 이상인 경우 시작 위치를 옮겼을 때 종류가 유지된다고 생각할 수 있으므로 이때 시작위치를 이동할 수 있습니다.
모든 원소를 queue에 삽입한 후 최단 거리를 갖는 시작위치를 찾고, 마지막 위치를 시작위치 + 최단 구간의 길이로 구할 수 있습니다. 이때 시작위치 answer는 0부터 N-1로 정해져 있으므로 answer+1을 하여야 합니다.
'Coding Test > Programmers' 카테고리의 다른 글
[프로그래머스] N-Queen (java) (0) | 2021.06.23 |
---|---|
[프로그래머스] 단체사진 찍기 (java) (0) | 2021.06.21 |
[프로그래머스] 전화번호 목록 (0) | 2021.06.03 |