[코딩 테스트] 칸토어 집합

문제 출처

https://www.acmicpc.net/problem/4779

 

문제풀이 생각과 과정

• 재귀를 통해서 왼쪽 부분과 오른쪽 부분을 계속 호출해야 할 것 같았음
  • 재귀 종료 조건은 마지막 한 개 남았을 경우 재귀 종료

이렇게 간단하게 생각하고 문제에 들어갔다.

문제 들어가서 인덱스 계산하는데 조금 햇갈려서 그림을 그려보았다.

예시는 N이 2일 경우이고, 즉 3^2 = 9 개의 집합이 있을 때이다.

(아래 참고)

 

이런식으로 재귀를 호출하면서 분할 정복으로 마지막 정복이 됐을 때 결과를 Print해주면 된다. StringBuilder를 통해서 String을 관리해주었다.

 

 

자바 문법 알게된 점

StringBuilder에 있는 replace(start,end,..) 메서드를 통해서 빈 문자열로 바꾸는 작업을 했는데 여기서 주의할 점이 있었다.

 

replace(start, end ,바꿀 문자열) 인데

여기서 end는 end-1의 내용까지를 바꾸는 것이다.

 

코드 예시를 보면서 말하자면

StringBuilder sb = new StringBuilder();
sb.append("Hello!");
sb.replace(0,3,"X");

라는 코드가 있으면

나는 "Hello!" 문자열에서 0번부터 3번 인덱스. 즉, H,e,l,l 까지 X로 바뀌어서

 

"Xo!" 라는 문자열이 나올 줄 알았지만

 

end-1 인덱스 까지. 즉, H,e,l 까지 X로 바뀌어서

 

결과는 "Xlo!"라는 문자열이 출력이 되게 된다.

 

또한 String에서 repeat()메서드를 사용하면 특정 문자열을 반복하는 문자열을 생성할 수 있다.

 

예를 들면

String space = "-".repeat(10);

를 하게되면

String space = "----------"

이렇게 선언한 것과 같게 된다.