[백준-35289] 괄호 문자열 카드

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

 

문제

A	B	C	D	E	F
(	((	)	))	()	)(

 

여섯 종류의 괄호 문자열로 이루어진 카드를 임의의 순서로 나열해 만들 수 있는 올바른 괄호 문자열의 최대 길이 구하기(모든 카드를 사용할 필요 X)

단, 카드는 뒤집거나 회전할 수 없고, 카드에 적힌 문자열을 분리해 사용할 수 없음

 

풀이 방식

처음에 괄호 문자열이어서 스택 자료구조를 이용하는 방식을 고민함. 스택을 이용해서 푸는 방법의 아이디어가 떠오르지 않아 조건 분기를 이용해 문제를 접근함.

 

• E 괄호 문자열인 ()는 단독으로 사용해도 올바른 문자열이므로 별도로 세어줌
• F 괄호 문자열인 )(는 위치가 가운데에 배치되어야 함(ex: AFC, BFC, BFFFFC 등). 가장 긴 올바른 괄호 문자열을 만들 수 있는 것부터 접근
  • B+F길이+D → (( )()(...)( ))
  • A+F길이+C → ( )()(...)( )
  • B+F길이+CC → (( )()(...)( ))
  • AA+F길이+D → (( )()(...)( ))
• B 괄호 문자열 ((는 닫힌 괄호가 나와주어야 함(ex: BD, BCC 등)
  • B+D → (( ... ))
    여기서 B와 D 중 개수가 더 적은 것을 기준으로 올바른 괄호 문자열 생성
  • 만약 B>D인 경우, 남는 B는 C와 올바른 괄호 문자열 만들 수 있음 고려 B+CC → (( ... ))
    이 부분도 B와 CC 중 개수가 더 적은 것을 기준으로 올바른 괄호 문자열 생성
• D 괄호 문자열 ))는 A 괄호가 2개 이상인 경우랑 매칭될 수 있음
  • AA+D → (( ... ))
• 남은 A 괄호 문자열은 남은 C로 올바른 괄호 문자열 만들 수 있음
  • A+C → (( ... ))

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

// A: (, B: ((, C: ), D: )), E: (), F: )(
let [A, B, C, D, E, F] = input[0].split(' ').map(Number);

let answer = 0;
// E는 항상 올바른 괄호 문자열임
if (E > 0) {
    answer += E * 2;
    E = 0;
}
// F가 존재할 때
if (F > 0) {
    // (()()()()(...)())
    if (B > 0 && D > 0) {
        answer += F * 2 + 4;
        B--;
        D--;
    }
    // ()(...)()
    else if (A > 0 && C > 0) {
        answer += F * 2 + 2;
        A--;
        C--;
    }
    // (()(...)())
    else if (A >= 2 && D > 0) {
        answer += F * 2 + 4;
        A -= 2;
        D--;
    }
    // (()(...)())
    else if (B > 0 && C >= 2) {
        answer += F * 2 + 4;
        B--;
        C -= 2;
    }
}

// B가 존재할 때
if (B > 0) {
    if (D > 0) {
        const min = Math.min(B, D);
        answer += min * 2 * 2;
        B -= min;
        D -= min;
    }
    if (B > 0 && C >= 2) {
        const min = Math.min(B, Math.floor(C / 2));
        answer += min * 2 * 2;
        B -= min;
        C -= 2 * min;
    }
}

// D가 존재할 때
if (D > 0) {
    if (A >= 2) {
        const min = Math.min(D, Math.floor(A / 2));
        answer += min * 2 * 2;
        A -= 2 * min;
    }
}

// A가 존재할 때
if (A > 0) {
    if (C > 0) {
        const min = Math.min(A, C);
        answer += min * 2;
    }
}

console.log(answer);