https://leetcode.com/problems/iterator-for-combination/description/
backTracking
String.valueOf() vs to.String()
1. 문제 및 접근
1286. Iterator for Combination
String 문자열이 영어로 주어지는데, 사전 순으로 combi로 반환
들어온 숫자만큼 짤라서 반환하면 됨
순서 x 중복 상관 x 조합
순서가 중요하고 ab는 되지만 ba는 안된다는 뜻이고
ab -> bc가 아닌 ac가 나와야 사전순서
다 만들어놓고 반환하자
to-do
- 생성자 호출 시 만들어진 list 반환
- next는 다음 조합된 요소를 반환
- hasNext는 다음 조합 요소가 있으면 t,f 반환
Constraints:
- 1 <= combinationLength <= characters.length <= 15
- All the characters of characters are unique.
- At most 10^4 calls will be made to next and hasNext.
- It is guaranteed that all calls of the function next are valid.
2. 내 풀이(틀림)
처음에 next와 hasNext를 호출할 때 만들어서 계쏙 부를까 하다가,
생성자 호출 시 만들어 놓고, next와 hasNext는 만들어진 list에 부를 때 마다 index를 증가시켜 찾는 형식으로 생각했다.
그러면 탐색의 과정에선 map에 저장 하는 게 더 효율적이지 않을까 ?..
제한 사항이 10,000번 들어오니까 일단 보류
BackTracking이라는 건 알겠지만, for문으로 작성하다 보니, 탈출 조건에서 애매해서 힘들었다..
이것 저것 추가하다보니, 너무 길어지기도 하고 헷갈려서 재귀 방법을 선택 ㅠㅠ
3. BackTracking
백트래킹은 특정 문제를 해결하기 위해 해를 찾는 과정에서 불필요한 경로를 포기하는 데 중점.
최적해를 찾기 위해 depth를 타고 내려가지만, 조건에 맞지 않으면 바로 탈출해서 다음 조건을 찾는다.
나는 DFS,BFS랑 BackTracking이랑 같은 걸로 생각했는데 사실 depth가 조건이라고 생각하면 같긴 하지만,
DFS
- dfs는 depth를 끝까지 돌고, 나온다
- 모든 경로(depth니까 있는 곳까지 다) 탐색
BackTracking
- backTracking은 조건에 맞지 않으면 바로 나온다.
- 유망하지 않은 노드라면 바로 포기
- 제한사항까지만 돈다는 것
- DFS보단 BFS가 더 어울리는 느낌
BackTracking은 얼마나 한정 조건(유망하지 않은 노드)을 잘 설정하냐에 따라 많이 차이가 난다.
아 다르고 어 다르다.
4. 풀이
public class combinationIteratorAnswer {
private List<String> list = new ArrayList<>();
private int now = 0;
String characters = " ";
int combiLength;
public static void main(String[] args) {
String ch = "chp";
int combi = 1;
String test = "abc";
int comm = 2;
// combinationIterator정답 main = new combinationIterator정답(ch, combi);
combinationIterator main = new combinationIterator(test, comm);
System.out.println(main.hasNext());
System.out.println(main.next());
System.out.println(main.hasNext());
System.out.println(main.hasNext());
System.out.println(main.next());
System.out.println(main.next());
System.out.println(main.hasNext());
System.out.println(main.hasNext());
System.out.println(main.hasNext());
}
public combinationIteratorAnswer(String characters, int combinationLength) {
this.characters = characters;
this.combiLength = combinationLength;
generateCombinations(new StringBuilder(), 0);
}
private void generateCombinations(StringBuilder current, int start) {
if (current.length() == combiLength) {
list.add(current.toString());
return;
}
for (int i = start; i < characters.length(); i++) {
current.append(characters.charAt(i));
generateCombinations(current, i + 1);
current.deleteCharAt(current.length() - 1);
}
}
public String next() {
// 호출 시 하나씩 반환
String next = list.get(now++);
// String next = la.get(now++);
return next;
}
public boolean hasNext() {
return combiLength < list.size();
// size가 더 작으면 true
// 5 < 10
// 11 < 10 이면 False
}
}
4-1. 전역변수
정답을 담을 list와
입력으로 들어온 characters = "abc",
조합의 길이인 combiLength = 2,
그리고 next, hasNext 호출 시 증가시킬 index = 0
4-2. 생성자
생성자 호출 시 들어온 값을 담아주고,
재귀메서드인 generateCombinations 를 StringBuilder와 index를 넣어 호출
4-3. generateCombinations(재귀)
탈출 조건은 현재 StringBuilder에 담긴 String의 length가 처음에 주어진 combiLength가 된다면
list에 정답인 StringBuilder를 담고 return;
ex) 현재 combiLength는 2다.
characters = "abc"
combiLength = 2
핵심로직인 for문은
들어온 Start의 index를 가지고, characters를 도는데,
1. StringBuilder인 current에 현재 i를 더해준다.
- ex) current = "a" , i = 0 , list = { }
2. generateCombinations("a" , 1) 호출
- if문 통과 후 start =1인 상태에서 다시 for문
- current = "a" + "b", i =1 , list = { }
3. generateCombinations("ab" , 2) 호출
- if문에 걸려 list에 추가 , list = {ab}
4. 2-1 generateCombinations("a" , 1)로 돌아가기
- 현재 generateCombinations("a" , 1)에서 index+1 호출이 끝났으니
- current.deleteCharAt(current.length() - 1)를 실행하고 나면
- current = "ab " -> "a"로 제거
5. 2-2 generateCombinations("a" , 1)
- 4의 단계에서, current = "a" , i =2 , list = {ab} (b를 제거했다 현재 단계에선 현재 인덱스의 char를 넣을꺼라)
- 2.를 호출한 곳에서 i값이 증가해 2=c를
- current = "a" + "c" i=2를 다시 index+1로 호출하면
- ac가 list에 담긴다. list = {ab,ac} 다시 return 반복
6. 호출 후 반복 후 BackTracking!
말로 설명할려니 어려운데,, 꼭 debuging 해보길 바란다.. 내 설명이 부족해서
(재귀 함수 부를 때 마다 StringBuilder를 초기화 시켰다가 시간을 좀 보냈다 ㅠㅜ DeleteCharAt을 생각 못해서..)
4-4. next(), hasNext()
제한사항에
- It is guaranteed that all calls of the function next are valid.
위 사항으로 없는 index를 호출할 일이 없어 에러가 나지 않는다.
부를 때 마다 now++해주고, 현재 index의 list의 요소를 반환
hasNext()는 들어온 조합의 길이와 정답 list의 size를 비교해
True or False 반환
성공~!
번외. String.valueOf() vs .toString()
현재 추가하는 경우에 StringBuilder로 사용하는데, 정답의 경우 String 타입의 반환이기에
StringBuilder를 String으로 타입 변환을 해줘야 한다.
String.valueOf()만 습관적으로 쓰다 문득
String.valueOf()와 toString()의 차이가 궁금해졌다..
1. String.valueOf()
2. toString()
String.valueOf()는 보면 null 값에 대한 처리가 있고, null이 아닐 경우에 toString()을 호출 하는 것을 볼 수 있다.
toString은 이해하기 어려워 gpt 형님 호출!
gpt 형님이 비교해준 걸 보자면,
null 값에 대한 처리가 다르다.
실제로 코드로 확인해보자.
hello를 넣어보면
둘다 똑같은 hello를 반환하고,
null값을 넣어보면
str3인 toString의 경우 NPE가 발생하는 걸 알 수 있고,
str4인 valueOf = null 값이 찍힌다.
결론은 ?
StringBuilder 객체가 null이 아님을 확신할 수 있는 경우 toString() 메서드를 사용하는 것이 좋다.
그러나 null 가능성을 염두에 두어야 하는 상황에서는 String.valueOf()를 사용하는 것이 더 안전할 수 있다.
전에 블로깅 했듯이 에러를 발생시키지 않냐 or 발생 하더라도 데이터의 정확성이 중요하냐 에 따라 맞게 선택하면 될 것 같다.
4. 마무리
아 진짜 거의 다 풀었는데, 다른 풀이를 참고해서 너무 분하다..
(못푼거임 사실)
keyword인 backTracking의 조건에 맞지 않는 녀석을 직관적으로 바로 떠오르는 게 힘들었다..
dp문제도 풀고 있는데 진짜 나는 언제 늘까.. 꾸준히 할 뿐이다..
그래도 String.valueOf() 와 toString()의 차이를 찾아내고 알아가니 행복하다..
이런 작지만 사소한 것들을 다 알고 싶다.. 배움에는 끝이 없고 도움되지 않는 지식도 없듯이
내가 알고 있는 고래가 아가미가 없는 이유, 거미가 집을 지을 때 나무를 어떻게 건너 가는가 ?
같은 작은 사소한 것들에 대한 집요함을 잃지말자~!
베토벤도 무라마키 하루키도, 바흐도 피카소도 유명한 작품들은 5%로 안된다고 했다..
저런 천재들도 그냥 꾸준함으로 승부 보는데, 평범한 나도 열심히 해야게따..
'알고리즘' 카테고리의 다른 글
| 99클럽 코테 스터디 31일차 TIL Sort Characters By Frequency feat. Comparator vs Comparable (0) | 2024.06.20 |
|---|---|
| 99클럽 코테 스터디 30일차 TIL Minimum Suffix Flips (0) | 2024.06.19 |
| 28일-2 Group the People Given the Group Size They Belong To (0) | 2024.06.17 |
| 99클럽 코테 스터디 28일차 TIL Find Words Containing Character (0) | 2024.06.17 |
| 99클럽 코테 스터디 27일차 TIL Find The Original Array of Prefix Xor (0) | 2024.06.15 |