보석 쇼핑 - 카카오 인턴십 2020 프로그래머스 LV3 JAVA

문제 링크

프로그래머스

---

 

 

풀기

---

바로 캐치한 것은

Set을 활용한 보석 종류 확인 ▶ 나중에 조건으로 활용

딱 이거 하나였다

 

그래서 엄청나게 헤딩을 하며 풀었던 것 같다

부끄러운 헤딩의 흔적들..

 

import java.util.*;
public class Diamond3 {
	
	int[] Solution(String[] gems) {
		//보석 종류
		Set<String> set = new HashSet<>();
		for(String str : gems) set.add(str);
		System.out.println(set);
		//보석이 1종류면 즉시 끝냄
		if(set.size()==1) {
			int[] answer = {1,1};
			return answer;
		}
		
		//보석 종류랑 일치하면 멈추게 할 set
		Set<String> set2 = new HashSet<>();
		//보석 배열 담을 list		
		List<Integer> list = new ArrayList<>();
				
		int cnt=0;
		int cnt2=0;
		for(int i=0; i<gems.length; i++) {
			for(int j=i; j<gems.length; j++) {
				set2.add(gems[j]);
				if(set.size()==set2.size()) {
					cnt++;
					cnt2=j;
					set2.clear();
					list.add(i);
					list.add(j);					
					break;
				}
			}			
		}
		
		List<Integer> list2 = new ArrayList<>();
		int i=0;
		int j=1;
		while(j<=list.size()) {
			list2.add(list.get(j)-list.get(i));
			i+=2; j+=2;
		}		

		int[] answer = {};
		return answer;
	}
	
}

 

import java.util.*;
public class Diamond2 {
		
	int[] Solution(String[] gems) {
		//보석 종류
		Set<String> set = new HashSet<>();
		for(String str : gems) set.add(str);
		System.out.println(set);
		
//		보석이 종류당 몇 개씩 있는지
//		ㅡ>
//		Map<String, Integer> map = new HashMap<>();
//		for(String str : gems) map.put(str, (map.getOrDefault(str, 0))+1);
//		System.out.println(map);
		
		//새 배열에 gems를 다시 집어넣어서
		//앞에값이 뒤에값이랑 같으면 앞의 값을 0으로 만들어버리
		List<String> list = new ArrayList<>();
		for(String str : gems) list.add(str);
		System.out.println(list);
		
		for(int i=0; i<gems.length; i++) {			
			for(int j=0; j<gems.length; j++) {
				if(i!=j && gems[j]!="") {
					if(list.get(i)==list.get(j)) {
						gems[i]="";
						break;
					}					
				}					
			}			
		}
		for(String str : gems)System.out.println(str);
		
		// 정답 시작~끝지점 저장할 리스트
		List<Integer> list2 = new ArrayList<>();
		
		for(int i=0; i<gems.length; i++) {
			if(gems[i]!="") {
				list2.add(i);
			}
		}
		System.out.println(list2);
		int[] answer = {((list2.get(0))+1), ((list2.get(list2.size()))+1)}; 
		for(int i=0; i<answer.length; i++) {
			System.out.println(answer[i]);
		}
		return answer;
	}
}

 

어떻게든 한바퀴 도는 경우의 수들만 뽑아내려고 고민하고 집착했던 것 같다

뽑아내고 나니까 한바퀴 도는 경우의 출발지점과 도착지점이 여러개가 생기면서 더 복잡해졌다

문제에 대한 이해력도 부족하지만 이해했을 때 어떤 것을 활용해야 하는지에 대한 생각 정리가 잘 안됐던 것 같다

 

---

 

문제에서 결국 특정 구간이 빠지면서 한바퀴를 도는 것은 인정하지 않았기 때문에

"처음 것부터 순차적으로 돌면서 배열의 시작지점과 끝을 도출 해 내면 되겠구나"

라고 생각이 닿는 데 까지 2일이 걸렸다 ㅋㅋ

 

Queue를 활용하여 보석을 담고, 빼는 과정에서 겹치는 것들이 있는지 확인했고 보석을 포기해야 할 때는

순차적으로 포기하게 만들었다. 문제에서 연속적으로 선택을 해야했기 때문에

보석 종류별 갯수는 Map을 활용했다

 

start값은 q에서 poll이 되는 숫자 만큼 셋팅했다

해당 보석을 손에 쥐고있는데 뒤의 보석이 손에 쥐고있는 보석과 같으면 poll 해야하기 때문이다

 

end값은 기본값은 결국 gems의 길이일 것이라 생각했다

그리고 end는 최소값이여야 하기 때문에 end값이 만약 q의 size보다 크다면 계속 갱신해줘야한다

 

기존에 가지고 있던 중구난방한 머리속의 지식들을 조금 정리하게 된 문제였던 것 같다

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
    	//보석 종류
        Set<String> set = new HashSet<>();
        //보석 종류 별 갯수
        Map<String, Integer> map = new HashMap<>();
        //문제 조건이 연속선택이기 때문에 Queue사용
        Queue<String> q = new LinkedList<>();
        
        for(String str : gems) {
        	set.add(str);
        }
        
        int cnt=0;
        int start=0;
        int end=gems.length;
        
        for(String str : gems) {        	
        	q.offer(str);
        	map.put(str, map.getOrDefault(str, 0)+1);
        	
        	while(true) {
        		String peek = q.peek();
        		
        		if(map.get(peek)>1) {
        			q.poll();
        			map.put(peek, map.getOrDefault(peek, 0)-1);
        			cnt++;
        		}
        		else {        		
        			break;
        		}
            }
                        
        	if(map.size()==set.size() && end>q.size()) {
            	if(end>q.size()) {
	            	end=q.size();
	            	start=cnt;
        		}    
            }        	
        }       
    
        int[] answer = {start+1, start+end};    
        return answer;
    }	
}