이번 글에서는 백준 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;
public class Main {
public static BigInteger factorial(int n) {
BigInteger result = BigInteger.ONE;
for (int i = 2; i <= n; i++) {
result = result.multiply(BigInteger.valueOf(i));
}
return result;
}
public static void main(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.*;
public class Main {
public static void main(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;
public class Main {
public static void main(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);
}
}
이번 글에서는 백준 2346번 문제를 통해 queue 개념에 관해 좀 더 복잡한 문제를 풀어보자
문제 핵심
N : 풍선의 개수 ( 자연수 ) 1 ~ 1000
각 종이에 이동할 숫자가 적혀 있다. ( 0은 없다 )
적힌 종이 별로 양수면 오른쪽, 음수는 왼쪽으로 이동한다.
풀이 과정
다음 Deque를 통해 문제를 풀어 나가며, 인덱스를 기억해 두는 것이 핵심이다.
1. 풍선 번호와 종이 저장
1. 큐에 인덱스 값들을 저장한다.
2. move 정수 배열에 해당 종이를 저장한다.
Deque<Integer> indexQueue = new ArrayDeque<Integer>();
int[] move = new int[N];
for (int i = 0; i < N; i++) {
move[i] = Integer.parseInt(stringTokenizer.nextToken());
indexQueue.add(i);
}
2. 반복
첫 시작은 앞에서부터 시작하기 때문에 미리 처리 한다.
큐에서 꺼낸 값은 인덱스 값이고, 이 인덱스 값을 가지고 move 정수 배열에서 이동할 거리를 확인할 수 있다.
int removeIndex = indexQueue.removeFirst();
stringBuilder.append(removeIndex + 1).append(" ");
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());
}
그렇게 되면 구분자를 저장하는 StringTokenizer의 특성을 활용해 문자를 가져올 수 있다.
true로 설정하면 구분자도 Token에 포함된다.
stringTokenizer = new StringTokenizer(sentence,"([)]",true);
2. 괄호 문자 찾아 균형확인하기
1. 구분자에 포함된 토큰 중에 괄호를 찾는다.
2. (, [ 라면 스택에 넣는다
3 - 1. ], ) 라면 스택에서 꺼내 비교한다
3 - 2. 이 때, 동일한 모양의 괄호 즉, )일 때 ( 괄호가 나오지 않는다면 균형이 맞지 않는 문자열로 처리
while(stringTokenizer.hasMoreTokens()) {
String token = stringTokenizer.nextToken();
if (token.equals("(") || token.equals("[")) {
push(token);
}
else if (token.equals(")")) {
if (!pop().equals("(")) {
isPerfect = false;
break;
}
}
else if (token.equals("]")) {
if (!pop().equals("[")) {
isPerfect = false;
break;
}
}
}
3. 스택에 남아있는 값 확인
마지막으로 스택에 남아 있는 경우 즉, (() 와 같은 문자열이 들어온다면 ( 이 스택에 남아 균형이 맞지 않는다.
if (!delimStack.isEmpty()) isPerfect = false;
스택을 활용하여 푸는 문제로 괄호를 저장하고 저장한 값을 꺼내 올 때, 다양한 경우에 대비하여 반론이 없게 푸는 것이 중요하다. 이번 문제는 빠르게 풀 수도 있지만, charAt함수가 아닌 StringTokenizer를 사용하듯이 다양한 방법으로 풀어보는 것을 추천한다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
private static LinkedList<String> delimStack;
private static void push(String delim){
delimStack.addLast(delim);
}
private static String pop(){
return delimStack.isEmpty() ? " " : delimStack.removeLast();
}
public static void main(String[] args) throws IOException {
delimStack = new LinkedList<>();
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder stringBuilder = new StringBuilder();
boolean isPerfect;
StringTokenizer stringTokenizer;
while (true) {
isPerfect = true;
delimStack.clear();
String sentence = bufferedReader.readLine();
if(sentence.equals(".")) break;
stringTokenizer = new StringTokenizer(sentence,"([)]",true);
while(stringTokenizer.hasMoreTokens()) {
String token = stringTokenizer.nextToken();
if (token.equals("(") || token.equals("[")) {
push(token);
}
else if (token.equals(")")) {
if (!pop().equals("(")) {
isPerfect = false;
break;
}
}
else if (token.equals("]")) {
if (!pop().equals("[")) {
isPerfect = false;
break;
}
}
}
if (!delimStack.isEmpty()) isPerfect = false;
stringBuilder.append(isPerfect ? "yes\n" : "no\n");
}
System.out.println(stringBuilder);
}
}
