문제 링크
1023번: 괄호 문자열
괄호 문자열은 다음과 같이 정의한다. 1. 빈 무자열은 괄호 문자열이다. 2. S가 괄호 문자열일 때, (S)도 괄호 문자열이다. 3. S와 T가 괄호 문자열이라면, ST도 괄호 문..
www.acmicpc.net
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
접근 방법
이 문제에 핵심
1. 괄호 문자열에 정의는 문제 설명과 동일하며, 빈 문자열도 괄호 문자열입니다.
2. 괄호 문자열은 ()의 형태로 열림 '(' 과 닫힘 ')'이 매칭되어야 합니다.
3. ㄴㄴ괄호 문자열은 괄호 문자열이 아닌 '(', ')'으로 구성된 문자열입니다.
4. 괄호 문자열은 사전순으로 정렬되며, 0번째부터 시작합니다.
5. N개의 길이를 가지는 괄호 문자열에 대해서 K번째 ㄴㄴ괄호 문자열을 결과로 출력합니다.
6. K번째 ㄴㄴ괄호 문자열이 존재하지 않으면 -1을 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. 점화식을 통해 '('와 남은 문자열 길이에 따라 ㄴㄴ괄호문자열에 대한 개수를 구해서, 조합을 통해서 K번째 ㄴㄴ괄호 문자열을 탐색합니다.
3. 탐색을 통해 얻은 ㄴㄴ괄호 문자열을 결과로 출력합니다.
ㄴㄴ괄호 문자열(다이나믹 프로그래밍)
먼저, 만들어야 하는 문자열의 길이가 짝수일 때와 홀수 일 때로 구분됩니다.
[홀수]
문자열의 길이가 홀수이면, 괄호 문자열을 만들 수 없습니다.
→ '(' 개수와 ')' 개수를 매칭시킬 수 없기 때문입니다.
[짝수]
문자열의 길이가 짝수이면, 괄호 문자열을 만들 수 있습니다.
→ 만들 수 있는 괄호 문자열 개수 - '('와 ')'을 매칭시키는 괄호 문자열의 개수 : ㄴㄴ괄호 문자열 개수
ㄴㄴ괄호 문자열 개수 구하기
ㄴㄴ괄호 문자열은 DP(다이나믹 프로그래밍)을 통해서 구현할 것입니다.
먼저, 길이가 N일 때 만들 수 있는 문자열의 개수를 살펴보면
N : 2 → ((, (), )(, (( : 4개
N : 3 → (((, ((), ()(, ()), )((, )(), ))(, ))) : 8개
각 문자열에서 '(', ')' 2개의 문자를 선택하기 때문에 만들 수 있는 문자열의 개수에 대한 점화식
만들 수 있는 문자열의 개수 = 2ⁿ
전체 문자열의 개수를 구하였다면 ㄴㄴ괄호 문자열에 대해서 접근해보자.
N(문자열의 길이)이 4일 때
((((, (((), (()(, (()) .... : 2⁴(16)개의 만들 수 있는 문자열이 존재합니다.
다음에 설명할 예정이지만, ㄴㄴ괄호 문자열 개수를 통해서 '(', ')'을 사용할 것인지 결정할 것입니다.
'('_ _ _ 일 상태일 때 ㄴㄴ괄호 문자열의 개수
'(' '(' _ _ 일 상태일 때 ㄴㄴ괄호 문자열의 개수
위처럼 문자열 앞에 상태에 따라 ㄴㄴ괄호 문자열의 개수를 통해서 '(', ')'을 선택하는 것을 결정할 것입니다.
DP[i][j]으로 점화식을 통해서 먼저 ㄴㄴ괄호 문자열의 개수를 구한 뒤 '(', ')'을 선택할 것입니다.
i : '('의 개수
j : 남은 문자열의 길이
ex.
'(' _ : 1개{ ) } , DP[1][1]
'(('_ : 2개{ (, ) }, DP[2][1]
'(('_ _ : 3개{ ((, (), )( }, DP[2][2]
2차원 배열로 표현하면
| 1 | 2 | 3 | 4 | |
| 0 | 2 | 3 | 8 | 14 |
| 1 | 1 | 4 | 6 | 0 |
| 2 | 2 | 3 | 0 | 0 |
| 3 | 2 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
점화식으로 표현하면
( i > 0 AND j > 1)일 때
DP[i][j] = DP[i-1][j-1] + DP[i+1][j-1]
→ DP[i-1][j-1]은 ')'가 앞에 올 때, DP[i+1][j-1]은 '('가 앞에 올 때에 ㄴㄴ괄호 문자열의 개수이므로, 두 값을 더해줍니다.
DP[3][4] = DP[2][3] + DP[4][3]
'((('_ _ _ _ 상태입니다.
→'((('_ _ _ _ : _ 곳에 올 수 있는 문자열은 '(', ')'이며, 각각 문자열이 올 때 ㄴㄴ괄호 문자열의 개수를 미리 점화식을 통해 메모이제이션하였기 때문에 이용할 수 있습니다.
DP[2][3] : '((()'_ _ _ 의 ㄴㄴ괄호 문자열 개수
DP[4][3] : '(((('_ _ _의 ㄴㄴ괄호 문자열 개수
DP[2][3], DP[4][3]은 이미 ㄴㄴ괄호 문자열의 개수를 계산하였기 때문에 점화식을 통해 메모이제이션한 값을 이용해서 ㄴㄴ괄호 문자열의 개수를 구할 수 있는 것입니다.
( i = 0 AND j > 1)일 때
DP[0][j] = j-1길이이 만들 수 있는 문자열 개수 + DP[i+1][j-1]
→ i = 0인 것은 '('가 매칭되는 것이 앞서 존재하지 않습니다.
→ '()'_ _ : _ 곳에 올 수 있는 문자열은 '(', ')'이며, '('이 오면 기존에 있던 메모이제이션을 사용하고, ')'이 오면 항상 ㄴㄴ괄호 문자열이기 때문에 j-1 길이로 만들 수 있는 문자열의 개수를 더해줍니다.
DP[0][2] : 1길이로 만들 수 있는 문자열 개수 + DP[1][1]
DP[1][1] : '()(' _ 의 ㄴㄴ괄호 문자열 개수
1길이로 만들 수 있는 문자열 개수 : ')'_의 ㄴㄴ괄호 문자열 개수 2¹
j = 0일 때
DP[0][0]은 빈 문자열이고, 빈 문자열은 괄호 문자열이기 때문에 0이 됩니다.
또한, DP[1][0], DP[2][0]은 모두 '(' 개수가 많은 문자열이므로 해당 문자열은 ㄴㄴ괄호 문자열로써 값이 1이 됩니다.
✭ '(' 개수가 음수가 되면 '(' 보다 ')'이 많이 있다는 뜻으로, 더 이상 괄호 문자열을 만들 수 없기 때문에 모든 조합이 ㄴㄴ괄호 문자열이 됩니다.
즉, 점화식들을 기반으로 2차원 배열에 DP[i][j]을 메모이제이션을 진행합니다.
K번째 ㄴㄴ괄호 문자열 만들기(조합)
K번째 ㄴㄴ괄호 문자열을 구할 때에는 2가지를 기준으로 조합을 만들 수 있습니다.
1. '('가 와야 할 때
K가 '('을 사용할 때 조합의 개수보다 작거나 같을 때입니다.
→ '('을 사용했을 때 K번째 ㄴㄴ괄호 문자열이 존재한다는 것입니다.
'('_ _ _ 일 때 K가 5번째를 찾고 있다면, '('_ _ _(DP[1][3])의 ㄴㄴ괄호 문자열 개수의 값이 5보다 크면 해당 조합 중 K번째 ㄴㄴ괄호 문자열이 존재합니다.
[점화식]
DP[i][j] ≥ K 만족하면
'('을 사용합니다.
2. ')'가 와야 할 때
K가 '('을 사용할 때 조합의 개수보다 클 때입니다.
→ '('을 사용했을 때 K번째 ㄴㄴ괄호 문자열이 존재하지 않는다는 것입니다.
'('_ _ _ 일 때 K가 12번째를 찾고 있다면, '('_ _ _(DP[1][3])의 ㄴㄴ괄호 문자열 개수의 값이 12보다 작으면 해당 조합 중 K번째 ㄴㄴ괄호 문자열이 존재하지 않습니다.
왜냐하면 괄호 문자열은 사전순으로 정렬되기 때문에, '('_ _ _ 모든 조합보다 K가 큰 값이므로 ')'가 사용한다는 것은 '('을 사용한 조합을 모두 지나왔다는 뜻입니다.
[점화식]
DP[i][j] < K 만족하면
')'을 사용합니다.
또한, '('의 조합의 개수를 지나왔기 때문에 { K - '('을 사용했을 때 조합의 개수 }을 진행해야 합니다.
※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.
예제입력 2.
1. 입력된 정보를 저장합니다.
N : 4 + 1
※ ㄴㄴ괄호 문자열은 0번째부터 시작하기 때문에 실제로보면 5번째 ㄴㄴ괄호 문자열이기 때문에 +1을 진행하였습니다.
K : 4
2. 점화식을 통해 '('와 남은 문자열 길이에 따라 ㄴㄴ괄호문자열에 대한 개수를 구해서, 조합을 통해서 K번째 ㄴㄴ괄호 문자열을 탐색합니다.
각 문자열 길이에 따른 조합의 개수
| 길이 | 0 | 1 | 2 | 3 | 4 |
| 개수 | 1 | 2 | 4 | 8 | 16 |
DP[][] 점화식을 통한 메모이제이션 진행
| 0 | 1 | 2 | 3 | 4 | |
| 0 | 0 | 2 | 3 | 8 | 14 |
| 1 | 1 | 1 | 4 | 6 | X |
| 2 | 1 | 2 | 3 | X | X |
| 3 | 1 | 2 | X | X | X |
| 4 | 1 | X | X | X | X |
✭ DP[4][1], DP[3][3] 같은 곳을 X로 표현한 것은 최소 6글자이기 때문에 N보다 커져서 조건에 만족하는 문자열을 만들 수 없기 때문입니다.
[j = 0일 때 ]
DP[0][0] = 0
DP[1][0] = 1
DP[2][0] = 1
[( i > 0 AND j > 1)일 때]
DP[2][2] = DP[1][1] + DP[3][1] = 3
[( i = 0 AND j > 1)일 때]
DP[0][2] = DP[1][1] + 문자열 길이 1일 때 조합의 개수(2) = 3
K번째 ㄴㄴ괄호 문자열 탐색
우선 K번째 문자열이 존재하는지 확인합니다.
문자열의 길이가 짝수이기 때문에, 괄호 문자열이 존재합니다.
길이가 N일 때 ㄴㄴ괄호 문자열의 총 개수 : DP[0][4] = 14개 입니다.
K < DP[0][4]을 만족하기 때문에 5번째 ㄴㄴ괄호 문자열은 존재합니다.
괄호 조합하기 진행.
_ _ _ _
'('일 때 조합의 개수(DP[1][3], 6) ≥ K(5)
→ '('을 사용하는 조합에 포함되어있기 때문에 '('을 사용합니다.
'('_ _ _
'('일 때 조합의 개수(DP[2][2], 3) < K(5)
→ ')'을 사용하는 조합에 포함되지 않기 때문에 ')'을 사용하며, '('을 썻을 때 조합을 지나왔기 때문에 K - DP[2][2](3)을 진행합니다.
K(5) - DP[2][2](3) = 2
'()'_ _
'('일 때 조합의 개수(DP[1][1], 1) < K(2)
→ ')'을 사용하는 조합에 포함되지 않기 때문에 ')'을 사용하며, '('을 썻을 때 조합을 지나왔기 때문에 K - DP[1][1](1)을 진행합니다.
K(2) - DP[1][1](1) = 1
'())'_
'('일 때 조합의 개수(DP[1][0], 1) ≥ K(1)
→ '('을 사용하는 조합에 포함되어있기 때문에 '('을 사용합니다.
K번째 문자열 완성
())(
3. 탐색을 통해 얻은 ㄴㄴ괄호 문자열을 결과로 출력합니다.
5(4+1)번째 문자열 : '())('
'())(' 결과로 출력합니다.
- BufferedReader를 사용하여 입력되는 정보를 저장합니다.
- StringTokenizer을 통해서 N, K의 값을 띄어쓰기 기준 나누었습니다.
- 문자열에 따른 조합 개수를 점화식을 통해 배열에 저장합니다.
- ㄴㄴ괄호 문자열의 개수를 점화식을 통해 DP[][]을 저장합니다.
- 만약, 만들 수 있는 ㄴㄴ괄호 문자열보다 K가 크다면 -1을 BufferedWriter 저장합니다.
- '(', ')'을 사용하는 조건에 따라 K번째 문자열을 탐색합니다.
- 탐색을 통해 얻은 K번째 ㄴㄴ괄호 문자열을 Bufferedwriter 저장합니다.
- BufferedWriter에 저장된 결과를 출력합니다.
결과코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int N = Integer.parseInt(st.nextToken());
long K = Long.parseLong(st.nextToken()) + 1;
//길이가 N개일 때 '(', ')'만 사용하여 만들 수 있는 문자열 개수
long[] combinationCnt = new long[N+1];
//ㄴㄴ괄호 문자열에 대한 조합 DP[i][j]
long[][] DP = new long[N+1][N+1];
combinationCnt[0] = 1;
//문자열 개수 및 DP[i][0]값 초기화
for(int i=1;i<=N;i++){
combinationCnt[i] = combinationCnt[i-1] * 2;
DP[i][0] = 1;
}
//점화식을 이용한 DP[i][j] 메모이제이션 진행
for(int i=1;i<=N;i++) {
DP[0][i] = DP[1][i - 1] + combinationCnt[i - 1];
for (int j = 1; j <= N - i; j++) {
DP[j][i] = DP[j - 1][i - 1] + DP[j + 1][i - 1];
}
}
//ㄴㄴ괄호 문자열 총 개수보다 K가 클 때, -> K번째 문자열을 만들지 못할 때
if((N % 2 == 1 && K > combinationCnt[N]) || (N % 2 == 0 && K > DP[0][N])){
bw.write("-1");
}else{
StringBuilder sb = new StringBuilder();
//현재 '(', ')'을 삽입한 개수
int len = 0;
//'('의 개수
int leftCnt = 0;
//만약 문자열의 개수가 홀수이면, 모든 조합의 개수는 ㄴㄴ괄호 문자열입니다.
boolean flag = N % 2 == 1;
//'(', ')' 조합 진행
while(len < N){
//더 이상 괄호 문자열이 존재하지 않을 때
if(flag){
//')'을 사용할 때
if(K > combinationCnt[N-len-1]){
sb.append(")");
K -= combinationCnt[N-len-1];
}else{ //'('을 사용할 때
sb.append("(");
}
}else{ //괄호 문자열이 존재할 때
//')'을 사용할 때
if(K > DP[leftCnt+1][N-len-1]){
sb.append(")");
K -= DP[leftCnt+1][N-len-1];
leftCnt--; //')'을 사용하기 때문에 '('의 개수가 줄어듭니다.
}else{ //'('을 사용할 때
sb.append("(");
leftCnt++; //'('을 사용하기 때문에 '('의 개수가 증가합니다.
}
}
//')'의 개수가 '('보다 커지면 더 이상 괄호 문자열을 만들 수 없습니다.
if(!flag && leftCnt < 0 ){
flag = true;
}
//문자 선택한 길이
len++;
}
//k번째 문자열 BufferedWriter 저장
bw.write(sb.toString());
}
bw.flush(); //결과 출력
bw.close();
br.close();
}
}'백준' 카테고리의 다른 글
| [백준, Java] 2011번, 암호 코드, (DP) (0) | 2024.05.31 |
|---|---|
| [백준, Java] 19590번, 비드맨, (그리디) (0) | 2024.05.26 |
| [백준, Java] 14939번, 불 끄기, (완전 탐색, 그리드) (0) | 2024.05.11 |
| [백준, Java] 21818번, Do You Know Your ABCs?, (완전 탐색) (0) | 2024.05.06 |
| [백준, Java] 17240번, Team Selection, (그리드) (0) | 2024.05.06 |
댓글