프로그래머스. 다단계 칫솔 판매

https://programmers.co.kr/learn/courses/30/lessons/77486

코딩테스트 연습 - 다단계 칫솔 판매

 

기록해 놓고싶은점: 

처음에 이름, 부모의 포인터를 갖는 구조체를 선언하고 벡터에 넣으면서 부모의 포인터로 연결했는데 

자꾸 이상한 값이 출력됐다.

이건 아마도 벡터에 값을 넣다가 벡터가 초기에 할당한 메모리를 넘어서서 재할당하면서 주소값이 변경되면서 생긴 문제인것 같다.

벡터에 모든 사람을 먼저 푸쉬해놓고 그 이후에 다시 반복문을 돌면서 부모의 주소값을 할당해줬더니 정상적으로 출력.

(그런데 결국 풀다보니 이 문제에서 벡터는 필요없었다)

 

1. 해당하는 인원의 이름, 벌어들인 돈, 부모의 포인터를 갖는 구조체를 갖는 Tree 구조체를 선언한다.

2. unordered_map<string, Tree>를 선언하고, enroll 벡터를 돌면서 할당한다.

 

• enroll 에 등장하는 이름은 조직에 참여한 순서에 따릅니다.
• 즉, 어느 판매원의 이름이 enroll 의 i 번째에 등장한다면, 이 판매원을 조직에 참여시킨 사람의 이름, 즉 referral 의 i 번째 원소는 이미 배열 enroll 의 j 번째 (j < i) 에 등장했음이 보장됩니다.

 

위 조건에 의해 enroll[i]의 부모는 이미 unordered_map에 할당이 됐음이 보장된다.

 

3. seller 벡터를 돌면서 번돈을 재귀적으로 계산한다.

   부모가 없는 인원을 만나면 리턴.

   또한 넘겨 받은 돈이 0원 이여도 리턴한다. (안할시 시간초과) 

 

 

다른 분들 코드를 봤는데 생각해보니 딱히 복잡하게 구조체를 쓸필요는 없었다.

그냥 트리 그림이 보여서 그쪽으로 생각이 쏠린듯.