이번 글에서는 백준 110번 문제를 통해 이항계수를 활용하고 최대 값을 넘어서는 순간을 다루는 방법을 알아보자.
문제 핵심
서쪽 ( N )
동쪽 ( M )
N <= M
최대 한 개의 다리만 연결
풀이 과정
이 문제는 조합론으로 mCn이라고 할 수 있다.
다만 M의 최대값이 30일 때 factorial의 값은 다음과 같다.
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40,320
9! = 362,880
10! = 3,628,800
11! = 39,916,800
12! = 479,001,600
13! = 6,227,020,800
14! = 87,178,291,200
15! = 1,307,674,368,000
16! = 20,922,789,888,000
17! = 355,687,428,096,000
18! = 6,402,373,705,728,000
19! = 121,645,100,408,832,000
20! = 2,432,902,008,176,640,000
21! = 51,090,942,171,709,440,000
22! = 1,124,000,727,777,607,680,000
23! = 25,852,016,738,884,976,640,000
24! = 620,448,401,733,239,439,360,000
25! = 15,511,210,043,330,985,984,000,000
26! = 403,291,461,126,605,635,584,000,000
27! = 10,888,869,450,418,352,160,768,000,000
28! = 304,888,344,611,713,860,501,504,000,000
29! = 8,841,761,993,739,701,954,543,616,000,000
30! = 265,252,859,812,191,058,636,308,480,000,000
한계는 이미 초과했다.
이 때 우리는 각 프로그래밍언어에서 제공하는 클래스를 사용하면 된다.
Java에서는 BigInteger가 있다.
핵심 코드
이항 계수1 문제 처럼 나왔지만 이번에는 동쪽이 숫자가 항상 크다.
( 값을 받을 때 반대로 받았다. 헷갈리지 않게 N M으로 선언하는게 좋다. )
int T = Integer.parseInt(bufferedReader.readLine());
int N, K;
BigInteger result;
for (int i = 0; i < T; i++) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
K = Integer.parseInt(stringTokenizer.nextToken());
N = Integer.parseInt(stringTokenizer.nextToken());
result = factorial(N).divide(factorial(K).multiply(factorial(N - K)));
stringBuilder.append(result).append("\n");
}
이번 문제는 자료형의 최대값을 한참 넘어서기 때문에, 그 부분만 해결할 수 있다면 이전 이항계수 문제를 활용해 아주 쉽게 풀 수 있는 문제이다.
꼭 BigInteger같은 클래스를 사용하지 않더라도 비슷한 방식으로 직접 문자로 만들어서 처리하는 방법도 존재한다.
전체코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
publicclassMain{
publicstatic BigInteger factorial(int n){
BigInteger result = BigInteger.ONE;
for (int i = 2; i <= n; i++) {
result = result.multiply(BigInteger.valueOf(i));
}
return result;
}
publicstaticvoidmain(String[] args)throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer;
StringBuilder stringBuilder = new StringBuilder();
int T = Integer.parseInt(bufferedReader.readLine());
int N, K;
BigInteger result;
for (int i = 0; i < T; i++) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
K = Integer.parseInt(stringTokenizer.nextToken());
N = Integer.parseInt(stringTokenizer.nextToken());
result = factorial(N).divide(factorial(K).multiply(factorial(N - K)));
stringBuilder.append(result).append("\n");
}
System.out.println(stringBuilder);
}
}
이번 글에서는 큐, 스택에 마무리 문제인 24511번 문제를 해결해 보자. 시간 제한과 메모리 제한이 까다로울 것으로 예상된다.
문제 핵심
첫째 줄 - 자료구조의 수 : N
둘째 줄 - 수열의 종류 : 0 ( Queue ), 1 ( Stack )
셋째 줄 - 자료구조의 초기값 설정
넷째 줄 - 삽입할 수열의 길이 : M
다섯째 줄 - 삽입할 수열의 원소들
풀이 과정
첫 번째 예제의 과정 중 첫 번째 스텝을 다음과 같이 나타낼 수 있다.
그림 처럼 queue와 stack을 구현하여 값을 삽입하고 제거하는 과정으로 구현해보자.
아마 메모리에서 먼저 초과되지 않을까 싶다.
1. 자료구조 저장
0, 1과 구별 값에 따라 큐인지 스택인지 구별하여 저장한다.
List<Object> dataStructure = new ArrayList<Object>();
for (int i = 0; i < N; i++) {
int type = Integer.parseInt(stringTokenizer.nextToken());
if (type == 0) {
dataStructure.add(new LinkedList<Integer>());
} else {
dataStructure.add(new Stack<Integer>());
}
}
2. 초기 값 저장
세번 째 줄의 초기 값들을 저장한다.
이 때 초기값들은 instanceof를 통해 자료구조를 판별 후 맞는 메소드를 사용한다.
for (int i = 0; i < N; i++) {
int num = Integer.parseInt(stringTokenizer.nextToken());
if (dataStructure.get(i) instanceof Queue) {
((Queue<Integer>) dataStructure.get(i)).offer(num);
} else {
((Stack<Integer>) dataStructure.get(i)).add(num);
}
}
3. 메인 과정
새로운 값 들이 큐와 스택을 지나면서 반복되는 과정이다.
이 때, 사실 스택이 값을 거쳐가기만 하기 때문에 의미가 없다.
for (int i = 0; i < M; i++) {
int num = Integer.parseInt(stringTokenizer.nextToken());
int temp = num;
for (int j = 0; j < N; j++) {
if (dataStructure.get(j) instanceof Queue) {
((Queue<Integer>) dataStructure.get(j)).add(temp);
temp = ((Queue<Integer>) dataStructure.get(j)).remove();
}
}
stringBuilder.append(temp).append(" ");
}
결과는 시간 초과로 메모리 문제가 아닌 2 중 for문에 N과 M의 최악의 경우 (On2) 100,000 * 100,000 = 10,000,000,000 기 때문에 벌어진 일이다. 그렇다면 2 중 for문의 구조를 제거하고, 스택구조에서 값은 지나치기만 하기 때문에 경우에서 제거한다.
4. 자료구조의 재구성
그렇다면 큐의 구조일 때 값을 교체하는 과정이고, 그게 여러개라면 하나씩 밀려나는 과정이다.
큐 여러개가 하나의 값만 가지고 있기 때문에 여러개의 큐가 하나의 큐가 되어버린다.
( 즉, 다음과 같은 구조일 때 새로운 값이 들어온다면 하나의 큐처럼 행동한다. )
그렇다면 하나의 큐를 생성하고 큐일 경우에만 값을 추가한다.
Deque<String> queue = new ArrayDeque<>();
StringBuilder stringBuilder = new StringBuilder();
int N = Integer.parseInt(bufferedReader.readLine());
String[] dataStructureString = bufferedReader.readLine().split(" ");
String[] valueString = bufferedReader.readLine().split(" ");
for (int i = 0; i < N; i++) {
int type = Integer.parseInt(dataStructureString[i]);
if(type == 0){
queue.addLast(valueString[i]);
}
}
5. 메인 과정 재구성
다음과 같이 큐의 삽입과 삭제를 반복하면 O(n)의 경우의 수와 메모리 문제가 모두 해결된다.
int M = Integer.parseInt(bufferedReader.readLine());
String[] addValueString = bufferedReader.readLine().split(" ");
for (int i = 0; i < M; i++) {
queue.addFirst(addValueString[i]);
stringBuilder.append(queue.removeLast()).append(" ");
}
이번 문제는 마치 알고리즘이 큐처럼 행동하게 하여 해결할 수 있었다. 다음과 같이 자료구조의 개념을 이해한다면 여러방법으로 구현할 수 있다. 줄 서거나(큐), 박스에 물건을 넣고 빼거나(스택) 처럼 한 가지로 제한되지 않는다는 점이다.
시간과 메모리를 줄여야 한다는 점에서 이런 구조를 생각할 수 있었던 문제였다.
실패 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
publicclassMain{
publicstaticvoidmain(String[] args)throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
List<Object> dataStructure = new ArrayList<Object>();
StringTokenizer stringTokenizer;
StringBuilder stringBuilder = new StringBuilder();
int N = Integer.parseInt(bufferedReader.readLine());
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int i = 0; i < N; i++) {
int type = Integer.parseInt(stringTokenizer.nextToken());
if (type == 0) {
dataStructure.add(new LinkedList<Integer>());
} else {
dataStructure.add(new Stack<Integer>());
}
}
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int i = 0; i < N; i++) {
int num = Integer.parseInt(stringTokenizer.nextToken());
if (dataStructure.get(i) instanceof Queue) {
((Queue<Integer>) dataStructure.get(i)).offer(num);
} else {
((Stack<Integer>) dataStructure.get(i)).add(num);
}
}
int M = Integer.parseInt(bufferedReader.readLine());
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int i = 0; i < M; i++) {
int num = Integer.parseInt(stringTokenizer.nextToken());
int temp = num;
for (int j = 0; j < N; j++) {
if (dataStructure.get(j) instanceof Queue) {
((Queue<Integer>) dataStructure.get(j)).add(temp);
temp = ((Queue<Integer>) dataStructure.get(j)).remove();
}
}
stringBuilder.append(temp).append(" ");
}
System.out.println(stringBuilder);
}
}
성공 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
publicclassMain{
publicstaticvoidmain(String[] args)throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
Deque<String> queue = new ArrayDeque<>();
StringBuilder stringBuilder = new StringBuilder();
int N = Integer.parseInt(bufferedReader.readLine());
String[] dataStructureString = bufferedReader.readLine().split(" ");
String[] valueString = bufferedReader.readLine().split(" ");
for (int i = 0; i < N; i++) {
int type = Integer.parseInt(dataStructureString[i]);
if(type == 0){
queue.addLast(valueString[i]);
}
}
int M = Integer.parseInt(bufferedReader.readLine());
String[] addValueString = bufferedReader.readLine().split(" ");
for (int i = 0; i < M; i++) {
queue.addFirst(addValueString[i]);
stringBuilder.append(queue.removeLast()).append(" ");
}
System.out.println(stringBuilder);
}
}
Queue<Integer> queue = new LinkedList<Integer>();
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bufferedReader.readLine());
for(int i = 1;i <= N; i++){
queue.add(i);
}
2. 과정 반복
while (queue.size() > 1) {
queue.poll();
queue.add(queue.poll());
}
마지막으로 스택에 남아 있는 경우 즉, (() 와 같은 문자열이 들어온다면 ( 이 스택에 남아 균형이 맞지 않는다.
if (!delimStack.isEmpty()) isPerfect = false;
스택을 활용하여 푸는 문제로 괄호를 저장하고 저장한 값을 꺼내 올 때, 다양한 경우에 대비하여 반론이 없게 푸는 것이 중요하다. 이번 문제는 빠르게 풀 수도 있지만, charAt함수가 아닌 StringTokenizer를 사용하듯이 다양한 방법으로 풀어보는 것을 추천한다.
