[TIL] 자바 알고리즘 연습 240722

 

문제구분 : 배열

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

프로그래머스

 

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
   - 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.

3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.

 

정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

 

풀이 회고 :

우선 입력 제한에 n이 10^7인 것을 확인하고 이중 포문으로 푸는 것은 아니라는 사실을 확인했다. 입력값이 커지면 O^n은 분명 시간초과가 발생할 것 같았다.

반복문을 한번만 돌린다면 위의 문제 순서대로 정답의 배열을 차근차근 만드는 방식으로는 해결할 수 없을 것 같았다.

값이 존재하는 2차원 배열을 만드는 것은 어렵지 않으므로 바로 해당되는 값을 answer 배열에 넣어주기로 한다.

행과 열을 어떻게 정의할 것인가. 행과 열의 크기가 같고 각 자리에 해당하는 값은 행과 열 중 큰 숫자의 값이다. (인덱스이므로 하나를 더한다)

예) (0, 0) => 1, / (0, 1) => 2 / (1, 0) => 2 / (1010, 10) => 1011

따라서 x와 y 좌표에 해당하는 값은 Math.max(x, y) +1 이다.

x와 y는 어떻게 구할 것인가. x이 고정되는 동안 y는 n까지 커질 것이며 y가 n이 되는 순간 0으로 돌아가고 x는 하나 높아진다.

이를 토대로 x = i / n, y = i % n으로 정의했다.

전체적인 코드는 다음과 같다.

 

class Solution {
   public int[] solution(int n, long left, long right) {
        int[] answer = new int[(int) (right - left + 1)];
        for(long i = left; i <= right; i++) {
            int x = (int) (i / n);
            int y = (int) (i % n);
            answer[(int)(i-left)] = Math.max(x, y) + 1;
        }
        return answer;

    }
}

 

위 코드를 완성하기까지 어이없는 몇번의 오답이 있었다.

left와 right의 타입이 long이므로 이를 가지고 계산한 x와 y를 정의하기 위해 int로 타입 변환을 시켜줘야 했는데

i / n의 괄호를 치지 않아서 계산한 값 전체가 아니라 i만 int로 타입변환하여 코드 실행하면 정답이 나오는데 테스트케이스 12번부터 계속 오답이 발생한 것이다. 

타입 변환에 대해 잘 체크하고 넘어가야겠다.