Programmers 커뮤러닝/3기/JAVA/코딩테스트 실력 UP 패키지 - 1주차_기지국

❤️ github 주소 : https://github.com/qkralswl689/programmers/tree/main/out/production/exercise

1주차_세번째 문제 : Programmers 기지국
https://programmers.co.kr/learn/courses/30/lessons/12979

• 나의 풀이

  전파가 가능한 곳 0으로 표시한 배열을 생성하고, 전파하지 않은 곳을 List에 담아 비교하려했지만
  초반에 기지국이 설치된 곳하고만 비교가 되어서 실패..

    int[] tmp = new int[n];

        for(int i = 0; i < tmp.length; i++){
            tmp[i] = i+1;
        }

        // 전파가능한곳 0 으로 표시
        for(int i = 0; i < stations.length; i++){
            for(int j = 0; j < tmp.length; j++){
                if(stations[i] == tmp[j]){

                    if(tmp[j] == 1 ){
                        tmp[j+w] = 0;
                        break;
                    }else if(tmp[j] == n) {
                        tmp[j-w] = 0;
                        tmp[j] = 0;
                        break;
                    }else {
                        tmp[j+w] = 0;
                        tmp[j-w] = 0;
                    }
                    tmp[j] = 0;
                }
            }
        }

        // 전파하지 않은곳 담기
        ArrayList<Integer> tmp2 = new ArrayList<>();

        for(int i = 0; i < tmp.length; i++){
            if(tmp[i] != 0){
                tmp2.add(tmp[i]);
            }
        }

        for(int i = 0; i < tmp2.size(); i++){
            int k = (tmp2.size() / 2)-1;
            int q = tmp2.get(k);

            if(tmp2.get(k) == q-1){
                answer++;
                break;
            }else if(tmp2.get(k-1) != tmp2.get(k-1) -1){
                int p = tmp2.get(k-1);
                if(tmp2.get(0) == p-1){
                    answer++;
                    break;
                }
            }

            break;

        }

        System.out.println( "answer : " + answer);

        for(int num : tmp2){
            System.out.println(num);
        }

• 나와 비슷하게 푼 사람의 코드

  나와 비슷한 방법으로 문제를 푼 사람의 코드를 참고할 수 있어서 좋았다

 int answer = 0;

        boolean[] apts = new boolean[n+1];
        ArrayList<Integer> noSgn = new ArrayList<>();
        apts[0] = true;
        // 전파 터지는 아파트 표시
        for (int i = 0; i < stations.length; i++) {
            for (int j = stations[i] - w; j <= stations[i] + w; j++) {
                try {
                    apts[j] = true;
                }
                catch (Exception e) {
                    continue;
                }
            }
        }

        // 안 터지는 아파트 구역별 구분
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (!apts[i]) {
                sum += 1;
                // System.out.println(i);
            }
            else if (apts[i] && sum != 0) {
                noSgn.add(sum);
                sum = 0;
            }
            if (i == n && sum != 0) noSgn.add(sum);
        }

        // 답 도출
        for (int i = 0; i < noSgn.size(); i++) {
            answer += (noSgn.get(i) / (w * 2 + 1));
            answer += noSgn.get(i) % (w * 2 + 1) == 0 ? 0 : 1;
        }
        // System.out.println(noSgn.get(i));

• 강사님 풀이

  처음에 Queue 로 문제풀이를 해주셔서 Queue사용법을 배울 수 있어서 좋았고, Queue를 사용했을 때엔 효율성이 떨어져
  인덱스를 사용하는 방법으로 문제풀이를 해주셨다

  // 아파트의 개수
        int n = 11;

        // 기지국이 설치된 아파트의 번호
        int[] stations = {4, 11};

        // 전파의 도달거리
        int w = 1;

        int answer = 0;

        int si = 0; // 스테이션의 인덱스를 사용한다

     /*   // Queue 사용시 효율성 떨어짐
        Queue<Integer> sq = new LinkedList<>();
        for(int s : stations) sq.offer(s);*/

        int position = 1; //

        while (position <=n){ //아파트 전체 돌때까찌

            // 인덱스가 끝까지 가지 않아있을때
            if( si < stations.length && stations[si] - w <= position){

                position = stations[si] + w + 1; //인덱스 번째의 값을 꺼내오고
                si ++; // 인덱스 증가
            }else {// 그렇지 않다면

                answer += 1; // 기지국 설치
                position += w + 1 + w; // 최대 전파범위(왼) + 현재위치 + 최대 전파범위(오)
                // -> 전체 전파범위 == w * 2 + 1

            }

        }

        // queue 사용시
      /*  while (position <=n){ //아파트 전체 돌때까찌

            // Queue 가 비어있지 않은것 체크
           if( !sq.isEmpty() && sq.peek() - w <= position){ // 현재 있는곳이 기지국이 있는곳의 왼쪽끝 전파범위  보다 현재위치가 오른쪽이라면 기지국의 전파범위 안에 있는것이면

               position = sq.poll() + w + 1; // 위치는 기지국의 전파범위 오른쪽 끝의 다음위치로 간다

           }else {// 그렇지 않다면

               answer += 1; // 기지국 설치
               position += w + 1 + w; // 최대 전파범위(왼) + 현재위치 + 최대 전파범위(오)
               // -> 전체 전파범위 == w * 2 + 1

           }

        }