프로그래머스 - 위클리 챌린지 7주차

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

코딩테스트 연습 - 7주차

 

• 단순한 구현 같은데 생각보다 잘 안풀렸던 문제
• 결국 n^3으로 풀었는데 다른 사람 풀이를 보니 n^2으로도 쉽게 풀렸던 문제
• 덕분에 나의 통과 속도는 그들에 비해 최대 100배 정도 느리게 돌아갔다 ㅡ 
• 시간 제한이 빡세게 걸려있었다면 통과 못했을 텐데 다른 사람 정답을 보고 연구 좀 해봐야겠다 ㅠㅠ

 

테스트 1 〉	통과 (1.63ms, 69.7MB)
테스트 2 〉	통과 (1.77ms, 72.3MB)
테스트 3 〉	통과 (1.58ms, 68MB)
테스트 4 〉	통과 (3.69ms, 59.3MB)
테스트 5 〉	통과 (3.27ms, 59.8MB)
테스트 6 〉	통과 (10.41ms, 59.4MB)
테스트 7 〉	통과 (4.99ms, 62.2MB)
테스트 8 〉	통과 (9.40ms, 59.6MB)
테스트 9 〉	통과 (17.42ms, 73.4MB)
테스트 10 〉	통과 (90.49ms, 72.9MB)
테스트 11 〉	통과 (204.15ms, 78.5MB)
테스트 12 〉	통과 (429.96ms, 120MB)
테스트 13 〉	통과 (1.48ms, 74MB)
테스트 14 〉	통과 (1.47ms, 58.7MB)
테스트 15 〉	통과 (1.38ms, 73MB)
테스트 16 〉	통과 (1.93ms, 76.9MB)
테스트 17 〉	통과 (1.50ms, 59.5MB)
테스트 18 〉	통과 (2.08ms, 73.1MB)
테스트 19 〉	통과 (2.03ms, 73.5MB)
테스트 20 〉	통과 (1.69ms, 72.1MB)
테스트 21 〉	통과 (17.10ms, 74.8MB)
테스트 22 〉	통과 (20.40ms, 77.1MB)
테스트 23 〉	통과 (11.29ms, 64.3MB)
테스트 24 〉	통과 (430.70ms, 110MB)
테스트 25 〉	통과 (458.24ms, 96.5MB)
테스트 26 〉	통과 (2697.10ms, 227MB)
테스트 27 〉	통과 (2518.06ms, 191MB)
테스트 28 〉	통과 (1.42ms, 58.9MB)
테스트 29 〉	통과 (4.95ms, 74.5MB)
테스트 30 〉	통과 (16.69ms, 72.6MB)
테스트 31 〉	통과 (64.27ms, 86.7MB)
테스트 32 〉	통과 (246.49ms, 77.9MB)
테스트 33 〉	통과 (1626.00ms, 175MB)
테스트 34 〉	통과 (1839.80ms, 173MB)
테스트 35 〉	통과 (2.78ms, 71MB)
테스트 36 〉	통과 (5.92ms, 73.2MB)
테스트 37 〉	통과 (0.05ms, 70.4MB)

 

 

import java.util.*;

class Solution {
        public int[] solution(int[] enter, int[] leave) {
            int[] answer = new int[enter.length];

            int maxIndex = 0;
            for (int i = 0; i < leave.length; i++) {

                List<Integer> shouldLeave = new ArrayList<>();
                int index = findIndex(enter, leave, leave[i]);
                maxIndex = Math.max(maxIndex, index);

                // 나간 사람은 뺀다
                for (int j = 0; j < i; j++) {
                    shouldLeave.add(leave[j]);
                }

                //만날 수도있는 사람 수
                for (int j = 0; j < maxIndex; j++) {
                    final int meetIndex = j;
                    Optional<Integer> any = shouldLeave.stream()
                            .filter(o -> o == enter[meetIndex])
                            .findAny();

                    if (any.isEmpty() && (leave[i] != enter[j])) {
                        //System.out.printf("%d %d\n", leave[i], enter[j]);

                        answer[leave[i] - 1] += 1;
                        answer[enter[j] - 1] += 1;
                    }
                }
            }

            return answer;
        }

        private int findIndex(int[] enter, int[] leave, int target) {
            for (int i = 0; i < enter.length; i++) {
                if (target == enter[i]) {
                    return i;
                }
            }
            return -999;
        }
    }