백준 문제 풀이 : 14659 한조 서열 정리, 1339 단어 수학

오늘 스터디에서 풀었던 문제입니다.

한조 서열 정리는 어떻게어떻게 스스로 했는데...단어 수학 문제는 3시간 고민하고도 도저히 안될 것 같아서 결국 저보다 똑똑하신 많은 다른 개발자님들의 힘을 빌렸습니다ㅠㅠ

 

1. 한조서열정리하고옴ㅋㅋㅋ

이 문제는 다르게 푸는 방법도 있겠지만 저는 최근에 공부하고 있는 DFS 로 풀어봤습니다.

자세한 설명은 주석 참고 부탁드립니다

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

14659번: 한조서열정리하고옴ㅋㅋ

package baekJoon;

import java.util.Scanner;

public class Quiz_14659 {
    static int[] arr;
    static int n;
    static int count = Integer.MIN_VALUE;

    // 재귀 함수 풀이
    static void peak(int num, int k, int kill) {

        // k 가 배열의 크기인 n 보다 크면 k 를 num+1 로 고정
        if(k>n) peak(num, num+1, 0);
        if(k == n){ // k 가 n 과 동일해지면 count 계산
            count = Math.max(count, kill);
        }else{
            if (arr[num] > arr[k]) {
                // 현재 arr[num] 의 값이 비교 대상 arr[k]보다 크다면
                // kill+1 한 후 비교대상 index 를 +1 하고 재귀 시작
                // 즉 arr[num] > arr[k] 인 경우 한조가 한명을 처치한 것

                //System.out.println(arr[num] + " : " + arr[k]);
                peak(num, k+1, kill+1);

            }else{
                // 만약 arr[num] 의 값이 arr[k] 보다 작다면
                // 더이상 처치할 수 없음으로 해당 arr[num] 값으로 재귀를 중지하고
                // 대신 num+1 해서 다시 재귀를 시작함
                // 이때 비교 대상이 되는 arr[k] 는 num+1이 num+1 의 다음 값인 num+2 가 됨
                // 동시에 kill 값은 초기화
                //System.out.println(arr[num] + " : " + arr[k]);
                count = Math.max(count, kill);
                peak(num+1, num+2, 0);
            }
        }
    }


    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        n = scan.nextInt(); // 산봉우리 수

        arr = new int[n]; // 산봉우리 배열

        for (int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
        }

        // 재귀 시작은 0번째 봉우리부터이고
        // 비교대상은 1번째 봉우리
        // 즉 arr[0] 과 arr[1] 부터 비교
        peak(0, 1, 0);
        System.out.println(count);


    }
}

 

2. 단어 수학

 이 문제는 개인적으로 정말 어려웠습니다.

사실 알고보면 정말 쉬운데, 심지어 코드도 간단하게 나오는데 왜 이렇게 힘든지ㅠㅠ

딱 입력받은 단어의 각 자리별로 10000, 1000 등 을 넣기는 했는데 거기서 막혔었어서 약 3시간을 해맸습니다

이번에 다시 느낀 건 알고리즘은 많이보고 많이 풀어야 한다는 것! 정말로 알고보니까 별것 없더라구요

역시나 자세한 내용은 주석하겠습니다!

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

1339번: 단어 수학

package baekJoon;

import java.util.*;

import java.io.*;

public class Quiz_1339 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 알파벳 단어 갯수 받기

        Integer[] alpha = new Integer[26]; // 알파벳 26개만크 배열 선언
        Arrays.fill(alpha, 0);

        for(int i=0; i<n; i++){
            char ch[] = br.readLine().toCharArray();

            for(int j=0; j<ch.length; j++){
                // ch[j] 로 단어중 하나의 알파벳만을 받아옴.
                // 그후 해당 알파벳의 자리에 해당 알파벳에 맞는 10의 배수를 넣어줌
                // ACD 인 경우 각 A = 100, C = 10, D = 1 이 들어감
                // 또한 자리로는 A 는 0번째, C 는 3번째, D 는 4번째 자리에 들어감
                // 이를 종합하면 아래와 같은 코드로 변환됨
                // 이때 += 인 이유는 단어가 여러개일때는 해당 알파벳이 10의 자리와 100의 자리 모두 올 수 있음으로
                // 이것을 계산해주기 위함
                alpha[ch[j] - 'A'] += (int)(Math.pow(10, ch.length - j - 1));
            }
        }

        // 정렬을 하는 이유는 시작하는 숫자가 9 부터 시작임으로
        // 결국 A 부터 alpha 의 값 중 가장 큰 숫자부터 넣어야 하기 때문
        Arrays.sort(alpha, Collections.reverseOrder());
        //System.out.println(Arrays.toString(alpha));

        int start = 9;
        int result = 0;

        for(int i=0; i<alpha.length; i++){
            // 알파벳 배열안에 값이 없으면 중단 => 필요하지 않은 단어임으로
            if(alpha[i] == 0){
                break;
            }
            result += alpha[i] * start;
            start--;
        }
        System.out.println(result);
    }
}