[항해99][선택 온보딩-7] 7?일차 문제풀이

 

연휴동안 코육대 하느라 문제를 못풀었다 얼른얼른..

 

백준 11050 이항계수 java https://www.acmicpc.net/problem/11050

11050번: 이항 계수 1

그냥 nCr을 계산하려고하면 팩토리얼을 써야해서 멋지지않다. (당연히 예전엔 팩토리얼로 푸는데 n시간, 팩토리얼을 쓰지 않는 풀이를 이해하기위해 r시간 정도 썼었다.)

 

고등학교 확률과통계 이항계수의 성질 중 파스칼의 삼각형을 활용하면 쉽게 풀 수 있다.

$_nC_r = \ \ {n-1}C{r-1} + \ {n-1}C{r}$ 공식을 활용하기 위해 2차원 배열을 이용한다.

static void input() throws Exception {
    int N = scan.nextInt();
    int K = scan.nextInt();
    //
    int[][] C = new int[N+1][N+1];
    C[1][0] = 1;
    C[1][1] = 1;
    for(int i  = 1; i <=N; i++){
        C[i][i] = 1;
        C[i][0] = 1;
    }
    for(int n = 2; n <=N; n++){
        for(int r = 1; r <n; r++){
            C[n][r] = C[n-1][r-1] +C[n-1][r];
        }
    }
    System.out.println(C[N][K]);
}

$_nC_r$ 을 C[n][r] 로 풀 수 있는게 이중 포문 안에 들어있는 코드를 보면 아름답기까지 함

---

백준 1541 잃어버린 괄호 java https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

간명한 풀이는 아니지만 오랜만에 정규식을 사용하고싶었다.

정규식을 버벅거리지 않고 사용하기위해서 기억해놔야겠음

 

정규식 활용하기!

1. java.util.regex.* 임포트
2. 적절한 정규식 정의
3. 정규식을 컴파일한 패턴 정의
4. 패턴에 검사할 문자열을 넣은 Matcher 클래스의 인스턴스 생성
5. while matcher.find → matcher.group으로 검사된 문자열 꺼내 쓰기

문제에 대한 아이디어는 주석에 자세히 적혀있다.

import java.util.regex.*;
static void input() throws Exception {
    // 괄호를 왜 잃어버렸지? ㅋㅋㅋ

    // 숫자들을 다 빼내서 연산자들의 순서를 바꿔보기에는, 괄호를 생성하는 작업이라서
    // 인접한 숫자끼리만 연산을 할 수 있다.
    // 인간의 풀이로 한다면 +기호가 -기호 뒤에있다면 미리 다 더해서 -뒤에 올 숫자를 크게 만들어주면 될텐데..
    // +밖에 없거나 - 밖에 없으면 그냥 연산
    // -뒤에 +가 없는 경우도 그냥 연산
    // -뒤에 +가 있다면 -로 치환
    // -뒤에 +, -가 반복되더라도 어떤 +가 -로 치환 가능한지만 생각하면된다.

    String s = scan.nextLine();
    // (연속된 어떤 숫자) 혹은 (+- 기호중 한개) 가 나오는 경우 split 하는 정규식
    // 1. 정규식 규칙 정의
    String regex = "\\\\d+|[+-]";
    // 2. 패턴 컴파일
    Pattern pattern = Pattern.compile(regex);
    // 3. matcher
    Matcher matcher = pattern.matcher(s);

    boolean minusFlag = false;
    int answer = 0;
    
    
    // 홀수 인덱스가 기호겠지만 -30 + 40 이라는 문제에도 대응할 수 있도록, 
    // 해당 문제의 조건과는 관련 없이 문자인지 숫자인지 검사하여 행동하도록 구현
    while(matcher.find()){
        String element = matcher.group();
        if(element.matches("\\\\d+")){
            // 숫자인경우
            if(minusFlag) // 이전에 한번이라도 -기호가 나온 적이 있다면
                answer -= Integer.parseInt(element);
            else // 한번도 - 기호가 나온 적이 없다면
                answer += Integer.parseInt(element);
        }
        else{
            if(element.equals("-"))
                minusFlag = true;
        }
    }

    System.out.println(answer);
}