6697. 이현이의 괄호 문자열 (D5)

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWdXrXraFloDFAWn&categoryId=AWdXrXraFloDFAWn&categoryType=CODE

< 입력 >

A ( 원하는 이동 횟수 ) [ 1 <= A <= 10^9 ]

< 출력 >

A번 올바른 문자열을 만들 수 있고 조건을 만족하는 문자열

< 풀이 >

문제가 이해가 안돼서 테스트케이스를 보고 분석을 했다.

)( 는 1번만에 ()라는 올바른 문자열을 만들 수 있다.

)())((는 4번만에 ()()()라는 올바른 문자열을 만들 수 있다.

문제 설명에서 문자열 T가 올바른 문자열이면 ( T ) 도 올바른 문자열이다. 라고 되어있지만

1) )))(((을 ()()()로 만드는 데는 3+2+1 = 6 번이 필요하다.

2) )))(((을 ((()))로 만드는 데는 3+3+3 = 9 번이 필요하다.

즉, )))(((는 6번만에 올바른 문자열로 만들 수 있기 때문에 9라는 입력에 이 문자열을 준다면

인접해 있는 두 문자의 위치를 바꾸는 작업을 B(0 <= B < A)번 해서는 이 문자열을 올바른 괄호 문자열로 만들 수 있는 방법이 없어야한다. 라는 조건에 위배된다.

따라서 1)과 같은 형태를 따르는 것이 정답임을 알 수 있다.

1)을 설명할 때 간단하게 언급되어 있지만 )))((( 을 올바른 문자열로 바꾸기 위해서는 3+2+1=6번의 이동이 필요하다.

괄호 개수에 따라 등차수열의 형태를 띄는 것이다.

이제 문제를 해결할 수 있는 힌트는 모두 주어졌다.

먼저, 1부터 n까지의 합이 입력받은 A(ex : 5)보다 크거나 같은 n(ex : 3)을 찾는다.

그렇다면 우리는 n을 통해 )))(((라는 문자열을 만들 수 있다.

이제 n과 A의 차이를 구한다. (n-A=1)

)))(((을 올바른 문자열로 만드는 과정은 아래와 같다.

) ) ) ( ( ( -> ) ) ( ) ( ( -> ) ( ) ) ( ( -> ( ) ) ) ( ( -> ( ) ) ( ) ( -> ( ) ( ) ) ( -> ( )( )( )

     0               1               2               3             4               5              6

위와 같은 과정을 거쳐서 총 6번만에 올바른 문자열이 만들어지는 것이다.

하지만 우리에게 주어진 횟수는 5번(A)이다. 즉, 5번만에 6의 형태를 만들어야 한다.

그러므로 0이 아닌 1(n-A)을 출력하면 A번만에 수행할 수 있게 된다.

" 너 이만큼 횟수 부족하지? 그럼 내가 이만큼 먼저 해줄게. " 와 같은 개념이다.

※ 이 문제에서는 테스트케이스가 83개이지만 테스트케이스가 많을 때를 생각해서 등차수열의 합을 미리 배열에 넣어놨다.

A의 범위가 10^9보다 작거나 같으므로 약 44,721까지 더하면 A의 범위를 모두 포함할 수 있다.

---

- 소스 코드 -

#include<iostream>
 
using namespace std;
 
typedef long long ll;
 
int main()
{
    int test_case;
    int a = 0;
    int arr[44724] = { 0 };
    int index = 0;
    while (index <= 44723) {
        a += index;
        arr[index] = a;
        index++;
    }
    // 등차수열 값 미리 계산해놓기 !!
    int T;
 
    cin >> T;
 
    for (int test_case = 1; test_case <= T; test_case++) {
        cin >> a;
        int last = 44724;
 
        for (int i = 0; i <= last; i++) {
            if (a <= arr[i]) {
                last = i;
                break;
            }
        }
        // A보다 크거나 같은 n 찾기
        int term = arr[last] - a;
        // 1부터 n까지 등차수열의 합만큼 진행해야 결과를 얻을 수 있기 때문에
        // a와의 차이(term)만큼 먼저 진행을 해준다.
 
        printf("#%d ", test_case);
        for (int i = 0; i < last - term; i++) {
            printf(")");
        }
        printf("(");
        for (int i = last-term; i < last; i++) {
            printf(")");
        }
        // term만큼 먼저 진행해서 첫 ( 를 왼쪽으로 옮겨준다.
        for (int i = 0; i < last - 1; i++) {
            printf("(");
        }
        // 나머지 ( 를 출력한다.
        printf("\n");
    }
}

---