프로그래머스 - 삼각 달팽이

링크

https://school.programmers.co.kr/learn/courses/30/lessons/68645

프로그래머스

 

문제 제한 사항

정수 n이 매개변수로 주어지고, 최소 1 이상이고 최대10^3 이다.

최대 시간 복잡도는 O(N^2)이다. 

 

문제 해결 아이디어

n=4 이고, 블록에 들어가는 숫자를 e라고 지칭할 때

e=1 , n=1

e=2, n=2

e=3, n=3

e=4, n=4

e=5, n=4

e=6, n=4

e=7, n=4

e=8, n=3

e=9, n=2

e=10, n=3

위와 같이 들어가게 된다.

 

처음에는 n값과 e값이 동일하게 증가하다가,

마지막 층인 n이 4일 때, 4개의 블럭이 다 찰 때까지 연속으로 숫자를 넣어준다.

그리고 e값은 증가하면서 다시 블럭이 다 안 찬 층을 찾으면 숫자를 바로 넣어주는 형식이 된다.

 

멤버변수로 자신의 n값과 어떤 값이 들어가는지 Integer 리스트를 멤버변수로 가질 수 있도록 하려고 했다.

 private static class Level {
    public int n;
    public List<Integer> elements;

    public Level(int n) {
        this.n = n;
        this.elements = new ArrayList<>();
    }
}

 

연속된 숫자와 맨마지막 구간에서 차례대로 숫자를 넣는 부분까지는 구현하기 쉬웠으나, 그 이후 순서부터 조금씩 꼬이기 시작했다.

 

코드

> 기존 코드(오답) .. 너무 별로인 코드ㅜ

조건 처리하는 데 예외 사항에 대한 처리가 명확하지 않았고,

'층 수가 줄어드는 경우 / 층 수가 증가하는 경우 / 층 수가 유지되는 경우'에 대한 조건을 마구잡이 형식으로 넣어줘서 정답이 제대로 나오지 않았다.

논리 단위로 동작 흐름을 나누는 부분에 대해 부족하게 느껴졌다.

    private static class Level {
        public int n;
        public List<Integer> elements;
        public boolean canPutElement;

        public Level(int n) {
            this.n = n;
            this.canPutElement = true;
            this.elements = new ArrayList<>();
        }

        private void addAllElements(int elementNum) {
            int number = elementNum;
            while (elementNum <= number + (number-1)) {
                elements.add(elementNum++);
            }
            this.canPutElement = false;
        }

        private void addElement(int elementNum) {
            if (canPutElement) {
                elements.add(elementNum);
                if (elements.size() == n) {
                    canPutElement = false;
                }
            }
        }
    }


public static void main(String[] args) {
//        int n = 4;
        int n = 5;
//        int n = 6;

        Map<Integer, Level> levelMap = new HashMap<>();

        for (int i=1; i<=n; i++) {
            Level level = new Level(i);

            if (i==n) {
                level.addAllElements(i);
            } else {
                level.addElement(i);
            }

            levelMap.put(i, level);
        }

        int flag = n-1;
        for (int element=2*n; ; element++) {
            Level level = levelMap.get(flag);
            if (flag == n && !level.canPutElement){
                break;
            }

            if (flag == n) {
                level.addElement(element);
                continue;
            }

            if (level.canPutElement) {
                level.addElement(element);
                flag--;
            } else {
                flag++;
                level = levelMap.get(flag);
                level.addElement(element);
            }
        }

        for (Level level : levelMap.values()) {
            System.out.println(Arrays.toString(level.elements.toArray()));
        }
    }

 

> 정답은 다른 블로그에 찾아보면 많이 나오기 때문에 따로 첨부하지는 않으려고 한다.

배운점

시작한지 얼마 되지 않아서, 일단 지금 형식처럼 풀어보고 기록하려고 한다. 

계속 연습해서 코딩테스트 준비에 차질이 없도록 해야겠다.