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

Algorithm

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

robinjoon98 2021. 8. 25. 14:19

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

민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후,

programmers.co.kr

문제를 간단히 설명하면, 이 조직은 민호와 판매원으로 이루어져있는데, 각 판매원은 자신을 조직에 추천한 사람들과 연결되어 피라미드 구조를 가진다. 이 피라미드의 정점에는 민호가 있다. 각 판매원은 칫솔을 판매해서 발생한 수익의 10%를 자신을 조직에 추천한 사람에게 주고, 나머지를 자신이 가진다. 단, 10%를 계산할 때 원단위 이하는 버리고, 10%가 1원 미만이라면 수익은 모두 판매원이 가진다.

이 상황에서 각 판매원의 이름을 담은 배열 enroll, 각 판매원을 다단계 조직에 참여시킨 다른 판매원의 이름을 담은 배열 referral, 판매량 집계 데이터의 판매원 이름을 나열한 배열 seller, 판매량 집계 데이터의 판매 수량을 나열한 배열 amount 가 주어졌을 때, 각 판매원의 수익을 담은 배열을 반환하는 함수를 작성하는 것이다.

문제의 제한사항은 아래와같다.

enroll의 길이는 1 이상 10,000 이하입니다.
enroll에 민호의 이름은 없습니다. 따라서 enroll의 길이는 민호를 제외한 조직 구성원의 총 수입니다.
referral의 길이는 enroll의 길이와 같습니다.
referral 내에서 i 번째에 있는 이름은 배열 enroll 내에서 i 번째에 있는 판매원을 조직에 참여시킨 사람의 이름입니다.
어느 누구의 추천도 없이 조직에 참여한 사람에 대해서는 referral 배열 내에 추천인의 이름이 기입되지 않고 “-“ 가 기입됩니다. 위 예제에서는 john 과 mary 가 이러한 예에 해당합니다.
enroll 에 등장하는 이름은 조직에 참여한 순서에 따릅니다.
즉, 어느 판매원의 이름이 enroll 의 i 번째에 등장한다면, 이 판매원을 조직에 참여시킨 사람의 이름, 즉 referral 의 i 번째 원소는 이미 배열 enroll 의 j 번째 (j < i) 에 등장했음이 보장됩니다.
seller의 길이는 1 이상 100,000 이하입니다.
seller 내의 i 번째에 있는 이름은 i 번째 판매 집계 데이터가 어느 판매원에 의한 것인지를 나타냅니다.
seller 에는 같은 이름이 중복해서 들어있을 수 있습니다.
amount의 길이는 seller의 길이와 같습니다.
amount 내의 i 번째에 있는 수는 i 번째 판매 집계 데이터의 판매량을 나타냅니다.
판매량의 범위, 즉 amount 의 원소들의 범위는 1 이상 100 이하인 자연수입니다.
칫솔 한 개를 판매하여 얻어지는 이익은 100 원으로 정해져 있습니다.
모든 조직 구성원들의 이름은 10 글자 이내의 영문 알파벳 소문자들로만 이루어져 있습니다.

문제에 피라미드 구조, 즉 트리구조가 등장한다. 이 때문에 DFS, BFS 같은게 떠올랐지만, 이 문제는 이런 그래프알고리즘과 무관하다. 이 문제는 판매자(트리의 한 노드)가 주어졌을때 그 판매자를 추천한 추천인(부모노드)와 그를 추천한 추천인(부모노드의 부모노드)... 로 이루어지는 리스트(이하 "부모리스트" 라한다.)내에서만 연산이 수행되기 때문이다. 즉, 모든 노드에대해 부모리스트를 만들고, 이들을 저장해두었다가, seller 배열의 각 원소로 시작되는 부모리스트를 골라 수익연산을 시행하면 된다.

자바에서 이를 아래 코드로 구현했다. Map 을 만들고 Key 로 String(판매원이름), Value로 Key의 부모리스트를 가지게 했다. enrollMap 은 String 이 enroll 배열의 몇번째 원소인지 구하는 연산을 줄이기 위해 판매원이름 - 배열내인덱스 로 구성한 Map이다.

Map<String,List<String>> map = new HashMap<String, List<String>>();
Map<String,Integer> enrollMap = new HashMap<String, Integer>();
for(int i=0;i<enroll.length;i++)
    enrollMap.put(enroll[i],i);
    for(int i=0;i<enroll.length;i++) {
    List<String> list = new ArrayList<>();
    int index = i;
    list.add(enroll[index]);
    while(true) {
        if(referral[index].equals("-")) {
            break;
        }else {
            list.add(referral[index]);
            index = enrollMap.get(referral[index]);
        }
    }
    map.put(enroll[i], list);
}

그리고 아래 코드는, 방금 만든 부모리스트들을 이용해 연산을 실행하는 코드다. ret는 반환할 배열이다.

for(int i=0;i<seller.length;i++) {
    amount[i]*=100;
    String name = seller[i];
    List<String> list = map.get(name);
    int total = amount[i];
    int money = total - (int)(amount[i]*0.1);
    for(int j=0;j<list.size();j++) {
        int index = enrollMap.get(list.get(j));
        ret[index] +=money;
        total = total - money;
        money = total - (int)(total *0.1);
        if(money==0) 
            money = total;
    }
}
return ret;

아래는 합친 코드다.

import java.util.*;

public class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        Map<String,List<String>> map = new HashMap<String, List<String>>();
        Map<String,Integer> enrollMap = new HashMap<String, Integer>();
        for(int i=0;i<enroll.length;i++)
        enrollMap.put(enroll[i],i);
            for(int i=0;i<enroll.length;i++) {
            List<String> list = new ArrayList<>();
            int index = i;
            list.add(enroll[index]);
            while(true) {
                if(referral[index].equals("-")) {
                    break;
                }else {
                    list.add(referral[index]);
                    index = enrollMap.get(referral[index]);
                }
            }
            map.put(enroll[i], list);
        }
        for(int i=0;i<seller.length;i++) {
            amount[i]*=100;
            String name = seller[i];
            List<String> list = map.get(name);
            int total = amount[i];
            int money = total - (int)(amount[i]*0.1);
            for(int j=0;j<list.size();j++) {
                int index = enrollMap.get(list.get(j));
                ret[index] +=money;
                total = total - money;
                money = total - (int)(total *0.1);
                if(money==0) 
                    money = total;
            }
        }
        return ret;
    }
}

이 코드를 제출하면, 1~9 번째 테스트케이스는 짧은 시간에 통과하고, 10번은 비교적 오래걸리며, 11 ~ 13번은 시간초과가 뜬다. 이를 해결하기 위해 다시 분석해보았다.

일단, 부모리스트에 많은 중복이 발생한다. 문제에서 주어진 예시를 이용해 설명하겠다.

문제 예시. 출처 https://programmers.co.kr/learn/courses/30/lessons/77486

이 상황에서 내 코드가 실행되면 sam - edward - mary 로 이어지는 List가 생긴다. 그리고, edward - mary 리스트도 생기게 된다. edward - mary 리스트는 이미 sam - edward - mary 리스트의 부분이므로 없어도 연산수행이 가능하다. 판매원 수가 많아지고 복잡해지면 많은 중복이 발생할 것이다. 이를 해결하기 위해 추가적인 클래스를 작성하였다.

private class Person{
        private Person referral;
        private String name;
        private int money;

        public Person(String name) {
            super();
            this.name = name;
            this.money = 0;
        }
        public Person getReferral() {
            return referral;
        }
        public void setReferral(Person referral) {
            this.referral = referral;
        }
        @Override
        public boolean equals(Object o) {
            if(o.equals(this.name)) {
                return true;
            }else return false;
        }
        @Override
        public int hashCode() {
            return this.name.hashCode();
        }
        @Override
        public String toString() {
            return "Person [referral=" + referral + ", name=" + name + ", money=" + money + "]";
        }
    }

Person 의 인스턴스들은, 자신을 추천한 Person을 필드로 가진다. 즉, 일종의 연결리스트가 된다.

그리고 이 Person인스턴스들을 Map에 저장하여, 연결리스트의 중간으로 바로 갈 수 있게 해주었다. 그 외의 로직들은 모두 먼저 코드와 같다. 아래는 새로 작성한 코드다.

import java.util.*;

public class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] ret = new int[enroll.length];
        Map<String,Integer> enrollMap = new HashMap<String, Integer>();
        Map<String,Person> personMap = new HashMap<String, Solution.Person>();
        for(int i=0;i<enroll.length;i++)
            enrollMap.put(enroll[i],i);
        for(int i=0;personMap.size()<enroll.length;i++) {
            int index = i;
            if(personMap.get(enroll[i])!=null)continue;
            Person person = new Person(enroll[i]);
            personMap.put(enroll[i],person);
            while(true) {
                if(referral[index].equals("-")) {
                    break;
                }else {
                    if(personMap.get(referral[index])==null) {
                        Person ref = new Person(referral[index]);
                        person.setReferral(ref);
                        personMap.put(referral[index],ref);
                    }else if(person.referral==null){
                        person.setReferral(personMap.get(referral[index]));
                    }
                }
                index = enrollMap.get(referral[index]);
            }
        }
        for(int i=0;i<seller.length;i++) {
            amount[i]*=100;
            String name = seller[i];
            Person person = personMap.get(name);
            int total = amount[i];
            int money = total - (int)(amount[i]*0.1);
            while(person.getReferral()!=null) {
                int index = enrollMap.get(person.name);
                ret[index] +=money;
                total = total - money;
                money = total - (int)(total *0.1);
                if(money==0) 
                    money = total;
                person = person.getReferral();
            }
            int index = enrollMap.get(person.name);
            ret[index] +=money;
            total = total - money;
            money = total - (int)(total *0.1);
            if(money==0) 
                money = total;
            person = person.getReferral();
        }
        return ret;
    }
    private class Person{
        private Person referral;
        private String name;
        private int money;

        public Person(String name) {
            super();
            this.name = name;
            this.money = 0;
        }
        public Person getReferral() {
            return referral;
        }
        public void setReferral(Person referral) {
            this.referral = referral;
        }
        @Override
        public boolean equals(Object o) {
            if(o.equals(this.name)) {
                return true;
            }else return false;
        }
        @Override
        public int hashCode() {
            return this.name.hashCode();
        }
        @Override
        public String toString() {
            return "Person [referral=" + referral + ", name=" + name + ", money=" + money + "]";
        }
    }
}

이 코드를 제출하면 아까보다 약 10% 더 빨라지긴 한다. 그러나, 여전히 11 ~ 13번은 통과하지 못한다.

위에서 생각한 중복이 생각보다 큰 영향을 주지 못하나보다. 이제 성능향상을 볼 수 있는 부분은 수익을 계산하는 부분이다. 코드를 다시 보자.

for(int i=0;i<seller.length;i++) {
    amount[i]*=100;
    String name = seller[i];
    Person person = personMap.get(name);
    int total = amount[i];
    int money = total - (int)(amount[i]*0.1);
    while(person.getReferral()!=null) {
        int index = enrollMap.get(person.name);
        ret[index] +=money;
        total = total - money;
        money = total - (int)(total *0.1);
        if(money==0) 
            money = total;
            person = person.getReferral();
        }
        int index = enrollMap.get(person.name);
        ret[index] +=money;
        total = total - money;
        money = total - (int)(total *0.1);
        if(money==0) 
            money = total;
            person = person.getReferral();
    }
}

만약, 트리가 아주 깊다면 위 코드의 while 문이 아주 많이 반복될 것이다. 그런데, 문제에서 수익은 고작 10%가 부모노드로 전달된다. 따라서, 트리가 아주 깊은 경우, 트리의 한참 아래쪽에서 이미 자식노드로부터 전달받은 수익이 1원미만이 되게된다. 그러나 위 코드는 이를 전혀 고려하지 않았다. 따라서 while문 내부에 total = 0일때 빠져나오게끔 하면 효율을 향상시킬 수 있다. 아래는 이를 반영한 코드다.

import java.util.*;

public class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] ret = new int[enroll.length];
        Map<String,Integer> enrollMap = new HashMap<String, Integer>();
        Map<String,Person> personMap = new HashMap<String, Solution.Person>();
        for(int i=0;i<enroll.length;i++)
            enrollMap.put(enroll[i],i);
        for(int i=0;personMap.size()<enroll.length;i++) {
            int index = i;
            if(personMap.get(enroll[i])!=null)continue;
            Person person = new Person(enroll[i]);
            personMap.put(enroll[i],person);
            while(true) {
                if(referral[index].equals("-")) {
                    break;
                }else {
                    if(personMap.get(referral[index])==null) {
                        Person ref = new Person(referral[index]);
                        person.setReferral(ref);
                        personMap.put(referral[index],ref);
                    }else if(person.referral==null){
                        person.setReferral(personMap.get(referral[index]));
                    }
                }
                index = enrollMap.get(referral[index]);
            }
        }
        for(int i=0;i<seller.length;i++) {
            amount[i]*=100;
            String name = seller[i];
            Person person = personMap.get(name);
            int total = amount[i];
            int money = total - (int)(amount[i]*0.1);
            while(person.getReferral()!=null) {
                int index = enrollMap.get(person.name);
                ret[index] +=money;
                total = total - money;
                money = total - (int)(total *0.1);
                if(money==0) 
                    money = total;
                if(total==0)break;
                person = person.getReferral();
            }
            int index = enrollMap.get(person.name);
            ret[index] +=money;
            total = total - money;
            
            money = total - (int)(total *0.1);
            if(money==0) 
                money = total;
            person = person.getReferral();
        }
        return ret;
    }
    private class Person{
        private Person referral;
        private String name;
        private int money;

        public Person(String name) {
            super();
            this.name = name;
            this.money = 0;
        }
        public Person getReferral() {
            return referral;
        }
        public void setReferral(Person referral) {
            this.referral = referral;
        }
        @Override
        public boolean equals(Object o) {
            if(o.equals(this.name)) {
                return true;
            }else return false;
        }
        @Override
        public int hashCode() {
            return this.name.hashCode();
        }
        @Override
        public String toString() {
            return "Person [referral=" + referral + ", name=" + name + ", money=" + money + "]";
        }
    }
}

저작자표시 동일조건

'Algorithm' 카테고리의 다른 글

[백준] 1074번 Z (0)	2021.09.25
[프로그래머스] 오픈채팅방 (0)	2021.08.30
[CodeGround] Practice - 미궁 속의 방 (0)	2021.07.28
[SCPC 2021] 친구들 (0)	2021.07.26
백준 2579 계단 오르기 (0)	2021.07.26

현재글[프로그래머스] 다단계 칫솔 판매

흔한 휴학생이 개발 공부한거 정리하는 블로그.

깃허브 액션, 코드그라운드, Spring CORS 설정 안먹힘, 클린코드, 백준, 스프링, 스프링 공식문서 번역, 추상화, 코드사인, 전자서명, 스프링 입문을 위한 자바 객체지향의 원리와 이해, 인터셉터와 CORS, 토이프로젝트, string, 자바 문법, 알고리즘, 자바, 객체지향, 객체지향의 사실과 오해, 객체,

Today :
Yesterday :

robinjoon의 개발이야기