[Baekjoon/Programmers] 10799 쇠막대기

10799 쇠막대기문제 해결 과정.

를 구현해보았는데

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static int splitBars(List<Integer> lasers, int st, int fn) {
        int laserNum = 0;
        for (int laser : lasers) {
            if ((laser>st) && (laser<fn)) laserNum += 1;
        }
        return laserNum+1;
    }

    public static void main(String[] args)  throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[] input = br.readLine().toCharArray();
        int MAX_LASER_NUM = input.length/2;
        List<Integer> lasers = new ArrayList<>(MAX_LASER_NUM);

        int totalBarNum = 0;

        StringBuilder bars = new StringBuilder();
        for (int i=0; i < input.length - 1; i++) {  // laser와 bar 분리
            if ((input[i] == '(') && (input[i + 1] == ')')) {
                input[i] = ' ';
                input[i + 1] = ' ';
                lasers.add(i + 1);
            }
            bars.append(input[i]);
            if (i == input.length-2) bars.append(input[i+1]);
        }

        while(!bars.toString().isBlank()) {
            int barSt = -1;
            int barFn = -1;

            for(int i=0; i<bars.length(); i++) {
                if (bars.charAt(i)=='(') {
                    barSt = i;
                } else if ((bars.charAt(i)=='(') && (barSt != -1)) {
                    barSt = i;
                } else if ((bars.charAt(i) == ')') && (barSt !=-1)) {
                    barFn = i;
                    totalBarNum += splitBars(lasers, barSt, barFn);
                    bars.replace(barSt, barSt+1, " ");
                    bars.replace(barFn, barFn+1, " ");
                    barSt = -1;
                    barFn = -1;
                }
            }
        }
        System.out.println(totalBarNum);
    }
}

문제 해결은 되나 결과는 시간초과였다…

작성하면서도 반복문을 지나치게 많이 사용하고 있고 불필요한 부분이 많다고 느꼈고 특히 굳이 막대기들을 층별로 나눠야 할까?라는 의문이 들었는데 막대기와 레이저를 구분하기만 한다면 이 부분은 생략해도 된다는 걸 깨달았고 중첩된 for문 없이도 문제를 해결할 수 있다는 걸 알았다!

import java.io.*;

public class Main {

    public static void main(String[] args)  throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] input = br.readLine().toCharArray();

        StringBuilder bars = new StringBuilder();

        for (int i = 0; i < input.length - 1; i++) {  // laser와 bar 구분
            if ((input[i] == '(') && (input[i + 1] == ')')) {
                i++;
                input[i] = 'l';
            }
            bars.append(input[i]);
            if (i == input.length - 2) bars.append(input[i + 1]);
        }

        int barNum = 0;
        int totalBarNum = 0;

        for (int i = 0; i < bars.length(); i++) {
            if (bars.charAt(i) == '(') barNum++;
            else if (bars.charAt(i) == ')') {
                barNum--;
                totalBarNum++;
            } else {
                totalBarNum += barNum;
            }
        }
        System.out.println(totalBarNum);
    }
}

그리하여 다시 작성한 코드. 레이저와 bar를 구분하는 작업을 먼저 진행해주었고 laser의 경우 ‘()’를 ‘l’로 대체해 주었다. 설명과 변수명이 모호한 감이 있긴 하지만.. 어쨌든 해냈다~!

1등 코드를 보니 레이저와 막대기를 나누는 작업도 불필요했다…