[프로그래머스] 보석 쇼핑 (자바)

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

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

투 포인터를 사용하여 풀었습니다.

모든 경우를 검사하는 O(n^2)로 풀게 되면 10만 개의 수가 들어왔을 때 이 문제를 풀 수 없습니다.

 

Map을 이용하여 각 문자열의 개수를 확인했습니다.

이 문제의 답은 짧은 구간이 여러 곳이 있다면 가장 앞 쪽의 번호를 요구하고 있습니다.

우선 가장 앞 쪽의 구간을 찾은 후 뒤로 밀어가며 최적화를 해나가는 식으로 구현했습니다.

 

이런 식으로 left와 right를 이동하여 가장 앞 쪽의 최적 값을 찾았습니다.

이제 이 값을 뒤로 밀어가며 정답을 찾을 것입니다.

 

위에서 구한 크기의 window를 가지고 우측으로 밀었더니 조건을 만족하는 길이가 3번째에서 나왔습니다.

더 짧게 만들 수 있다면 짧아진 값을 정답으로 바꿔줍니다.

 

2번째 단계에서 최적 값을 찾았고 찾은 값으로 다시 window 탐색을 진행합니다.

끝까지 탐색해보고 없다면 찾은 정답을 반환해줍니다.

---

전역 변수

HashMap <String, Integer> map = 문자열 "key"가 "value"번 나온 것을 세줍니다.

answer [] = 정답 배열

메소드

int [] solution

문제에서 주어진 배열을 전부 map에 넣습니다.

그리고 초기값을 찾은 후 최적화를 진행합니다.

(search, opt 호출)

 

void search

right를 우선적으로 줄이고 더 이상 줄일 수 없을 때 left를 증가시킵니다.

이 과정을 통해 가장 앞 쪽의 window를 찾아낼 수 있습니다.

 

void opt

찾은 window를 뒤로 밀어주면서 최적화를 진행합니다.

한 칸씩 이동하며 그 칸의 값을 적절히 증가/감소시키며 0이 있는지 검사합니다.

0이 없다면 모든 문자열이 있다는 것이므로 window크기를 감소시킵니다.

 

이때 정답에서 요구하는 것은 가장 앞쪽의 최적 길이이므로 right -> left 순으로 이동합니다.

현재 window길이보다 바뀐 window 길이가 더 짧아졌다면 정답을 최신화해줍니다.

 

import java.util.*;

public class pm보석쇼핑 {
    
	public Map<String, Integer> map = new HashMap<String, Integer>();
	public int answer[];

	public int[] solution(String[] gems) {

		for(String gem : gems) {
			if(map.containsKey(gem))
				map.put(gem, map.get(gem) + 1);
			else
				map.put(gem, 1);
		}

		search(gems);
		opt(gems);
		
		return answer;
	}

	public void search(String[] gems) {
		int left = 0;
		int right = gems.length-1;

		boolean finish = false;

		while(!finish) {
			finish = true;
			if(map.get(gems[right]) > 1) {
				map.put(gems[right], map.get(gems[right])-1);
				right--;
				finish = false;
			}
		}

		finish = false;
		while(!finish) {
			finish = true;
			if(map.get(gems[left]) > 1) {
				map.put(gems[left], map.get(gems[left])-1);
				left++;
				finish = false;
			}
		}
		answer = new int[] {left+1, right+1};

	}

	public void opt(String[] gems) {
		int left = answer[0] - 1;
		int right = answer[1] - 1;
		int len = right - left;

		while(right < gems.length-1) {
			map.put(gems[left], map.get(gems[left])-1);
			left++;
			right++;
			map.put(gems[right], map.get(gems[right])+1);

			boolean b = false;
			while(!map.containsValue(0)) {
				while(!map.containsValue(0)) {
					b = true;
					map.put(gems[right], map.get(gems[right])-1);
					right--;
				}
				if(b) {
					right++;
					map.put(gems[right], map.get(gems[right])+1);
				}

				b = false;
				while(!map.containsValue(0)) {
					b = true;
					map.put(gems[left], map.get(gems[left])-1);
					left++;
				}
				if(b){
					left--;
					map.put(gems[left], map.get(gems[left])+1);
				}

				if(right-left == len)
					break;
				if(right-left < len) {
					answer = new int[] {left+1, right+1};
					len = right - left;
				}
			}

		}
	}

}

 

문제를 보자마자 투 포인터가 떠올라서 아이디어를 억지로 끼워 넣다 보니 효율이 그다지 좋지 않습니다.

물론 통과는 했지만 다른 코드와 비교했을 때 성능 차이가 심하게 납니다.

이것도 하나의 아이디어로 봐주시고 다른 코드도 공부하시는 것을 추천합니다.