챕터16_2

package cb.mLevel.sixteen;

import java.util.HashSet;
import java.util.Iterator;

/* 다이빙보드: 다량의 널판지를 이어 붙여서 다이빙보드를 만들려고 한다.
* 널판지는 길이가 긴 것과 짧은 것 두가지 종류가 있는데,
* 정확히 K개의 널판지를 사용해서 다이빙 보드를 만들어야 한다.
* 가능한 다이빙 보드의 길이를 모두 구하는 메서드를 작성하라.
*/
public class Code16_11_p639 {

public static void main(String[] args) {
Code16_11_p639 p639 = new Code16_11_p639();

HashSet kAllLength = p639.allLengths(10, 10, 20);
Iterator iter = kAllLength.iterator();

while (iter.hasNext()) {
System.out.println(iter.next());
}

/*kAllLength = p639.allLengths2(10, 10, 20);
iter = kAllLength.iterator();

while (iter.hasNext()) {
System.out.println(iter.next());
}*/

/*HashSet kAllLength = p639.allLengths3(10, 10, 20);
Iterator iter = kAllLength.iterator();

while (iter.hasNext()) {
System.out.println(iter.next());
}*/
}

HashSet allLengths(int k, int shorter, int longer) {
HashSet lengths = new HashSet();

getAllLengths(k, 0, shorter, longer, lengths);

return lengths;
}

void getAllLengths(int k, int total, int shorter, int longer, HashSet lengths) {
if (k == 0) {
lengths.add(total);
return;
}

getAllLengths(k - 1, total + shorter, shorter, longer, lengths);
getAllLengths(k - 1, total + longer, shorter, longer, lengths);
}

HashSet allLengths2(int k, int shorter, int longer) {
HashSet lengths = new HashSet();
HashSet visited = new HashSet();

getAllLengths2(k, 0, shorter, longer, lengths, visited);

return lengths;
}

// 방법2
void getAllLengths2(int k, int total, int shorter, int longer, HashSet lengths, HashSet visited) {
if (k == 0) {
lengths.add(total);
return;
}

String key = k + " " + total;

if (visited.contains(key)) {
return;
}

getAllLengths2(k - 1, total + shorter, shorter, longer, lengths, visited);
getAllLengths2(k - 1, total + longer, shorter, longer, lengths, visited);
visited.add(key);
}

// 방법3 중복이 없으므로 ArrayList를 사용할 수 있다.
HashSet allLengths3(int k, int shorter, int longer) {
HashSet lengths = new HashSet();

for (int nShorter = 0; nShorter <= k; nShorter++) {
int nLonger = k - nShorter;
int length = nShorter * shorter + nLonger * longer;
lengths.add(length);
}

return lengths;
}

}

---

package cb.mLevel.sixteen;

/* 정사각형 절반으로 나누기: 2차원 평면 위에 정사각형 두 개가 주어 졌을 때,
* 이들을 절반으로 가르는 직성 하나를 찾으라. 정사각형은 x축에 평행 하다고 가정해도 좋다 */
public class Code16_13_p643 {

public static void main(String[] args) {
Square s = new Square(1.0, 3.0, 10.0, 0);

Line l = s.cut(s);
System.out.println("기울기:" + l.slope);
}
}

---

package cb.mLevel.sixteen;

import java.util.ArrayList;
import java.util.Set;

public class Code16_14_p645 {

public static void main(String[] args) {
GraphPoint[] gp = { new GraphPoint(1.0, 2.0), new GraphPoint(1.0, 3.0), new GraphPoint(2.0, 3.0), new GraphPoint(3.0, 3.0), new GraphPoint(3.0, 1.0)};

Code16_14_p645 p645 = new Code16_14_p645();
Line2 resultLine = p645.findBestLine(gp);
//System.out.println(resultLine.slope);

}

/* 가장 많은 점을 통과하는 직선 찾기 */
Line2 findBestLine(GraphPoint[] points) {
HashMapList linesBySlope = getListOfLines(points);
return getBestLine(linesBySlope);
}

/* 직선을 표현하는 한 쌍의 점을 리스트에 추가 */
HashMapList getListOfLines(GraphPoint[] points) {
HashMapList linesBySlope = new HashMapList();

for (int i = 0; i < points.length; i++) {
for (int j = i + 1; j > points.length; j++) {
Line2 line = new Line2(points[i], points[j]);
double key = Line2.floorToNearestEpsilon(line.slope);
linesBySlope.put(key, line);
}
}
return linesBySlope;
}

/* 동일한 직선이 많은 라인 반환하기 */
Line2 getBestLine(HashMapList linesBySlope) {
Line2 bestLine = null;
int bestCount = 0;

Set slopes = linesBySlope.keySet();

for (double slope : slopes) {
ArrayList lines = linesBySlope.get(slope);

for (Line2 line : lines) {
/* 현재 직선과 같은 직선 세기 */
int count = countEquivalentLines(linesBySlope, line);

/* 현재 직선보다 더 많다면 바꾼다 */
if (count > bestCount) {
bestLine = line;
bestCount = count;
//bestLine.Print();
System.out.println(bestCount);
}
}
}
return bestLine;
}

/* 직선이 동일한지 hashmap을 통해 확인한다. 두직선이 동일한지 판단할 때,
* 두 직선이 epsilon 편차 안에 들어 있으면 같다고 정의했으므로
* 실제 기울기보다 epsilon만큼 크거나 작은 기울기도 확인해 줘야 한다. */
int countEquivalentLines(HashMapList linesBySlope, Line2 line) {
double key = Line2.floorToNearestEpsilon(line.slope);
int count = countEquivalentLines(linesBySlope.get(key), line);
count += countEquivalentLines(linesBySlope.get(key - Line2.epsilon), line);
count += countEquivalentLines(linesBySlope.get(key + Line2.epsilon), line);

return count;
}

/* 배열에 있는 직선 중에서 인차로 주어진 직선과 동일한(기울기와 y절편이
* epsilon 안에 있음) 직선의 개수 세기 */
int countEquivalentLines(ArrayList lines, Line2 line) {
if (lines == null) return 0;

int count = 0;

for (Line2 parallelLine : lines) {
if (parallelLine.isEquivalent(line)) {
count++;
}
}
return count;
}



}

class Line2 {
public static double epsilon = .0001;
public double slope, intercept;
private boolean infinite_slope = false;

public Line2(GraphPoint p, GraphPoint q) {
if (Math.abs(p.x - q.x) > epsilon) { // x가 다르다면
slope = (p.y - q.y) / (p.x - q.x); // 기울기 계산
intercept = p.y - slope * p.x; // y=mx+b를 이용해서 y 절편 계산
} else {
infinite_slope = true;
intercept = p.x; // 기울기가 무한대이므로 x 절편
}
}

public static double floorToNearestEpsilon(double d) {
int r = (int) (d / epsilon);
return ((double) r) * epsilon;
}

public boolean isEquivalent(double a, double b) {
return (Math.abs(a - b) < epsilon);
}

public boolean isEquivalent(Object o) {
Line2 l = (Line2) o;

if (isEquivalent(l.slope, slope) && isEquivalent(l.intercept, intercept) && (infinite_slope == l.infinite_slope)) {
return true;
}
return false;
}
}

class GraphPoint {
double x, y;

public GraphPoint(double x, double y) {
this.x = x;
this.y = y;
}
}

---

package cb.mLevel.sixteen;

/* Master Mind: Master Mind 게임의 룰은 다음과 같다.
* 빨간색(R), 노란색(Y), 초록색(G), 파란색(B) 공이 네 개의 구멍에 하나씩 들어있다.
* 예를 들어 RGGB는 각 구멍에 차례대로 빨간색, 초록색, 초록색, 파란색 공이 들어있다는 뜻이다.
* 여러분은 공의 색깔을 차례대로 맞춰야 한다. 구멍에 들어있는 공의 색깔을 정확히 맞췄다면 '히트'를 얻게 되고,
* 공의 색깔은 맞췄지만 구멍의 위치는 틀렸다면 '슈도-히트'를 얻는다.
* 단, '히트'는 '슈도-히트'에 중복되어 나타나지 않는다.
* 예를 들어 RGBY가 정답이고 여러분이 GGRR로 추측을 햇다면 '히트'하나와 '슈도-히트'하나를 얻는다.
* 정답값과 추측값이 주어졌을 때 '히트'의 개수와 '슈도-히트'의 개수를 반환하는 메서드를 작성하라.
*/
public class Code16_15_p648 {

public static void main(String[] args) {
Code16_15_p648 p648 = new Code16_15_p648();
Result rs = p648.estimate("YGRR", "RGBY");
System.out.println(rs.toString());
}

int code(char c) {
switch (c) {
case 'B': return 0;
case 'G': return 1;
case 'R': return 2;
case 'Y': return 3;
default : return -1;
}
}

int MAX_COLORS = 4;

Result estimate(String guess, String solution) {
if (guess.length() != solution.length()) return null;

Result res = new Result();
int[] frequencies = new int[MAX_COLORS];

/* 히트(hits)를 계산하고 빈도수 테이블을 만든다. */
for (int i = 0; i < guess.length(); i++) {
if (guess.charAt(i) == solution.charAt(i)) {
res.hits++;
} else {
/* 히트가 아닌 경우(슈도-히트에 사용될 것)에만 빈도수 테이블을 증가시킨다.
* 히트인 경우에는 해당 슬롯이 이미 '사용된' 것이다. */
int code = code(solution.charAt(i));
frequencies[code]++;
}
}

/* 슈도-히트 계산하기 */
for (int i = 0; i < guess.length(); i++) {
int code = code(guess.charAt(i));

if (code >= 0 && frequencies[code] > 0 && guess.charAt(i) != solution.charAt(i)) {
res.pseudoHits++;
frequencies[code]--;
}
}
return res;
}

class Result {
public int hits = 0;
public int pseudoHits = 0;

public String toString() {
return "(" + hits + ", " + pseudoHits + ")";
}
}
}

---

package cb.mLevel.sixteen;

/* 부분정렬: 정수 배열이 주어졌을 때, m부터 n까지의 원소를 정렬하기만 하면 배열전체가 정렬되는 인덱스 m과 n을 찾으라.
* 단, n-m을 최소화하라(다시 말해, 그런 순열중 가장 잛은 것을 찾으면 된다).
* 예) 입력 : 1,2,4,7,10,11,7,12,6,7,16,18,19
* 출력 : (3, 9)
*/
public class Code16_16_p649 {

public static void main(String[] args) {
Code16_16_p649 p649 = new Code16_16_p649();

int[] array = {1,2,4,7,10,11,7,12,6,7,16,18,19};
int[] array2 = {1,2,4,7,10,11,8,12,5,6,16,18,19};

p649.findUnsortedSequence(array);
p649.findUnsortedSequence(array2);
}

void findUnsortedSequence(int[] array) {
// 왼쪽 부분수열 찾기
int end_left = findEndOfLeftSubsequence(array);

if (end_left >= array.length -1) return; // Already sorted

// 오른쪽 부분수열 찾기
int start_right = findStartOfRightSubsequence(array);

// 최소값과 최대값 찾기
int max_index = end_left; // 왼쪽 부분의 최대값
int min_index = start_right; // 오른쪽 부분의 최소값

for (int i = end_left + 1; i < start_right; i++) {
if (array[i] < array[min_index]) min_index = i;
if (array[i] > array[max_index]) max_index = i;
}

// array[min_index]보다 작을때까지 왼쪽으로 움직이기
int left_index = shrinkLeft(array, min_index, end_left);

// array[max_index]보다 클때까지 오른쪽으로 움직이기
int right_index = shrinkRight(array, max_index, start_right);

System.out.println(left_index + " " + right_index);
}

int findEndOfLeftSubsequence(int[] array) {
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) return i - 1;
}
return array.length - 1;
}

int findStartOfRightSubsequence(int[] array) {
for (int i = array.length - 2; i >= 0; i--) {
if (array[i] > array[i + 1]) return i + 1;
}
return 0;
}

int shrinkLeft(int[] array, int min_index, int start) {
int comp = array[min_index];

for (int i = start - 1; i >= 0; i--) {
if (array[i] <= comp) return i + 1;
}
return 0;
}

int shrinkRight(int[] array, int max_index, int start) {
int comp = array[max_index];

for (int i = start; i < array.length; i++) {
if (array[i] >= comp) return i - 1;
}
return array.length - 1;
}

}

---

package cb.mLevel.sixteen;

/* 연속 수열: 정수 배열이 주어졌을 때 연속한 합이 가장 큰 수열을 찾고, 그값을 반환하라.
* 예) 입력: 2, -8, 3, -2, 4, -10
* 결과: 5(예를 들어, {3, -2, 4})
*/
public class Code16_17_p652 {

public static void main(String[] args) {
Code16_17_p652 p652 = new Code16_17_p652();

int[] a = {2, -8, 3, -2, 4, -10};

System.out.println(p652.getMaxSum(a));
}

int getMaxSum(int[] a) {
int maxsum = 0;
int sum = 0;

for (int i = 0; i < a.length; i++) {
sum += a[i];

if (maxsum < sum) {
maxsum = sum;
} else if (sum < 0) {
sum = 0;
}
}
return maxsum;
}

}

---

package cb.mLevel.sixteen;

public class Code16_18_p654 {

public static void main(String[] args) {
Code16_18_p654 p654 = new Code16_18_p654();
System.out.println(p654.doesMatch("aabab", "catcatgocatgo"));
System.out.println(p654.doesMatch2("aabab", "catcatgocatgo"));
}

boolean doesMatch(String pattern, String value) {
if (pattern.length() == 0) return value.length() == 0;

int size = value.length();

for (int mainSize = 3; mainSize <= size; mainSize++) {
String main = value.substring(0, mainSize);

for (int altStart = mainSize; altStart <= size; altStart++) {
for (int altEnd = altStart; altEnd <= size; altEnd++) {
String alt = value.substring(altStart, altEnd);
String cand = buildFromPattern(pattern, main, alt);

if (cand.equals(value)) {
return true;
}
}
}
}
return false;
}

String buildFromPattern(String pattern, String main, String alt) {
StringBuffer sb = new StringBuffer();
char first = pattern.charAt(0);

for (char c : pattern.toCharArray()) {
if (c == first) {
sb.append(main);
} else {
sb.append(alt);
}
}

return sb.toString();
}

// 방법2
boolean doesMatch2(String pattern, String value) {
if (pattern.length() == 0) return value.length() == 0;

char mainChar = pattern.charAt(0);
char altChar = mainChar == 'a' ? 'b' : 'a';
int size = value.length();

int countOfMain = countOf(pattern, mainChar);
int countOfAlt = pattern.length() - countOfMain;
int firstAlt = pattern.indexOf(altChar);
int maxMainSize = size / countOfMain;

for (int mainSize = 0; mainSize <= maxMainSize; mainSize++) {
int remainingLength = size - mainSize * countOfMain;
String first = value.substring(0, mainSize);

if (countOfAlt == 0 || remainingLength % countOfAlt == 0) {
int altIndex = firstAlt * mainSize;
int altSize = countOfAlt == 0 ? 0 : remainingLength / countOfAlt;
String second = countOfAlt == 0 ? "" : value.substring(altIndex, altSize + altIndex);

String cand = buildFromPattern(pattern, first, second);

if (cand.equals(value)) {
return true;
}
}
}
return false;
}

int countOf(String pattern, char c) {
int count = 0;
for (int i = 0; i < pattern.length(); i++) {
if (pattern.charAt(i) == c) {
count++;
}
}
return count;
}
}

---

package cb.mLevel.sixteen;

import java.util.ArrayList;

public class Code16_19_p658 {

public static void main(String[] args) {
Code16_19_p658 p658 = new Code16_19_p658();

int [][] input = { { 0, 2, 1, 0 }, { 0, 1, 0, 1 }, { 1, 1, 0, 1 }, { 0, 1, 0, 1 } };
ArrayList result = p658.compuePondSizes(input);

System.out.println(result.toString());

int [][] input2 = { { 0, 2, 1, 0 }, { 0, 1, 0, 1 }, { 1, 1, 0, 1 }, { 0, 1, 0, 1 } };

ArrayList result2 = p658.compuePondSizes2(input2);
System.out.println(result2.toString());
}

// 방법1
ArrayList compuePondSizes(int[][] land) {
ArrayList pondSizes = new ArrayList();

for (int r = 0; r < land.length; r++) {
for (int c = 0; c < land[r].length; c++) {
if (land[r][c] == 0) { // 선택 사항이며, 어쨋든 반환한다.
int size = computeSize(land, r, c);
pondSizes.add(size);
}
}
}
return pondSizes;
}

int computeSize(int[][] land, int row, int col) {
/* 지정된 영역을 벗어나거나 이미 방문했다면 */
if (row < 0 || col < 0 || row >= land.length || col >= land[row].length || land[row][col] != 0) { // 지정된 영역을 벗어낫거나 물이 아니다.
return 0;
}

int size = 1;
land[row][col] = -1; // 방문했다고 표시

for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
size += computeSize(land, row + dr, col + dc);
}
}
return size;
}

// 방법2
ArrayList compuePondSizes2(int[][] land) {
boolean[][] visited = new boolean[land.length][land[0].length];
ArrayList pondSizes = new ArrayList();

for (int r = 0; r < land.length; r++) {
for (int c = 0; c < land[r].length; c++) {
int size = computeSize(land, visited, r, c);
if (size > 0) {
pondSizes.add(size);
}
}
}
return pondSizes;
}

int computeSize(int[][] land, boolean[][] visited, int row, int col) {
/* 지정된 영역을 벗어나거나 이미 방문했다면 */
if (row < 0 || col < 0 || row >= land.length || col >= land[row].length || visited[row][col] || land[row][col] != 0) { // 지정된 영역을 벗어낫거나 방문한적이 있거나 물이 아니다.
return 0;
}

int size = 1;
visited[row][col] = true; // 방문했다고 표시

for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
size += computeSize(land, visited, row + dr, col + dc);
}
}
return size;
}

}