[백준 11509 / java] 풍선맞추기

문제

11509번: 풍선 맞추기 (acmicpc.net)

 

풀이 1

처음 접근 : 재귀 -> 테케는 통과되었으나, 제출 결과 시간 초과

 

1. arr 배열에 값 입력받기

2. 인덱스 0부터 탐색 -> 해당 인덱스 뒤에 (해당 인덱스 값-1)인 숫자가 있는지 검사 -> 모두 방문처리, count++

3. 모든 인덱스를 다 방문처리할 때까지 반복

 

• 시간 초과가 뜬 이유

시간 제한 : 2초

입력값 : 1 <= N <= 1,000,000

 

각 N개의 풍선에 대해, 현재 풍선 높이보다 1 낮은 풍선이 있으면 solve 메서드를 재귀 호출.

이때, 이미 방문한 풍선은 무시한다.

최악의 경우 '5, 4, 3, 2, 1'과 같이 모든 풍선 높이가 연속적으로 감소하여 모든 풍선에 대해 재귀 호출이 일어난다.

-> 시간 복잡도 O(N^2)

 

1,000,000^2 >>>> 2억

따라서 시간 초과

코드 1

//시간 초과
import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[] arr;
    static boolean[] visited;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        visited = new boolean[N];

        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int count = 0;
        for(int i=0; i<N; i++){
            if(!visited[i]){
                solve(i);
                count++;
            }
        }
        bw.write(count + " ");
        bw.close();
    }
    static void solve(int start){ //한 턴!!
        visited[start] = true;
        for(int i=start+1; i<N; i++){
            if(arr[i] == arr[start]-1){
                solve(i);
                break;
            }
        }
    }
}

풀이 2

재귀 호출을 없애고 dp를 사용해 시간 복잡도를 낮춘다.

*dp : 큰 문제를 작은 문제로 나누어 해결, 해결된 작은 문제의 해답을 저장해두고 다음 단계에 사용하는 방법

arrows 배열 -> 각 높이의 풍선을 맞출 수 있는 화살의 개수를 저장하는 역할

 

1. arr 배열에 값 입력받기

2. 인덱스 0부터 탐색 -> 현재 높이의 풍선을 쏠 수 있는 화살이 있는지 확인 'arrows[arr[i]] > 0'

-> 없다면 화살 한 개 생성 'count++', 한 단계 낮은 높이의 화살 개수 증가시키기 'arrows[arr[i]-1]++'

-> 있다면 해당 높이의 화살 개수 줄이기 'arrows[arr[i]]--', 한 단계 낮은 높이의 화살 개수 증가시키기 'arrows[arr[i]-1]++'

 

코드 2

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[] arr;
    static int[] arrow; //높이별 현재 쏠 수 있는 화살의 개수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        arrow = new int[1000001];

        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int count = 0;
        for(int i=0; i<N; i++){
            if(arrow[arr[i]] > 0){ //현재 높이의 풍선을 터트릴 수 있는 화살이 있다면
                arrow[arr[i]]--;
                arrow[arr[i]-1]++;
            }else{ //화살이 없다면
            	count++; //화살 개수 추가
                arrow[arr[i]-1]++;
            }
        }
        bw.write(count + " ");
        bw.close();

    }

}

Note

• 재귀 외에 arrows 배열을 사용하는 아이디어를 스스로 떠올리지 못했다.
• arrows 배열을 사용해서 새로 풀었는데, ArraysIndexOutofBonds오류 -> 주어지는 화살 높이가 1~1,000,001 이므로 arrows의 크기가 N-1이 아니라 1,000,001가 되어야 한다.
• 참고한 풀이 https://j3sung.tistory.com/1106