백준 10799 - 자료구조

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int cnt = 0; // 나눠진 개수
        int line = 0; // 막대기 수
        String s = br.readLine();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(') line++;
            else{
                line--;
                //레이저
                if(s.charAt(i-1) == '(') cnt += line;
                //선 끝남
                else cnt += 1;
            }
        }
        System.out.println(cnt);
    }
}

풀이과정 및 리뷰

1. Map<Integer,String> → `R: 레이저, S: 막대 시작 E: 막대 끝

• 현재 괄호가 ) 이고 직전 괄호가 ( 라면 map.put(idx,"R") map.put(idx-1,"R")
• 현재 괄호가 ) 이고 직전 괄호가 ( 가 아니라면 map.put(idx,”E”)
• 현재 괄호가 ( 라면 map.put(idx,"S")
• map.get(idx).equals("S) 라면, R을 만날 때마다 cnt++, C를 만나면 cnt 리턴하는 방식으로 풀이

→ 너무 복잡하고, cnt를 구하는 과정에서 막힘

1. stack<Character>

• 현재 괄호가 ( 라면 push
• 현재 괄호가 ) 이며 & 직전이 ( 라면 pop

→ 레이저와 막대기 구분 안됨, cnt 계산이 각각 이뤄져야 해서 복잡하다고 생각함

1. 자료구조 없이 cnt(조각 수) + line(막대 수) 사용

→ 막대기 수 line과 조각 수 cnt 를 선언 후 문자열 길이만큼 루프 반복하며

현재 괄호가 ( 라면 line++ , 괄호가 ) 라면 일단 line-- 후,

• 레이저인 경우(s.charAt(i-1) == ')' → line을 취소하는 느낌)와
• 막대 끝인 경우( else → line이 끝났으므로 줄여주는 느낌)로 나누어 cnt 계산

레이저인 경우 : 조각 수 cnt 를 막대 수만큼 ++ (⇒ 한번에 여러 막대기의 조각 개수 계산 가능)

막대 끝인 경우: 남은 조각 수를 더해줌 cnt += 1 (⇒ 짜투리 더해주기)