baekjoon 1662 압축 java

2개의 풀이가 있다.

1. 재귀로 푼 풀이

package 구현;


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

public class baekjoon_압축1662 {
    static boolean[] v;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine().trim();
        v = new boolean[input.toCharArray().length];
        System.out.println(solution(input, 0));
    }

    static int solution(String s,int index){
        int cnt = 0;
        char[] str = s.toCharArray();
        for(int i=index;i<str.length;i++){
            if(!v[i] && str[i] == '('){
                v[i] = true;
                int result = solution(s, i + 1);
                cnt = (cnt - 1) + (result * (str[i - 1] - '0'));
            }else if(!v[i] && str[i]==')'){
                v[i] = true;
                return cnt;
            }else if(!v[i]){
                v[i] = true;
                cnt++;
            }
        }

        return cnt;
    }

}

2. arraylist로 푼 풀이.

package 구현;

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

public class baekjoon_압축_다른풀이1662 {
    static boolean[] v;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String [] strings = br.readLine().split("");
        List<Integer>stack=new ArrayList<>();
        for(int i=0;i<strings.length;i++) {

        	
        	if(strings[i].equals("(")) {
        		stack.add(-1);
        	}else if(strings[i].equals(")")) {
        		int count=0;
        		while(true) {
        			int temp=stack.remove(stack.size()-1);
        			if(temp==-1) {
        				break;
        			}
        			count=count+temp;
        		}
        		stack.add(count*stack.remove(stack.size()-1));
        	}else if((i<strings.length-1)&&strings[i+1].equals("(")) {
        		stack.add(Integer.parseInt(strings[i]));
        	}else {
        		//그냥 숫자일경우
        		stack.add(1);
        	}
        }
        int answer=0;
        for(int s: stack) {
        	answer=answer+s;
        }
        System.out.println(answer);
        
    }
}

참고코드:
https://developerbee.tistory.com/74

이런문제는 참 생각하는데 시간이 많이 걸리는거같은데,,

많이 풀면 익숙해질 것 같아서 그래도 희망적이다.