LEVEL 3 : 보석쇼핑

https://programmers.co.kr/learn/courses/30/lessons/67258

코딩테스트 연습 - 보석 쇼핑

 

• 문제

  • 

    문제

  • 

    예시

 

---

풀이

• 투 포인터 문제이다.
  • 투 포인터로 해결하는 것 까지는 생각했지만, 코드로 구현하는 것을 하지 못하여 결국 다른 사람 코드를 참조했다ㅠㅠ
• Set을 사용하여 중복을 제거한 보석을 담고(모든 보석 종류), Map을 활용하여 투 포인터 간의 간격 사이에 존재하는 보석을 종류, 개수를 파악한다.
  • 만약 set의 크기와 map의 크기가 같다면 모든 보석이 존재 하는 거니까 left++
  • 만약 right가 배열의 크기를 초과하면 break
  • 모두 아니라면 right ++
  • 해당 조건문을 모두 탄 뒤, 투포인터의 위치가 정해지면 set과 map을 크기가 같은지(모든 보석을 포함하는지)와 그게 그 구간을 길이가 최소인지를 판단하여 최소라면 그때의 시작 지점, 종료지점을 저장한다(정답)
• Map을 활용하여 크기비교하며, 투 포인터의 left를 증가시키는 것이 신박했던 풀이이다(아직 부족ㅜㅜ).

• public static int[] solution(String[] gems) {
          int[] answer = new int[2]; //[0] : 시작위치, [1] : 종료위치
          Set<String> set = new HashSet<>(); // 중복되지 않는 보석을 저장할 Set, 보석종류 파악
          for(String gem : gems) // 모든 보석을 중복되지 않게 저장
          	set.add(gem);
          int left = 0;  // left
          int right = 0; // right
          int dis = Integer.MAX_VALUE; // 처음 모든 보석을 포함한 길이 최댓값으로 초기화
          Map<String,Integer> map = new HashMap<>(); // 투포인터 위치 안에 존재할 보석, 갯수
          while(true) {
          	if(map.size() == set.size()) { //보석모든 종류 == 투포인터내 가지고 있는 보석 종류
          		map.put(gems[left], map.get(gems[left])-1); //모든 보석을 다 가지고 있을경우, left에 존재했던 보석을 갯수를 하나 줄이고
          		if(map.get(gems[left]) == 0) // 그 줄인 보석을 갯수가 0이면 투포인터 내에 그 줄일 보석을 제거해줘야된다.
          			map.remove(gems[left]);//보석 제거
          		left++;//left증가
          	}else if(right == gems.length) { // 더이상 없다
          		break;
          	}else { //투포인터을 범위를 증가시켜 투포인터 안에 모든 보석이 담기도록 right++
          		map.put(gems[right], map.getOrDefault(gems[right],0)+1); // 만약 투포인터 내에 보석이 없었다면 1개, 있다면 그 보석을 갯수 + 1로 세팅해준다
          		right++; //right 증가
          	}
          	if(map.size() == set.size()) {//보석모든 종류 == 투포인터내 가지고 있는 보석 종류
          		if(right - left < dis) { //범위가 최소일경우
          			dis = right - left; //최소범위 = dis
          			answer[0] = left+1; 
          			answer[1] = right;
          		}
          	}
          }
          return answer;
      }