[문제풀이] 풍선터트리기

업데이트:

문제 링크 : 풍선터트리기

풀이 시간 : 30분

1. 문제 풀이

붙어 있는 풍선 2개 중 하나를 터트려서 마지막까지 남을 수 있는 풍선 값 개수 구하는 문제

최대 한 번만 작은 값 풍선을 터트릴 수 있고 나머지는 큰 값의 풍선을 터트린다.

인덱스 i를 기준으로 0 ~ i 번째까지 가장 작은 풍선, i+1 부터 끝까지 중 가장 작은 풍선을 중복없이 개수를 세면 되는 문제

1) 0 ~ i 번째 까지 최소 값을 찾아준다.

2) i+1 ~ 끝까지 최소 값을 찾아준다.

3) 그 후 중복 없이 개수를 리턴한다.

2. 소스 코드

    public int solution(int[] a) {
		HashSet<Integer> hs = new HashSet<>();
		int min = a[0];
		for (int i = 1; i < a.length; i++) {
			// i 기준으로 왼쪽에서 가장 작은 값 저장
			hs.add(min);
			min = Math.min(a[i], min);
		}
		min = a[a.length - 1];
		for (int i = a.length - 2; i >= 0; i--) {
			// i 기준으로 오른쪽에서 가장 작은 값 저장
			hs.add(min);
			min = Math.min(a[i], min);
		}
		return hs.size();
	}

3. 후기

프로그래머스 월간 코드 챌린지 시즌 1에서 출제된 3번째 문제

최대 한번만 작은 풍선을 터트릴 수 있기 때문에 결국 i 위치에서 왼쪽과 오른쪽의 최소 값을 찾아주면 되는 문제였다.

결국 왼쪽과 오른쪽의 최소값을 어떤 것을 사용하든 최대 한번만 작은 풍선을 터트리는 경우가 생기기 때문이다.

하지만 i 위치 일때마다 왼쪽과 오른쪽의 최소값을 구하게 되면 n*n이 걸리게 되므로 미리 왼쪽과 오른쪽 기준으로 최소값을 구하면 된다.(2n)

참고