[BOJ 10799번/LowerBound(Binary Search)] 쇠막대기 (Java)

문제 링크

https://www.acmicpc.net/problem/10799

10799번: 쇠막대기

백준 10799번 문제는 주어진 문자열에서 쇠막대기와 레이저의 배치를 나타내고, 몇 개의 조각으로 쇠막대기가 잘려지는지를 구하는 문제이다.

풀이 방법

1) 처음에 구상했던 방법

 - 배열을 이용해 쇠막대기 사이 위치의 인덱스들을 모두 돌며 레이저의 개수를 확인하여 쇠막대기의 잘린 조각 개수 세기

1. 스택을 이용한 레이저 및 쇠막대기의 위치 확인
    - 여는 괄호 '('를 만나면 스택에 추가한다.
    - 닫는 괄호 ')'를 만나면 스택에서 괄호를 꺼내어 레이저와 쇠막대기를 구분한다.
    - 레이저는 배열에 저장되며 레이저가 있는 곳의 인덱스 값에 +1로 값이 있음을 표현한다.
    - 쇠막대기 잘린 조각 개수 계산한다.
2. 저장된 쇠막대기의 위치를 기반으로 잘린 조각 개수를 계산
    - 각 쇠막대기의 시작 인덱스와 끝 인덱스 값을 가져온다.
    - 각 인덱스 값의 처음부터 끝까지 레이저 배열을 돌며 총 레이저 개수의 +1로 쇠막대기가 잘린 개수를 계산한다.

 - 위의 풀이에 따라 구현한 코드

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

public class Main {
	
	static class Pair {
		char sym;
		int index;
		
		public Pair(char sym, int index) {
			this.sym = sym;
	        this.index = index;
	    }
	}
	
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] lazer = new int[100000];
        Stack<int[]> stick = new Stack<int[]>();
    	
		String line = br.readLine();
		Stack<Pair> sym = new Stack<Pair>();
    		
		for(int j = 0; j < line.length(); j++) {
			char index = line.charAt(j);
			Pair curSym = new Pair(index, j);
			
			if(sym.isEmpty()) {
				sym.push(curSym);
			} else if(index == ')') {
				Pair compare = sym.pop();
				if(j - compare.index == 1) {
					lazer[compare.index]++;
				} else {
					stick.push(new int[]{compare.index, j});
				}
			} else {
				sym.push(new Pair(index, j));
			}
		}
		
		int partStick = 0;
		while(!stick.isEmpty()) {
			int[] curr = stick.pop();
			int startIndex = curr[0];
			int endIndex = curr[1];
			
			partStick++;
			for(int i = startIndex; i < endIndex; i++) {
            		// 해당 부분의 코드에서 시간초과가 발생할 수 있겠다고 생각했다.
				if(lazer[i] != 0) {
					partStick++;
				}
			}
		}
		System.out.println(partStick);
		
        br.close();
    }
}

 - 기존 코드의 시간복잡도
코드에서 가장 시간이 많이 소요되는 부분은 쇠막대기마다 레이저의 개수를 세는 부분이다. 이 부분에서 최악의 경우, 입력 문자열의 길이가 N이라면, 모든 쇠막대기마다 레이저를 확인해야 하므로 O(N^2)에 가까운 시간 복잡도를 가질 수 있다고 생각했다. 따라서 이를 개선하기 위해 lowerbound개념을 생각하게 되었고, 이진 탐색을 활용한 최적화 방법을 적용했다.(마침 백준에서도 시간초과로 인해 문제를 해결하지 못했다.)

2) lower bound의 간략한 개념

이진탐색(Binary Search)은 데이터 내의 특정 값으 찾아내는 알고리즘이다.
lower bound와 upper bound 는 이진탐색 알고리즘에서 변형된 것으로 중복된 자료가 있을때 유용하게 탐색할 수 있는 알고리즘이다.

• lower bound는 데이터내 특정 K값보다 같거나 큰값이 처음 나오는 위치를 리턴
• upper bound 는 K값보다 처음으로 큰 값이 나오는 위치를 리턴

 

 

3) lower bound 개념을 활용하여 이진탐색으로 코드 최적화

 - 정렬된 레이저배열에 막대의 startIndx와 endIndex가 들어갈 수 있는 값의 인덱스 차이를 통해 레이저 개수 확인

1. 스택을 이용한 레이저 및 쇠막대기의 위치 확인
    - 여는 괄호 '('를 만나면 스택에 추가한다.
    - 닫는 괄호 ')'를 만나면 스택에서 괄호를 꺼내어 레이저와 쇠막대기를 구분한다.
    - 레이저는 확인 즉시 배열에 저장되며 구조상 인덱스 값이 오름차순으로 정렬된 상태로 저장된다.
    - 쇠막대기 잘린 조각 개수 계산한다.
2. 저장된 쇠막대기의 위치를 기반으로 잘린 조각 개수를 계산
    - 각 쇠막대기의 시작 인덱스와 끝 인덱스 값을 가져온다.
    - 이진탐색을 이용하여 레이저배열에서 주어진 값보다 크거나 같은 첫 번째 원소의 인덱스를 반환하는 함수를 작성한다. (lowerbound개념)
    - 해당 값들의 차이가 쇠막대기 사이에 존재하는 레이저의 개수이므로 위 코드와 동일한 방법으로 쇠막대기의 잘린 조각을 계산한다.
   
   

 - lowerbound 개념을 이용한 문제풀이 코드

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

public class Main {
    static class Pair {
        char sym;
        int index;

        public Pair(char sym, int index) {
            this.sym = sym;
            this.index = index;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<Integer> lazer = new ArrayList<>();
        Stack<int[]> stick = new Stack<>();

        String line = br.readLine();
        Stack<Pair> sym = new Stack<>();

        for (int j = 0; j < line.length(); j++) {
            char index = line.charAt(j);
            Pair curSym = new Pair(index, j);

            if (sym.isEmpty()) {
                sym.push(curSym);
            } else if (index == ')') {
                Pair compare = sym.pop();
                if (j - compare.index == 1) {
                    lazer.add(compare.index);
                } else {
                    stick.push(new int[]{compare.index, j});
                }
            } else {
                sym.push(new Pair(index, j));
            }
        }

        Collections.sort(lazer);

        int partStick = 0;
        while (!stick.isEmpty()) {
            int[] curr = stick.pop();
            int startIndex = curr[0];
            int endIndex = curr[1];

            partStick++;

            int start = lowerBound(lazer, startIndex);
            int end = lowerBound(lazer, endIndex);
            partStick += end - start;
        }
        System.out.println(partStick);

        br.close();
    }

    // lowerBound() 메소드 생성
    public static int lowerBound(List<Integer> arr, int target) {
        int start = 0;
        int end = arr.size();

    // 이진 탐색
        while (start < end) {
            int mid = (start + end) / 2;
            if (arr.get(mid) >= target) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }

        return start;
    }
}

 - lowerbound를 통해 수정된 코드의 시간복잡도
이 코드에서도 가장 시간이 많이 소요되는 부분은 쇠막대기마다 레이저의 개수를 세는 부분이다. 이 부분의 시간 복잡도는 O(S * log L)이고, 여기서 S는 막대기의 개수이다. 최악의 경우, S = N/2이므로, O(N * log N)이 될수 있다고 생각했다. 따라서 시간복잡도가 계산되었고, 시간초과가 발생하지 않을 수 있다고 생각했다.

최종 결론

백준 결과 제출 사진

최근 코딩 테스트를 준비하며 알고리즘에 대해서 공부하기 시작했고, 문제 해결 과정에서 최적화가 중요하다는 것을 깨달았다. 
그러다 이번 문제를 해결하며 기존에 배웠던 lowerBound와 같은 개념을 활용하여 코드를 최적화 할 수 있다는 것을 알게되었고, 이를 통해 효율적인 알고리즘을 생각하여 기존 코드에 활용할 수 있는 능력을 기르게 됐다.

아주 효율적인 코드

- 레이저 발견시 현재 존재하는 쇠막대기의 개수만큼 결과값에 추가하는 방식으로 동작하는 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        Stack<Character> stack = new Stack<>();
        int result = 0;

        for (int i = 0; i < input.length(); i++) {
            char current = input.charAt(i);

            if (current == '(') {
                stack.push(current);
            } else {
                stack.pop();

                // stack에는 현재 index까지 이어지는 쇠막대기의 개수만큼 쌓여있음.
                if (input.charAt(i - 1) == '(') {
                // input의 이전값이 '(' 이라면 레이저이므로 현재 존재하는 쇠막대기의 개수만큼 +
                    result += stack.size();
                } else {
                // 이외에는 쇠막대기 이므로 쇠막대기 조각 개수 1개 추
                    result++;
                }
            }
        }

        System.out.println(result);
    }
}