이진 변환 반복하기
링크: https://school.programmers.co.kr/learn/courses/30/lessons/72411
문제분류 : 구현, 백트래킹
난이도 : Level 2
결과: 실패
회고
처음 문제풀이 방법을 생각했을 때는 등장한 모든 글자들을 구하고
그 문자들을 가지고 만들 수 있는 모든 조합을 구한 후에 비교하는 것을 생각했다.
근데, 이렇게 되면 시간초과 나는거 아닌가 싶어서 멈칫했다...!
또 메뉴 문자열 안에 그 조합이 포함되어 있는지 판단하는 방법으로
정규표현식을 사용하려 했는데,이리저리 풀이가 꼬여서 계속 답이 안나왔다.
결국 안풀려서 답을 확인했는데, 의외로 풀이 맥락은 어느 정도 맞았다.
하지만 복잡한 조건들을 쉽게 풀어나가는 방식들이 배울점이 많아 공부할 겸 올려보려고 한다.
모범 답안
먼저 solution 메서드이다.
여기서는 코드가 크게 세 부분으로 나눠진다.
- 답을 구하기 위해 필요한 데이터를 편리하게 가공
- 재귀메서드(getCourses)를 통해 답을 구함
- stream을 이용해 문제에서 원하는 형태의 답으로 반환
먼저 List<Set< String>> orderList 에 주목해보자.
이런 방식으로 데이터를 패키징하는 이유는 답을 편하게 구하기 위해서이다.
나는 정규식을 가지고 orders 안의 문자열에서 조합의 존재유무를 확인하려했다.
이 방법은 정규표현식에 익숙하지 않다면 좀 힘들 수 있다.(그리고 나는 정규표현식에 익숙하지 않다...ㅎ)
반면 모범 답안의 코드는 orders에 저장된 String을 구성하는 글자들을
char로 바꿨다가 다시 String으로 바꾼다. 그리고 바꾼 글자들 하나하나(하나의 메뉴)를 Set에 저장한다.
Set 메서드의 containsAll을 이용해서 조합의 유무를 확인할 수 있기 때문이다.
정말 좋은 아이디어라 생각했다.
두 번째로 주목할 부분은 Map< Integer, List< String>>courses 이다.
key는 코스가 포함할 메뉴의 개수, Value는 답의 후보가 되는 코스들이다.
여기서 for문으로 course 배열 안에 있는 데이터를 순회한다.
course에는 코스가 필요로하는 메뉴의 개수이다.
value의 List에 들어가는 Course는 답의 후보가 되는 정보들을 담는 클래스다.
List를 초기화 할때 더미 Course를 같이 넣는 이유는 답을 찾는 과정에서 NPE를 방지하기 위함이다.
물론 모범답안의 알고리즘은 이 더미데이터가 있어야 NPE를 피할 수 있지만,
if문을 활용해서 NPE를 방지할 수도 있으니 취향에 따라 코드를 바꾸면 될거 같다.
Course 클래스는 답의 후보가 되는 코스의 정보를 저장하는 클래스이다.
course는 코스가 어떤 메뉴들로 조합되어 있는지를 나타내는 문자열이고
occurrences는 course가 orderList들에서 몇 번이나 나타났는지를 나타내는 정수이다.
이 두 정보가 필요한 이유는 코스조합을 저장, 출현 횟수가 2번 이상, 가장 많이 등장한 조합을 찾기 위해서이다.
자세한 것은 getCourses 메서드 안에서 보도록 하자.
이제 조합으로 답의 후보가 되는 코스를 찾는 getCourses 메서드이다.
주석으로 간단하게 설명을 달아놓긴 했지만 핵심이 되는 부분은 설명해보도록 하겠다.
먼저 메서드의 처음부분에서 orderList를 스트림으로 변경한다.
그리고 orderList가 가진 주문 리스트에 만들어진 조합(selectedMenus)이 포함되었는지 확인한다.
여기서 containsAll을 통해 간단하게 포함여부를 확인할 수 있기 때문에, 앞에서 Set으로 바꾼 것이다🤩
마지막으로 count를 통해 몇 번이나 등장했는지 체크한다.
여기서 2번 이상 나오지 않은 조합은 return 해준다. 왜 그래야만 할까?
만일 2번 이상 나오지 않은 조합이라면 그 이후의 조합도 2번이상 나오지 않기 때문이다.
예를 들어 문제의 첫 번째 예제 케이스를 살펴보자.
orders [ "ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH" ], course [ 2,3,4 ] 이다.
만일 현재 만든 조합(selectedMenus)가 "A", "B"라고 해보자.
orders에서 selectedMenus가 속하는 조합은 "ABCFG" 1개 밖에 없다.
여기에 "C"를 넣는다고 해서 조합의 개수가 1개보다 더 커질 수는 없다.
오히려 경우에 따라서는 포함되는 조합의 개수가 줄어들 것이다.
따라서 이에 관한 경우는 더 이상 조합을 찾지 않도록 만든다.
selectedMenus가 2곳 이상 포함되고 크기가 key에 해당한다면 답의 후보가 될 수 있다.
map에서 key에 해당하는 List< Course>를 불러온다.
불러온 List에 있는 Course와 현재 후보가 될 수 있는 Course의 occurrences를 비교한다.
만일, 현재 조합의 occurrences가 List 안에 있는 occurrences 보다 크다면,
List를 비우고 새로운 Course 객체를 집어 넣는다.
하지만 occurrences의 크기가 같다면 둘 다 정답 후보이므로 새로운 Course를 List에 추가한다.
당연히 새로운 조합의 occurrences가 이전보다 작다면 정답 후보가 아니므로 무시한다.
아까 NPE를 피하려고 더미 Course 데이터를 넣어줬다고 했다.
그 부분은 Course original = courseList.get(0)에 해당한다.
이 부분은 본인의 방식에 맞게 바꿔도 상관 없을 거라 생각한다.
그리고 그 다음 if문에서 size가 10 이상인지 체크하고 있다.
왜냐하면 문제의 조건에서 하나의 코스 조합의 길이가 2이상 10이하이기 때문이다.
이 부분을 체크하지 않는다면 시간초과가 나니 주의하자.
마지막 for문은 재귀문으로 조합을 찾기위해 전형적으로 사용하는 방식이니 설명을 생략하겠다.
답의 형태를 String 배열의 형태로 바꾸는 부분이다.
여기서 주의할 점은 filter 부분이다. 0보다 커야하는 이유는 더미데이터가 들어있을 수 있기 때문이다.
하지만 더미데이터를 사용하지 않는 방법이라면 이 부분은 삭제해도 된다.
여기서 flatMap이 사용되고 있는데, 내 경우에는 IDE의 도움 없이 flatMap을 사용하는게 익숙치 않다.
아마 실전이라면 courses.values()로 for문을 만들어서 Array에 넣었을 거 같다.
여기서 주의할 점은 반드시 sorted() 를 사용해야한다.
왜냐하면 정답 포멧이 문자열의 사전순이기 때문이다.
sorted는 문자열에 관해 Comparator를 구현하지 않으면 기본값으로 사전순으로 정렬한다.
사실 책에는 sorted 때문에 정렬 단원에 포함되어 있는데, 정렬은 거들뿐이라 생각한다..ㅎ
