[알고리즘풀이]백준 14267: 회사 문화 1 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 14267번 회사 문화1을  풀었습니다. 이를 정리해보고자 합니다.

14267번: 회사 문화 1

 

본문

1) 문제

2) 과정

이번 문제는 1시간 30분 정도 걸려서 풀었어요. 아이디어는 빨리 나왔지만 시간초과 때문에 고전했던,,, 문제입니다.

 

제가 문제를 풀며 사용했던 아이디어는 다음과 같습니다.

 1. 인덱스 별 상사를 읽을 때, 탐색 개선을 위해 HashSet으로 [상사(입력값)].add(부하(for인덱스))을 empArr에 넣어 직원 간의 연결을 만든다.
 2. 각 사람들이 직접 받은 칭찬을 meritArr에 담아 시간초과가 발생할 불상사를 피하고(에러로그 확인..)
 3. 1(사장)부터 dfs탐색을 하며 meritArr에 칭찬값들을 누적시켜나간다.
 4. meritArr의 값들을 형식에 맞게 가공하여 출력한다.

 

시간초과 19%의 늪에 빠졌었는데... 이를 해결하는 과정은 맨 아래있는 깃헙링크를 확인해주세요... 맞춘 이후의 개선과정도 담아뒀답니다 :)

 

main에 대부분의 내용이 들어있습니다. 그렇지만 코테 문제들은 거의다 값을 받는 Input, 값을 계산하는 Logic, 값을 출력하는 Output으로 구성되니 해당 구성에 맞게 부분들을 나눠 보여드리겠습니다!

2-1) Input

        // Input
        // input basic info
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        // initialize
        empArr = new HashSet[n+1]; // 각 사람들의 부하를 담을 배열
        meritArr = new int[n+1]; // 각 사람들이 받은 칭찬을 담을 배열
        
        // connect employees
        st = new StringTokenizer(br.readLine());
        for(int i=1;i<=n;i++){
            empArr[i] = new HashSet<>();
            int input = Integer.parseInt(st.nextToken());
            if(input>0) empArr[input].add(i);
        }
        
        // combine the merits of each employee
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int emp = Integer.parseInt(st.nextToken());
            int merit = Integer.parseInt(st.nextToken());
            meritArr[emp] += merit;
        }

n과 m을 입력받아 각 사람들의 부하를 담을 배열인 empArr과 각 사람들이 받은 칭찬을 담을 배열인 meritArr을 만들어줍니다. 그리고 employee들의 관계를 연결해주고 각 employee들의 칭찬 값을 미리 받아둬 후에 로직에서 계산하도록 하여 최상위 상사가 여러번 칭찬을 받았을때 전체를 여러번 탐색하는 낭비를 줄입니다.

 

2-2) Logic 

    // Logic
    public static void main(String[] args) throws IOException{
      	// adding merit point
      	addMerit(1);
    }
    // Method - merit을 더해나가는 함수
    private static void addMerit(int cur){
        for(int e : empArr[cur]){
            meritArr[e] += meritArr[cur];
            addMerit(e);
        }
    }

최상위 상사인 1부터 각 직원들의 칭찬점수를 누적시켜 부하들에게 칭찬점수를 더해주며 내려갑니다 

 

2-3) Output 

        // Output
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=n;i++) sb.append(meritArr[i]+" ");
        System.out.println(sb.toString());

그동안 meritArr에 모든 각 직원들의 칭찬점수를 차례대로 출력해줍니다.

 

 

3) 전체코드

그렇게 완성된 코드는 아래쪽에 링크된 깃헙 레포짓토리에 방문하여 확인해주세요!

앞서 말씀드렸듯이 소요시간, 아이디어, 에러로그 등 더 자세히 보실 수 있습니다.

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/tree/BOJ14267.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비