[BOJ] 백준 15663 N과 M(9) (JAVA)

맛있는 문제.

📑 문제

 

백준 15663 N과 M(9)

---

🌱 아이디어

입력된 숫자의 모든 경우의 조합 중 중복 제거 + 사전순 정렬!

 

이 문제를 풀 때 모든 경우의 수를 HashSet에 넣고 정렬을 한다면 중복제거 + 사전순 출력으로 될 줄 알았다.

 

일단 필자는 문자열로 처리했고 문자열 정렬을 했다 하지만 제대로 정렬되지 않았다.

 

입력을 String 으로 받았을때

 

숫자를 문자열로 입력받고 Arrays.sort를 하면 제대로 정렬되지 않는다.

그 이유는 "숫자의 사전순 정렬"과 "문자열의 사전순 정렬"의 개념이 다르다, 필자는 제대로 몰랐다.;;

 

입력값 = 100, 20 오름차순 정렬 시

 

숫자의 사전순 정렬 은 20 < 100 임으로  출력은 20 100이다.

문자열의 사전순 정렬 은 20의 "2" 보다 100의 "1"이 사전 순으로 먼저이다. 즉 숫자 자체는 100이 크지만

문자열 정렬 시 우선순위는 "2"보다 작은 "1", 출력은 100 20 순으로 정렬된다

 

위의 경우를 헷갈리지 않는다면 쉽게 문제를 풀 수 있다... 개념을 다시 잡을 수 있는 좋은 문제였다 ㅎㅎ

---

🌱 코드 및 풀이

재귀적으로 모든 경우의 수를 만들고 HashMap에 저장하고 중복된 결과가 있다면 ArrayList에 저장하지 않는다.

dfs함수 실행 전 숫자를 정렬한다면 dfs 결과 값도 자연스럽게 정렬된다.

---

🌱 느낀 점

숫자의 정렬과 문자의 정렬에 대해 다시 한번 생각해 볼 수 있는 좋은 문제였다 다른 알고리즘을 배우다 보면 

사소한 부분 또는 자주 사용 안 하는 부분은 깊게 생각 안 하게 되는데 이 문제는 그러한 단점을 보완할 수 있는 좋은 문제이다.

덕분에 개념을 다잡을 수 있었다 ㅎㅎ