백준 1662번, 1377번

문딤·2022년 8월 8일

1662 압축

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

소스코드

 
public class Main {
 
	public static void main(String[] args) throws IOException {
        
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine().trim();
        Stack<Integer> len = new Stack<>();
        Stack<Integer> mul = new Stack<>();

        int cnt=0;
        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            if(c=='('){
                cnt-=1;
                int mulNum = str.charAt(i-1)-'0';
                len.add(cnt);
                mul.add(mulNum);
               cnt=0;
            }
            else if(c==')'){
                int val = mul.peek();
                mul.pop();
                val*=cnt ;
                int valLen = len.peek();
                len.pop();
                cnt= valLen + val;
            }
            else  cnt++;     //숫자
        }
        System.out.print(cnt);
    }
}

재귀

  static Stack<Integer> len;
    static Stack<Integer> multi;
    static int [] paren =new int [50];
    static char[] s;

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

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

        String str= br.readLine();
        s= str.toCharArray();
        Stack<Integer> st = new Stack();

        for (int i = 0; i < s.length; i++) {
            if(s[i]=='(') st.push(i);
            if(s[i]==')')paren[st.pop()] = i;
        }
        System.out.println(recur(0,s.length));
    }
    static int recur(int start, int end){
        int len =0;
        for (int i = start; i < end; i++) {
            if(s[i]=='('){
                len +=(s[i-1]-'0')* recur(i+1,paren[i])-1;
                i=paren[i];
            }else{
                len++;
            }
        }
        return len;
    }
}

문제풀이

스택을 두개 만들어서 그냥 더해줄 문자열길이, 곱해줄 스택 두가지를 만들었다.
해서 '('일때 스택에 넣어주고, ')'일때 pop 시켜주면서 카운팅
재귀로도 가능하다.

참고

https://coder-in-war.tistory.com/entry/BOJ-JAVA1662-%EC%95%95%EC%B6%95

==========================================================================================================================

프로그래머스 가장 큰 수

https://school.programmers.co.kr/learn/courses/30/lessons/42746

문제 생각

    // 배열안의 값 중에서 비교할 수 있게 하고
    // 정렬시키고 제일 마지막애를 가져오면 되겠다.

소스코드


// 프로그래머스 가장 큰수
public class NumMain {
    public static void main(String[] args) {

        int [] numbers = {6,10,2};
       String [] str = new String[numbers.length];
        StringBuilder sb = new StringBuilder();
        String result ="";

        for (int i = 0; i < numbers.length; i++) {
            str[i] =String.valueOf(numbers[i]);
        }

        Arrays.sort(str, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2+o1).compareTo(o1+o2);
            }
        });

        if(str[0].equals("0")) {
            System.out.println(0);
        }
        for (String s: str
             ) {
            result+=s;
        }
        System.out.println(result);
    }

}

문제풀이

1.문자열을 더하고 정렬시키고 비교하려했으나, 생각처럼 잘 되지 않았다.
2.Arrays.sort 정렬시 compareTo해서 비교하는 방법으로 풀이 방법이 있었다.
3. 두수를 더한 값이 반대보다 클때 리턴

참고

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

==========================================================================================================================

1337 버블소트

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

소스코드

main



public class BOJ1377 {
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {


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


        Integer n= Integer.parseInt(br.readLine());
        Point [] arr =new Point[n+1];
        for (int i = 1; i <= n; i++) {
           int num = Integer.parseInt(br.readLine());
            arr[i] = new Point(num,i);
        }

        Arrays.sort(arr,1,n+1);

        int max= 0;
        for (int i = 1; i <=n ; i++) {
            max = Math.max(max,arr[i].idx -i);
        }

        System.out.println(max+1);

    }

}

갯수 비교

class Point implements Comparable<Point>{
    int num;
    int idx;
    Point(int num, int idx){
        this.num = num;
        this.idx =idx;
    }

    @Override
    public int compareTo(Point o) {
        return num-o.num;
    }
}