다단계 칫솔 판매

오늘은 프로그래머스에 있는 레벨3 다단계 칫솔 판매 문제를 풀어보았다. 전에도 풀어봤던 문제였지만 처음시도했을때는 정말 대참사였다. DFS를 이용해서 문제를 풀려고 했었고 테스트 케이스까지는 성공했지만 더 많은 테스트 케이스가 추가 되었을때는 감당도 못하고 코드가 터졌었다. 그러던중 발견한 Union Find 알고리즘은 나름 신세계인거같다. 이런 식에 피라미드 형태의 문제에서 조상을 찾아야하는 방법을 이용하는 이 알고리즘은 문제를 풀기에 최고로 적합했다.

원래 Union Find 알고리즘의 기초는 초기에는 자기 자신을 조상이라는 조건하에 문제를 읽으면서 진짜 조상들을 업데이트 시켜주는 작업이 있지만 문제에는 이미 누가 누구의 조상인지 나와 있어씨에 referral 과 enroll 관계를 업데이트 했다. 후에는 update() 라는 함수를 이용해서 조상을 타고 올라가며 문제에 맞게 한 사람이 가질수있는 돈의 양을 amountUpdate 라는 맵에다가 저장을 했다. 문제를 풀면서 느낀건데 내가 문제를 정말 잘 읽고 이해했다면 훨씬 쉬웠을거라는 생각을했다. 실수를 했던거로는 10%의 값이 1 미만일때 return 을 안적어줬더니 시간초과가 났었고 pay라는 변수를 따로 설정안하고 그냥 (money * 0.1) 로만 적었더니 숫자가 다르게 나왔었다. 이런 자잘한 실수는 진짜 줄여나가야겠다.

배우점:
1. UnionFind의 제대로된 활용법
2. 문제를 정말 잘읽자 라는 생각