[매일프로그래밍] 4월 30일

안녕하세요. 6월이지만 4월 30일 매일프로그래밍 문제 포스팅입니다. 일이 바쁘다는 핑계로 한주에 한번 포스팅 쓰는게 어려워 많이 밀렸네요. 조금 더 노력해야겠습니다. ※해당 문제에대한 저작권은 매일프로그래밍에 있습니다 이번 문제는 오랜만이라 그런지 문제 이해하는 시간도 오래걸렸습니다.

문제

---

간격(interval)로 이루어진 배열이 주어지면, 겹치는 간격 원소들을 합친 새로운 배열을 만드시오. 간격은 시작과 끝으로 이루어져 있으며 시작은 끝보다 작거나 같습니다.

예제)

Input : {{2,4}, {1,5} , {7,9}}

Output : {{1,5},{7,9}}

Input : {{3,6}, {1,3} , {2,4}}

Output : {{1,6}}

먼저 예제의 인풋 데이터를 살펴보면 시작과 끝으로 이루어진 배열들이 나열되어 있습니다. 해당 배열들중 겹치는 배열들을 합치는 문제입니다. 첫번째 배열({2,4})과 두번째 배열({1,5}) 의 시작값과 끝 값을 각각 비교해서 서로의 배열에 포함이 가능한지 여부를 체크해야 합니다. 코드는 아래에 숨겨놓겠습니다.

public class test {
    private ArrayList<Interval> list = new ArrayList<>();
    private ArrayList<Interval> result = new ArrayList<>();


    public void setList(ArrayList<Interval> list) {
        this.list = list;
    }

    public void calculate() {

        list.add(new Interval(3, 6));
        list.add(new Interval(1, 3));
        list.add(new Interval(2, 4));

        Interval lastResultItem;
        boolean isStartChange;
        boolean isEndChange;
        boolean isContains;

        for (int i = 0; i < list.size(); i++) {
            Interval item = new Interval();
            item.set(list.get(i).getStart(), list.get(i).getEnd());
            if (result.size() == 0) {
                result.add(item);
            } else {
                lastResultItem = result.get(result.size() - 1);
                isStartChange = false;
                isEndChange = false;
                isContains = false;

                //각 아이템이 서로의 범위를 포함하는지 체크한다.
                if (item.getStart() < lastResultItem.getStart() && item.getEnd() >= lastResultItem.getStart()) {
                    lastResultItem.setStart(item.getStart());
                    isStartChange = true;
                }
                if (item.getEnd() > lastResultItem.getEnd() && item.getStart() <= lastResultItem.getEnd()) {
                    lastResultItem.setEnd(item.getEnd());
                    isEndChange = true;
                }

                if (!isStartChange && !isEndChange) {
                    //둘다 변하지 않았으면 범위에 포함하지 않는단 얘기이므로 추가한다.
                    if (item.getEnd() <= lastResultItem.getEnd() && item.getStart() >= lastResultItem.getStart()) {
                        isContains = true;
                    }

                    if (!isContains)
                        result.add(item);
                }
            }

        }

        String resultStr = "";
        for (int i = 0; i < result.size(); i++) {
            if (i == 0) {
                resultStr += result.get(i).print();
            } else {
                resultStr += "," + result.get(i).print();
            }
        }

        WLog.e("################", "result=" + resultStr + ", size=" + result.size());
    }

    class Interval {
        private int start;
        private int end;

        public Interval() {
            this.start = 0;
            this.end = 0;
        }

        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }

        public void set(int start, int end) {

            this.start = start;
            this.end = end;
        }

        public void setEnd(int end) {
            this.end = end;
        }

        public String print() {
            return "[" + start + "," + end + "]";
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getEnd() {
            return end;
        }

        public int getStart() {
            return start;
        }
    }

}

※해당 포스팅은 지극히 주관적인 내용으로 저자의 복기 목적으로 작성된 것이고, 내용에대해 수정이나 추가 요청은 언제든 환영합니다.