(Java)프로그래머스 코딩테스트 연습 - 월간 코드 챌린지 시즌1 - 풍선 터트리기

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/68646#qna

코딩테스트 연습 - 풍선 터트리기

2. 나의 풀이

class Solution {
    public int solution(int[] a) {
        //System.out.println("a : " + Arrays.toString(a));
    	//System.out.println("");
        int answer = 2;
        int [] min = new int[2];
        min[0] = a[0];
        min[1] = a[a.length - 1];
        int left = 1;
        int right = a.length - 2;
        for(int i = 1; i < a.length - 1; i = i + 1) {
        	if(min[0] > min[1]) {
        		if(a[left] < min[0]) {
        			min[0] = a[left];
        			answer += 1;
        		}
        		left += 1;
        	}else if(min[1] > min[0]) {
        		if(a[right] < min[1]) {
        			min[1] = a[right];
        			answer += 1;
        		}
        		right -= 1;
        	}
        	//System.out.println(i + "번째 min : " + Arrays.toString(min) + ", left 위치 : " + left + ", right 위치 : " + right);
        }
        return answer;
    }
}

 - 처음 실패 원인 : 처음 문제를 보고 구현하려던 로직은 배열의 1번 인덱스부터 마지막의 하나 전의 인덱스까지 반복을 하면서 인덱스 기준 오른쪽과 왼쪽의 최소값을 각각 구한 후 둘 중 큰 최소값보다 해당 인덱스의 값이 작은지를 확인하는 로직이였다. 실패의 원인은 배열의 크기가 커짐에 따라 시간 초과가 나는 것에 있었고, 그 후 시간 초과를 해결하기 위해서 왼쪽의 최소값과 오른쪽의 최소값을 저장한 후 인덱스를 하나 씩 이동하면서 최솟값을 갱신하는 방식으로 로직을 다시 구현하여 문제를 해결

3. 다른 사람 풀이

import java.util.*;
class Solution {
    public int solution(int[] a) {
        int answer = 0;
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        HashSet<Integer> hs = new HashSet<>();
        // int[][] dp=new int[a.length][2];
        for(int i=0;i<a.length;i++){
            min1=Math.min(min1,a[i]);
            min2=Math.min(min2,a[a.length-1-i]);
            hs.add(min1);
            hs.add(min2);
            // dp[i][0]=min1;
            // dp[a.length-1-i][1]=min2;

        }
        // for(int i=0;i<dp.length;i++){
        //     System.out.println(dp[i][0]+" "+dp[i][1]);
        // }
        return hs.size();
    }
}