모각코 내부스터디 PS / 백준 1449번 - 수리공 항승

모각코 내부스터디 PS

어제는 따로 모이는 날은 아니었는데 다들 라운지에 계셔서 놀러가봤다. 문제를 막 풀려고 하시던 참이라고 해서 나도 껴서 한 문제 풀어보았다. 그 문제를 정리해보려고 한다.

문제 링크 : 백준 1449번 - 수리공 항승

처음은 문제를 보고나서 의식의 흐름대로 대충 풀어보았고, 다음날 아침(오늘) 리팩토링 해보았다.
그리고 어제 함께 문제 풀었던, 모각코 스터디 대장님의 코드를 보면서 생각해보니, 모든 케이스에 선형시간이 걸리게 풀 필요가 없단 걸 깨달았다. 역시 대장님...!!이라고 생각을 하면서... 또 한번 코드를 고쳐보았다.
아이디어를 제시해주셔서 감사드립니당. ( - -)( _ _)
(너그럽게 표기도 허락해주셨다!)

첫번째 풀이

---

👇너무 의식의 흐름이라 접어놨다...

귀찮음이 곳곳에 묻어나는 코드다(사이즈 1000짜리 배열...ㅋㅋㅋ..)
처음 풀 때 가장 어려웠던 건, 문제를 읽는 거였다. 무슨 뜻인지 이해를 못해서 한참 고민했다 ;;

주요 로직은,
파이프(배열)를 만들어놓고, 구멍을 체크(해당 인덱스에 true 값 입력)한 뒤에, 파이프를 쭉 훝으며 처리한다.

어차피 sorting을 한 번 해야 하기 때문에(O(nlogn)), 주요 로직(파이프를 쭉 훑는 것)에 O(n)이 걸리는 건 상관없다고 생각했다.
'어차피 nlogn이니까, 나중에 보기만 좋게 좀 수정하지 뭐~' 라고 생각했던 것 같다.

import java.util.Arrays;
import java.util.Scanner;

public class Ps {
    public static void main(String[] args) {

        //상황 설정 시작---
        int count = 0;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // n: 빵꾸 갯수
        int m = sc.nextInt(); // m: 테이프 미터(길이)
        sc.nextLine();


        boolean[] pipe = new boolean[1000]; // 파이프

        int[] ns = new int[n]; //빵꾸들 위치 저장용
        for (int i = 0; i < n ; i++) {
            ns[i] = sc.nextInt();
            pipe[ns[i]] = true; //빵꾸는 true로 체크해둔다.
        }
        //---상황 설정 끝


        /*
        시나리오:
        파이프 왼쪽부터 쭉 가.
        쭉 가다가 빵꾸를 만나.
        그러면 거기부터 m-1미터 안은 전부 메꾸고 보는거야
        그럼 또 진행해. 연달아메꿔진거는 안걸리겠지?
        쭉가.
        마지막 빵꾸까지만 메꿔졌는지 확인하면 되니까, 거기 위치까지 확인하면서 가.
        다 갔어? 그럼 됐네.

        아 테이프 갯수 세야되니까 빵꾸를 만날때마다 카운트.
        * */

        Arrays.sort(ns); //아 빵꾸가 순서대로라는 보장이 없구나

        for (int i = 0; i <= ns[ns.length - 1]; i++) { //쭉 가다가 ~ 마지막빵꾸까지
            if (pipe[i] == true) { // 빵꾸를 만나
                for (int j = i; j <= i+m-1; j++) {
                    pipe[j] = false;
                }
                count++;
            }
        }

        System.out.println(count);

    }
}

두번째 풀이

---

👇너무 의식의 흐름이라 접어놨다22...

주요 로직은 같다. 배열 크기 정리한 정도...?(무조건 1000 -> 마지막 구멍 지점까지)

import java.util.Arrays;
import java.util.Scanner;

public class Ps {
    public static void main(String[] args) {

        //상황 설정 시작---
        //  입력부 시작------
        int count = 0;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // n: 빵꾸 갯수
        int m = sc.nextInt(); // m: 테이프 미터(길이)
        sc.nextLine();
        int[] ns = new int[n]; //빵꾸들 위치 저장용
        for (int i = 0; i < n ; i++) ns[i] = sc.nextInt();
        //  ------입력부 끝

        Arrays.sort(ns); // 구멍의 위치 정보를 왼쪽(1)부터 마지막(n)까지 순서대로 나열
        boolean[] pipe = new boolean[ns[ns.length - 1] + 1]; //파이프 정보 배열 (마지막 구멍 위치까지만 기록, [0]은 편의상 무시)
        for (int in : ns) pipe[in] = true; // 구멍난 부분 체크해둔다(true)
        //---상황 설정 끝

        /*
        시나리오:
        파이프 왼쪽부터 쭉 가.
        쭉 가다가 빵꾸를 만나.
        그러면 거기부터 m-1미터 안은 전부 메꾸고 보는거야
        그럼 또 진행해. 연달아메꿔진거는 안걸리겠지?
        쭉가.
        마지막 빵꾸까지만 메꿔졌는지 확인하면 되니까, 거기 위치까지 확인하면서 가.
        다 갔어? 그럼 됐네.

        아 테이프 갯수 세야되니까 빵꾸를 만날때마다 카운트.
        * */

        for (int i = 1; i <= ns[ns.length - 1]; i++) { // 쭉 가다가 ~ 마지막빵꾸까지
            if (pipe[i] == true) { // 빵꾸를 만나면
                for (int j = i; j <= i+m-1; j++) { // 구멍난 지점에서부터 테이프 길이만큼
                    pipe[j] = false; // 쭉 떼운다
                }
                count++; //테이프 한번 썼으니까 카운트 한다
                i += m; //떼운 부분은 다시 체크할 필요 없으니 건너뛴다
            }
        }

        System.out.println(count);

    }
}

세번째 풀이

---

👇아이디어를 얻어서 고친 코드

sorting이 필요 없는 케이스에는 상수시간으로 처리할 수가 있다.
sorting이 필요없는 경우인지 체크하는 isSequantial 변수를 추가했고,
실제 메꾸는 작업이 필요한 게 아니라, 테이프 갯수만 세면 되기 때문에 pipe 배열은 없앴다.

import java.util.Arrays;
import java.util.Scanner;

public class Ps {
    public static void main(String[] args) {
        //상황 설정 시작---
        int count = 0;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // n: 빵꾸 갯수
        int m = sc.nextInt(); // m: 테이프 미터(길이)
        sc.nextLine();
        boolean isSequantial = true; // 구멍 위치를 순차적으로 입력중이니?
        int[] ns = new int[n]; //빵꾸들 위치 저장용
        for (int i = 0; i < n ; i++) { //순차적인지 확인하는 loop
            int nowN = sc.nextInt();
            if (isSequantial && i > 0) isSequantial = ns[i - 1] < nowN ? true : false;
            ns[i] = nowN;
        }
        if (!isSequantial) Arrays.sort(ns); // 구멍의 위치 정보를 왼쪽(1)부터 마지막(n)까지 순서대로 나열; 순서대로가 아닐 때에만
        //---상황 설정 끝


        /*
        * 새로운 아이디어: 꼭 파이프를 훑을 필요 없다. 세어만 보면 되니까.
        */
        int cnt = 0;        // 몇개 썼나
        int tapeTail = 0;   // 현재 테이프의 끝지점(마지막으로 가려주는 위치)
        for (int nowN : ns) {           // 구멍 위치를 하나씩 확인하며
            if (nowN > tapeTail) {      // '테이프로 메꿔진 마지막 구멍(위치)'보다 더 뒤에 구멍이 등장하면
                tapeTail = nowN + m - 1;    // '테이프로 메꿔진 마지막 위치'를 새롭게 체크하고(새롭게 테이프를 붙이고)
                cnt++;                      // 붙였으니까 카운트.
            }
        }

        System.out.println(cnt);
    }
}

마무리

---

맥시멈 사이즈가 1000이기 때문에 마지막처럼 풀어도 사실 성능 개선이 크진 않지만, 풀면서 전혀 고려하지 못했던 관점을 제시받아서 놀라웠다.
아이디어를 받아 코드를 구현하긴 했지만 '비슷한 다른 문제를 또 풀게 된다면, 내가 이런 생각을 또 할 수 있을까?'란 생각이 들긴 했다.
모르겠다. 부족한 재능에 좌절이 되고 그런건 아니고 ㅋㅋㅋ 어쨌든 스스로 생각지 못했던 부분을 생각해보게 되었으니 오히려 좋을지도...? ㅋㅋ
몰라 계속 하면 되지 뭐 ㅋㅋ..