URL 복사
카카오톡 공유하기원주율 외우기 알고리즘
May 09, 2018 조회수 138
문제
(주의: 이 문제는 TopCoder 의 번역 문제입니다.)
가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다.
이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다.
이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다.
이 때, 각 조각들의 난이도는 다음과 같이 정해집니다:
모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1
숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2
두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4
숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5
그 외의 경우 난이도: 10
원주율의 일부가 입력으로 주어질 때,
난이도의 합을 최소화하도록 숫자들을 3자리에서 5자리까지 끊어 읽고 싶습니다. 최소의 난이도를 계산하는 프로그램을 작성하세요.
<br/>
입력
12341234
11111222
12122222
22222222
12673939
208998628034825342117067982
14808651328230664709384460955058223172535940812848111
74502841027019385211055596446229489549303819644
288109756659334461284756482337867831652
<br/>
출력
4
2
5
2
14
60
99
95
77
<br/>
소스코드
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class PIAlgo {
static String input = "19577818577805321712268066130019278766111959092164201989380952572010654858632"; //INPUT
public static final String ID_CASE1 = "CASE001";
public static final String ID_CASE2 = "CASE002";
public static final String ID_CASE4 = "CASE004";
public static final String ID_CASE5 = "CASE005";
public static final String ID_CASENOT = "CASENOT";
static int[] numbers = null;
static boolean[] valid = null;
static List<Point> selected = new ArrayList<>();
static List<Point> completed = new ArrayList<>();
public static void main(String[] args) {
numbers = new int[input.length()];
valid = new boolean[input.length()];
// init
for (int i = 0; i < input.length(); i++) {
numbers[i] = Integer.parseInt(input.substring(i, i + 1));
valid[i] = false;
}
System.out.println("INPUT LENGTH : " + input.length());
// CASE SELECT
selectionCase1(numbers);
selectionCase2(numbers);
selectionCase4(numbers);
selectionCase5(numbers);
selectionCaseNot(numbers);
Collections.sort(selected, new XComparator()); //정렬
print(selected);
// CASE Mix
List<Point> ps = get(0);
for(int i=0; i< ps.size();i++) {
join(ps.get(i));
}
/* =========================================================*/
Collections.sort(completed, new ValueComparator()); //정렬
System.out.println("========================");
print(completed.get(0)); //최소 난이도, 정답
System.out.println("========================");
}
public static List<Point> get(int x) {
List<Point> ps = new ArrayList<>();
for(int i = 0; i < selected.size(); i++) {
if(selected.get(i).getX() == x) {
ps.add(selected.get(i));
}
}
return ps;
}
/* 재귀 */
public static void join(Point p) {
int y = p.getY();
Point newP = null;
List<Point> ps = get(y + 1);
Point pp = null;
if(p.getY() == numbers.length -1) {
p.setCaseId("COMPLETE");
completed.add(p);
return;
}
for(int i = 0; i < ps.size(); i++) {
pp = ps.get(i);
newP = new Point();
newP.setCaseId("JOIN " + "[ " + p.getX()+ " , " + p.getY() + " ]\t" + "[ " + pp.getX() + " , " + pp.getY() + " ]\t");
newP.setY(pp.getY());
newP.setValue(p.getValue() + pp.getValue());
join(newP);
}
}
public static void updateValid(int x) {
valid[x] = true;
}
/* CASE 1111 : 동일값 */
private static void selectionCase1(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
if (i + 1 < numbers.length && numbers[i] == numbers[i + 1]) {
if (i + 2 < numbers.length && numbers[i + 1] == numbers[i + 2]) {
updateValid(i);
selected.add(new Point(ID_CASE1, i, i + 2, 1));
if (i + 3 < numbers.length && numbers[i + 2] == numbers[i + 3]) {
updateValid(i);
selected.add(new Point(ID_CASE1, i, i + 3, 1));
if (i + 4 < numbers.length && numbers[i + 3] == numbers[i + 4]) {
updateValid(i);
selected.add(new Point(ID_CASE1, i, i + 4, 1));
}
}
}
}
}
}
/* CASE 1234 : 1증가*/
private static void selectionCase2(int[] numbers) {
int gap = 0;
for (int i = 0; i < numbers.length; i++) {
if (i + 1 < numbers.length) {
gap = numbers[i + 1] - numbers[i];
if (i + 2 < numbers.length && numbers[i + 2] - numbers[i + 1] == 1 && gap != 0 && gap == 1) {
updateValid(i);
selected.add(new Point(ID_CASE2, i, i + 2, 2));
if (i + 3 < numbers.length && numbers[i + 3] - numbers[i + 2] == 1 && gap != 0 && gap == 1) {
updateValid(i);
selected.add(new Point(ID_CASE2, i, i + 3, 2));
if (i + 4 < numbers.length && numbers[i + 4] - numbers[i + 3] == 1 && gap != 0 && gap == 1) {
updateValid(i);
selected.add(new Point(ID_CASE2, i, i + 4, 2));
}
}
}
}
}
}
/* CASE 1212 : 반복*/
private static void selectionCase4(int[] numbers) {
int a = 0;
int b = 0;
for (int i = 0; i < numbers.length; i++) {
if (i + 1 < numbers.length) {
a = numbers[i];
b = numbers[i + 1];
if (i + 2 < numbers.length && numbers[i + 2] == a && numbers[i + 2] - numbers[i + 1] != 0) {
updateValid(i);
selected.add(new Point(ID_CASE4, i, i + 2, 4));
if (i + 3 < numbers.length && numbers[i + 3] == b && numbers[i + 3] - numbers[i + 2] != 0) {
updateValid(i);
selected.add(new Point(ID_CASE4, i, i + 3, 4));
if (i + 4 < numbers.length && numbers[i + 4] == a && numbers[i + 4] - numbers[i + 3] != 0) {
updateValid(i);
selected.add(new Point(ID_CASE4, i, i + 4, 4));
}
}
}
}
}
}
/* CASE 1357 : 등차 */
private static void selectionCase5(int[] numbers) {
int gap = 0;
for (int i = 0; i < numbers.length; i++) {
if (i + 1 < numbers.length) {
gap = numbers[i + 1] - numbers[i];
if (i + 2 < numbers.length && numbers[i + 2] - numbers[i + 1] == gap && gap != 0 && gap != 1) {
updateValid(i);
selected.add(new Point(ID_CASE5, i, i + 2, 5));
if (i + 3 < numbers.length && numbers[i + 3] - numbers[i + 2] == gap && gap != 0 && gap != 1) {
updateValid(i);
selected.add(new Point(ID_CASE5, i, i + 3, 5));
if (i + 4 < numbers.length && numbers[i + 4] - numbers[i + 3] == gap && gap != 0 && gap != 1) {
updateValid(i);
selected.add(new Point(ID_CASE5, i, i + 4, 5));
}
}
}
}
}
}
/* 어떤 케이스도 아닌 경우 */
private static void selectionCaseNot(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
if(valid[i] == false) {
if(i +2 < numbers.length) { selected.add(new Point(ID_CASENOT, i, i+2, 10)); }
if(i +3 < numbers.length) { selected.add(new Point(ID_CASENOT, i, i+3, 10)); }
if(i +4 < numbers.length) { selected.add(new Point(ID_CASENOT, i, i+4, 10));}
}
}
}
/* Print 문 */
public static void print(Point p) {
int x = -1;
int y = -1;
x = p.getX();
y = p.getY();
System.out.print(p.getCaseId() + "\t");
System.out.print("[ " + x + " , " + y + " ]\t");
for (int j = x; j <= y; j++) {
System.out.print(numbers[j]);
}
System.out.print("\t VALUE : " + p.getValue());
System.out.println("");
}
public static void print(List<Point> selected) {
int x = -1;
int y = -1;
Point p = null;
for (int i = 0; i < selected.size(); i++) {
p = selected.get(i);
x = p.getX();
y = p.getY();
System.out.print(p.getCaseId() + "\t");
System.out.print("[ " + x + " , " + y + " ]\t");
for (int j = x; j <= y; j++) {
System.out.print(numbers[j]);
}
System.out.print("\t VALUE : " + p.getValue());
System.out.println("");
}
}
}
class XComparator implements Comparator<Point> {
@Override
public int compare(Point p1, Point p2) {
int x1 = p1.getX();
int x2 = p2.getX();
if (x1 > x2) {
return 1;
} else if (x1 < x2) {
return -1;
} else {
return 0;
}
}
}
class ValueComparator implements Comparator<Point> {
@Override
public int compare(Point p1, Point p2) {
int x1 = p1.getValue();
int x2 = p2.getValue();
if (x1 > x2) {
return 1;
} else if (x1 < x2) {
return -1;
} else {
return 0;
}
}
}
class Point {
String caseId;
int x;
int y;
int value;
public Point() {
}
public Point(String caseId, int x, int y, int value) {
super();
this.caseId = caseId;
this.x = x;
this.y = y;
this.value = value;
}
public String getCaseId() {
return caseId;
}
public void setCaseId(String caseId) {
this.caseId = caseId;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
<br/>
문제풀이
예시를 들어 쉽게 문제풀이를 이해 할 수 있다.
39391237를 예를 들어 보자.
예제는 인덱스 0 ~ 7 까지 8자리의 숫자이다.
우선 각 인덱스로 시작하는 조각을 뽑아 List에 넣어 둔다.
//0번 인덱스 (난이도가 낮은 조각이 있으므로, 보다 큰 난이도의 조각은 뽑지 않는다)
393, 3939
//1번 인덱스 (난이도가 낮은 조각이 있으므로, 보다 큰 난이도의 조각은 뽑지 않는다)
939,
//2번 인덱스
391, 3912, 39125
//3번 인덱스
912, 9127, 91279
//4번인덱스
127, 1279
//5번인덱스
279
<br/>
다음은 0번 인덱스를 시작으로, 조각들을 이어주는 것이다.
0번 인덱스로 시작하는
**393, 3939 **중 393부터 시작해보자.
393 은 2번 인덱스까지의 숫자이므로 다음으로 3번 인덱스 부터 시작하는 조각을 찾는다.
3번 인덱스를 시작하는 조각은 **912, 9127, 91279 **이다. 조각들을 이어준다. 조각을 이어주며 난이도 숫자도 더 해주자.
**393 912, 393 9127, 393 91279 **세 가지의 조각 조합이 생성된다.
<br/>
그럼 또 다음 조각을 이어보자.
393 912 : 다음에는 조각이 없으므로 예외처리한다.
393 9127 : 다음에는 조각이 없으므로 예외처리한다.
<span style="color:#0000ff">393 91279 : 마지막 인덱스까지 숫자가 나왔으므로, 완성 조합으로 간주. ★
<br/>
<br/>
이제 0번 인덱스로 시작하는
**393, 3939 **중 3939부터 시작해보자.
3939 은 3번 인덱스까지의 숫자이므로 다음으로 4번 인덱스 부터 시작하는 조각을 찾는다.
4번 인덱스로 시작하는 조각은 **127, 1279이다. **조각들을 이어준다. 조각을 이어주며 난이도 숫자도 더 해주자.
3939 127, 3939 1279 두 가지의 조각 조합이 생성된다.
<br/>
그럼 또 다음 조각을 이어보자.
3939 127 : 다음에는 조각이 없으므로 예외처리한다.
<span style="color:#0000ff">3939 1279 : 마지막 인덱스까지 숫자가 나왔으므로, 완성 조합으로 간주. ★
<br/>
<br/>
그럼 이제 모든 완성된 조합을 찾았다.
완성된 조합중 가장 난이도 숫자가 적은 조합을 찾아보자. 정답!
'원주율 외우기 알고리즘' 관련된 다른글
이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.