문제 url:
칸토어 집합
문제:
🤔 문제 알아보기
이쯤되니 문제를 볼 때마다 눈이 아프다.. 왜 이런 문제들만
해당 문제를 같이 알아보자면,
"-" 가 만큼 존재하는데, 이를 3등분하여 가운데에 존재하는 "-"는 공백으로 변경하는 문제이다.
즉, 만약 길이가 3일경우 "---" 에서 "- -"이 된다는 의미이다.
그럼 길이가 9라면? "---------" "--- ---"이 된다. 9를 3등분하면, 크기가 3, 3, 3씩 나누어 지기 때문에 3만큼 공백이 생긴다.
하지만! 문제 조건에서 모든선의 길이가 1이 될 때까지 나눈다고 했다.
"--- ---"그럼 이 친구 중 "-"가 존재하는 등분을 다시 3등분한다.
마지막으로 "- - - -" 이와 같을 수 있다.
나중에 확인했는데, 벨로그는 연속되는 공백을 그냥 하나의 공백으로 본다
그러면 우리는 해당 문제를 재귀를 이용해서 풀 수 있다.
재귀를 이용하는 데, 길이가 1이 될 때까지 나누면 될 것이다.
🐱👤 실제 코드
import java.io.*;
public class Main {
static String[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sbd = new StringBuilder();
while(true) {
String str = br.readLine();
if(str != null && !str.isEmpty()) {
if(str.equals("0")) {
sbd.append("-").append("\n");
continue;
}
int N = (int) Math.pow(3,Integer.parseInt(str));
arr = new String[N];
for(int i = 0; i < N; i++) {
arr[i] = "-";
}
divide(0, N);
for(int i = 0; i < N; i++) {
sbd.append(arr[i]);
}
sbd.append("\n");
} else {
break;
}
}
System.out.println(sbd);
}
static void divide(int start, int length) {
/*
* 즉, 마지막 길이가 1보다 작다는 의미는, 길이가 하나밖에 없다는 얘기
*/
if(length <= 1) {
return;
}
// 중앙값을 입력,
int new_length = length / 3;
/*
* 2번째 부분 공백
* 왜 반복을 start + new_length * 2만큼하는가??
* new_start는 현재 3등분한 길이를 의미한다,
* 공백화 시키려는 배열의 마지막 길이는 그러면 new_length * 2만큼 될 것이다.
* 그러면 시작 부분은? start+ new_start만큼 하면 시작부분이 되는 것
*/
for(int i = start+ new_length; i < start + new_length * 2; i++) {
arr[i] = " ";
}
// 첫번째 부분 반환
divide(start, new_length);
// 세번째 부분 반환
divide(start + new_length * 2, new_length);
}
}
😉 코드 풀이 및 해석
첫 번쨰 코드
while(true) {
String str = br.readLine();
if(str != null && !str.isEmpty()) {
if(str.equals("0")) {
sbd.append("-").append("\n");
continue;
}해당 문제의 조건에서느 EOF(End of File)가 됐을 경우 반복을 멈춰라고 했다.
그래서, 다음과 같이 조건문을 만들어 줬는데,
필자는 BufferedReader를 사용하였기에 저런 형태이지만,
Scanner는 while문 조건으로hasNext()를 이용하면 된다고 한다.
그 후, 입력값이 0이라면 재귀를 하지 않고 "-"를 출력
두 번째 코드
static void divide(int start, int length) {
/*
* 즉, 마지막 길이가 1보다 작다는 의미는, 길이가 하나밖에 없다는 얘기
*/
if(length <= 1) {
return;
}
// 중앙값을 입력,
int new_length = length / 3;
/*
* 2번째 부분 공백
* 왜 반복을 start + new_length * 2만큼하는가??
* new_start는 현재 3등분한 길이를 의미한다,
* 공백화 시키려는 배열의 마지막 길이는 그러면 new_length * 2만큼 될 것이다.
* 그러면 시작 부분은? start+ new_start만큼 하면 시작부분이 되는 것
*/
for(int i = start+ new_length; i < start + new_length * 2; i++) {
arr[i] = " ";
}
// 첫번째 부분 반환
divide(start, new_length);
// 세번째 부분 반환
divide(start + new_length * 2, new_length);
}처음에 divide로 (0과 N)을 입력해주는데, N은 을 해준 값이다.
설명은 대부분 주석으로 처리했지만, 필자는 해당 문제를 못풀었기 때문에 복기차원에서 설명하자면,
divide 메서드의 두번째 파라미터는 길이를 입력받을 것이다.
이것이 중요한 데, 그 이유는 첫 번째 로직으로 길이가 1보다 작거나 같으면 return해줘야 하기 때문이다.
우리는 문제 조건에서 길이가 1일경우 즉 "-"이 상태면 나누는 것을 멈춰라고 했다.
그래서 재귀를 length가 1이하가 될 때까지 반복하는 것이다.
그런 다음, new_length 변수에 길이 /3으로 현재 새로운 길이를 입력받는다.
해당 길이를 통해서 3등분 했을 때 나타낼 수 있는 범위를 구할 수 있는 것이다.
for(int i = start+ new_length; i < start + new_length * 2; i++) {
arr[i] = " ";
}해당 코드는 두 번째(공백이 되어야 할) 등분을 나타낸 로직인데, 이를 살펴보면
start + length를 하여, 시작점, 즉 첫 번째 등분의 마지막 인덱스 +1값 부터 시작하여
length * 2미만까지 반복한다.
여기서 왜 length 2인가? 두 번째 등분의 마지막 지점은
첫 번째 등분 + 2번 째 등분한 값과 같이 때문에 결국 length 2와 같은 것이며,
첫 시작점이 0이 아닐 수 있기 때문에 start를 더해주는 것이다.
🤣 회고
근래, 몸살기운이 심하고, 운동량을 늘렸더니 체력이 남아나질 않는다..
그래서 공부량이 저조해지고 있는데, 그럼에도 재충전이 되지 않는다.
해당 문제도 사실 조금만 고민해보면 풀 수 있는 문제인데, 너무 쉽게 포기해 버려서 스스로에게 너무 놀랬다.
근 1달 반동안 쉬지않고 알고리즘을 해와서 그런지 약간의 휴식이 필요해 보인다.
