[프로그래머스 / 월간 코드 챌린지 시즌3 / 자바(JAVA)] n^2 배열 자르기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

 

 

▼ ▼ ▼

정답 풀이로 바로 가기

▲ ▲ ▲

 

오답 풀이

 

로직

 

예시 애니메이션에 나온대로 배열을 만들어 풀고자 했다.

1. i는 행, j는 열로 설정한다.
2. k는 i+1부터 시작한다.
3. 해당 행, 열에 해당하는 값은 n*i+j이 된다. 이 값이 left와 right 사이에 있으면 k를 list에 추가한다.
4. 만약 j>=i라면 k++해준다.
5. 만들어진 list를 stream을 이용해 배열화 해 return해준다.

 

코드

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {

        List<Integer> answer = new ArrayList<>();

        for(int i=0; i<n; i++) {
            int k = i+1;

            for(int j=0; j<n; j++) {
                if(n*i+j >=left && n*i+j<=right) answer.add(k);
                if(j>=i) k++;
            }
        }

        return answer.stream().mapToInt(i -> i).toArray();
    }
}

 

채점 결과

정확성  테스트
테스트 1 〉    통과 (16.59ms, 97.7MB)
테스트 2 〉    실패 (시간 초과)
테스트 3 〉    실패 (시간 초과)
테스트 4 〉    통과 (3.62ms, 85.9MB)
테스트 5 〉    통과 (2.02ms, 72MB)
테스트 6 〉    통과 (17.10ms, 98.1MB)
테스트 7 〉    통과 (26.03ms, 113MB)
테스트 8 〉    통과 (23.71ms, 106MB)
테스트 9 〉    통과 (220.77ms, 94.9MB)
테스트 10 〉    통과 (215.27ms, 107MB)
테스트 11 〉    통과 (195.07ms, 89.4MB)
테스트 12 〉    실패 (시간 초과)
테스트 13 〉    실패 (7635.78ms, 86.5MB)
테스트 14 〉    실패 (7879.79ms, 80.7MB)
테스트 15 〉    실패 (시간 초과)
테스트 16 〉    실패 (시간 초과)
테스트 17 〉    실패 (시간 초과)
테스트 18 〉    실패 (시간 초과)
테스트 19 〉    실패 (시간 초과)
테스트 20 〉    실패 (시간 초과)

채점 결과
정확성: 45.0
합계: 45.0 / 100.0

 

 

정답 풀이

 

로직

너무 정직하게 했더니 역시나.. 시간초과가 떴다. 다른 방식을 써야한다.
(근데 내가 골머리 싸매고 생각한 이것도... 그닥 간단한 방법이 아니다... 그래서 슬퍼...)

1. n이 3인 행렬로 예시를 들어보자.
   1 2 3 - 0번째 그룹
   2 2 3 - 1번째 그룹
   3 3 3 - 2번째 그룹
2. 이를 일렬로 줄세워보자

인덱스	0	1	2	3	4	5	6	7	8
인덱스/n	0	0	0	1	1	1	2	2	2
인덱스%n	0	1	2	0	1	2	0	1	2
값	1	2	3	2	2	3	3	3	3

3. 찬찬히 살펴보자...
   • 인덱스 / n 은 그 그룹이 몇 번째인지를 나타낸다.
   • 그룹의 시작값은 인덱스 / n + 1 이다.
4. 그래서 처음에는 어떻게 하려고 했냐면...
   left부터 right까지 증가하는 int index를 이용해서이런식으로 하려고 했으나, left가 index / n >= index % n의 조건을 달성하지 못한 상태에서 시작한다면
   stack이 빈 상태이기 때문에 오류가 뜨게 되기에 다른 방법을 강구할 필요가 있었다.
5. if(index / n >= index % n) stack.push(i/n+1); else stack.peek()+1;
6. 그래서... 찾아낸 규칙이,
   index / n < index % n 일 때, (그룹 첫 수) + (index % n - index / n)가 된다는 거였음.
   • 즉, (index / n + 1) + (index % n - index / n)
   • 여기서 생각이 멈췄었음. 이걸 정리하면 곧 index % n + 1이라는 간편한 식이 나오는데...ㅠㅠ 아쉽

 

코드

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {

        Stack<Long> stack = new Stack<>();

        for(long i=left; i<=right; i++) {
            if(i/n >= i%n) stack.push(i/n+1);
            else stack.push((i/n+1)+(i%n-i/n));
                // 이를 stack.push(i%n+1)로 수정한다면 더 간결했을 것.
        }

        return stack.stream().mapToInt(i -> i.intValue()).toArray();
    }
}

채점 결과

정확성  테스트
테스트 1 〉    통과 (16.36ms, 105MB)
테스트 2 〉    통과 (18.96ms, 113MB)
테스트 3 〉    통과 (19.35ms, 113MB)
테스트 4 〉    통과 (3.15ms, 70.8MB)
테스트 5 〉    통과 (3.23ms, 85.1MB)
테스트 6 〉    통과 (16.26ms, 93.9MB)
테스트 7 〉    통과 (18.21ms, 113MB)
테스트 8 〉    통과 (36.24ms, 101MB)
테스트 9 〉    통과 (19.07ms, 97.1MB)
테스트 10 〉    통과 (26.97ms, 116MB)
테스트 11 〉    통과 (18.30ms, 110MB)
테스트 12 〉    통과 (24.54ms, 111MB)
테스트 13 〉    통과 (19.14ms, 94.6MB)
테스트 14 〉    통과 (24.47ms, 95.7MB)
테스트 15 〉    통과 (18.66ms, 97.7MB)
테스트 16 〉    통과 (27.71ms, 101MB)
테스트 17 〉    통과 (21.21ms, 117MB)
테스트 18 〉    통과 (32.99ms, 112MB)
테스트 19 〉    통과 (28.69ms, 94.2MB)
테스트 20 〉    통과 (19.05ms, 96.8MB)-

채점 결과
정확성: 100.0
합계: 100.0 / 100.0

 

 

좋은 풀이

홍희표, 김태환, YMK

import java.util.Arrays;
import java.util.stream.LongStream;

class Solution {
    public int[] solution(int n, long left, long right) {
        return LongStream.rangeClosed(left, right).mapToInt(value -> (int) (Math.max(value / n, value % n) + 1)).toArray();
    }
}

배운 점

1. if문을 단순 Math.max() 메소드로 간결화한 것
   • 다음은 내가 짠 코드..
   • Math.max(i/n+1, i%n+1)로 간결하게 만들 수 있다.

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {

        Stack<Long> stack = new Stack<>();

        for(long i=left; i<=right; i++) {
            if(i/n >= i%n) stack.push(i/n+1); // 즉 i/n이 더 크면 i/n+1을 push하고
            else stack.push(i%n+1);    // i%n이 더 크면 i%n+1을 push함
        }

        return stack.stream().mapToInt(i -> i.intValue()).toArray();
    }
}

2. LongStream.rangeClosed(left, right)
   • left부터 right 까지의 Long을 stream으로 내보내는 것
   • 참고로 .range(a, b)는 b값을 포함하지 않고, .rangeClosed(a, b)는 b값ㅇ르 포함함.