[TIL-31/230922][백준 2635/자바(java)] 수 이어가기

오늘은 프로젝트도 끝났기에, 알고리즘 문제를 풀었다.

알고리즘 문제는 아래와 같다.

https://www.acmicpc.net/problem/2635

2635번: 수 이어가기

시간	제한메모리	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	11202	4366	3511	37.773%

문제

다음과 같은 규칙에 따라 수들을 만들려고 한다.

1. 첫 번째 수로 양의 정수가 주어진다.
2. 두 번째 수는 양의 정수 중에서 하나를 선택한다.
3. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다.
4. 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.

첫 번째 수로 100이 주어질 때, 두 번째 수로 60을 선택하여 위의 규칙으로 수들을 만들면 7개의 수들 100, 60, 40, 20, 20 , 0, 20이 만들어진다. 그리고 두 번째 수로 62를 선택하여 위의 규칙으로 수들을 만들면 8개의 수들 100, 62, 38, 24, 14, 10, 4, 6이 만들어진다. 위의 예에서 알 수 있듯이, 첫 번째 수가 같더라도 두 번째 수에 따라서 만들어지는 수들의 개수가 다를 수 있다.

입력으로 첫 번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성하시오. 최대 개수의 수들이 여러 개일 때, 그중 하나의 수들만 출력하면 된다.

입력

첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다.

출력

첫 번째 줄에는 입력된 첫 번째 수로 시작하여 위의 규칙에 따라 만들 수 있는 수들의 최대 개수를 출력한다.

둘째 줄에 그 최대 개수의 수들을 차례대로 출력한다. 이들 수 사이에는 빈칸을 하나씩 둔다.

 

첫 번째 풀이

메모리에 대한 생각을 하나도 하지 않은 부끄러운 코드지만 복습할 때 반성하기 위해 오답 코드도 첨부하겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        br.close();

        // 2차원 배열 선언 및 초기화
        int[][] arr = new int[n + 1][n + 1];

        // 각 배열의 첫 번째 요소 초기화
        for (int i = 0; i < n; i++) {
            arr[i][1] = n; // i행의 1열은 모두 n으로 초기화. 첫번째 수는 갯수
        }

        int nextValue = n / 2;

        // 배열 값 계산
        for (int i = 0; i < n; i++) {
            arr[i][2] = nextValue;
            int count = 2;

            // 3열부터 계산
            for (int j = 3; j < n; j++) {
                int newNumber = arr[i][j - 2] - arr[i][j - 1];

                // 새로운 수가 0보다 크면 배열에 저장하고 카운트 증가
                if (newNumber > 0) {
                    arr[i][j] = newNumber;
                    count++;
                } else {
                    // 새로운 수가 0 이하이면 카운트 저장하고 다음 값을 준비
                    arr[i][0] = count;
                    nextValue++;
                    break;
                }
            }
        }

        // 최대 카운트와 해당 행 찾기
        int maxCount = 0;
        int maxRow = 1;
        for (int i = 0; i < n; i++) {
            if (arr[i][0] > maxCount) {
                maxCount = arr[i][0];
                maxRow = i;
            }
        }

        // 결과 출력
        System.out.println(maxCount);
        for (int i = 1; i < n; i++) {
            if (arr[maxRow][i] == 0) {
                break;
            }
            System.out.print(arr[maxRow][i] + " ");
        }
    }
}

문제 분석 과정

문제를 보고 메모리에 대한 고려를 하지 않고 단순하게 생각했다.

• [n+1][n+1] 크기의 2차원 배열을 만듦
• col = 1에 입력받은 n 값 대입
• col = 2부터 조건을 만족하는 경우 값을 대입
• 대입하면서 count의 값을 1 증가
• 조건을 만족하지 않는 수가 나올 경우 반복문 종료 및 count 값을 col = 0에 대입
• col = 0인 값을 순회하며 최대 개수값의 row를 찾음
• 최대 개수를 출력하고, row 값에 해당하는 배열의 값 출력(0이 아닌 값들)

보통 문제를 풀 때 메모리에 대해서 큰 생각은 하지 않고 풀었었는데, 메모리 초과가 나와서 당황했다.

아마 입력값의 범위가 30000 이하의 양수이기에, [n+1][n+1]의 배열을 선언하여 너무 많은 메모리를 차지해서 메모리 초과가 되었다.

 

메모리 계산 방법

• int[] = 4byte
• int[30001][30001] = 900,060,001 * 4 byte = 3,600,240,004 byte = 3600.24MB
• 주어진 조건인 128MB를 훨씬 초과한다.

 

 

이런 이유들 때문에 기초 지식이 중요하다는 건데 아직 많이 부족하구나라고 느꼈다.

그래서 다시 고민했다. 다른 방법이 없을까?

 

다른 자료형 구조들을 생각해봤다.

저번에 공부하였던 컬렉션 프레임워크의 자료를 참고하였다.

https://prao.tistory.com/entry/TIL-18-230907-%ED%95%A8%EC%88%98%ED%98%95-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-%EC%BB%AC%EB%A0%89%EC%85%98-%ED%94%84%EB%A0%88%EC%9E%84%EC%9B%8C%ED%81%AC

[TIL-18 / 230907] 함수형 프로그래밍, 컬렉션 프레임워크

이 문제의 경우 차례대로 값을 넣고 FIFO 형태로 출력하는 방식이 적절하기에,

List 중에 ArrayList가 적절하다.(중간의 요소 삽입, 삭제가 일어나지 않음)

 

따라서 다음과 같이 다시 코드를 작성하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		br.close();

		ArrayList<Integer> answer = new ArrayList<>(); // 결과를 저장할 ArrayList
		int maxCount = 2; // 초기 최대 길이는 2 (1, 1)

		// 1부터 n까지의 수에 대해 수열 생성 및 최대 길이 갱신
		for (int i = 1; i <= n; i++) {
			ArrayList<Integer> list = new ArrayList<>(); // 현재 수열을 저장할 ArrayList
			list.add(n); // 첫 번째 항 추가
			list.add(i); // 두 번째 항 추가 (현재의 i)

			int firstNumber = n;
			int secondNumber = i;

			while (true) {
				int temp = firstNumber - secondNumber; // 다음 항 계산
				if (temp >= 0) {
					list.add(temp); // 다음 항 추가
				}
				if (temp < 0) {
					break; // 음수가 되면 종료
				}
				firstNumber = secondNumber; // 변수 갱신
				secondNumber = temp;
			}

			if (list.size() >= maxCount) {
				maxCount = list.size(); // 최대 길이 갱신
				answer = list; // 현재 수열이 최대 길이일 경우 결과 갱신
			}
		}

		System.out.println(maxCount);
		for (int i = 0; i < answer.size(); i++) {
			System.out.print(answer.get(i) + " "); // 공백으로 구분하여 출력
		}
	}

}

문제 풀이

• 정답 배열과, 최대 개수(maxCount) 선언(최솟값 2 -> 1 1)
• 반복문을 돌면서 i번째 배열에는 i-2번째에 있는 수 - i-1번째에 있는 수의 값이 음의 정수가 아닌지를 판별하여 0 또는 양의 정수라면 대입하고 음의 정수라면 반복문을 종료한다.
• 반복문 종료 시 maxCount와 list.size(()를 비교하여 maxCount보다 list.size()가 크다면 최대 길이와 정답 배열을 갱신한다.
• 반복문 종료 시 maxCount와 answer 배열을 출력한다.

이번 문제는 실버5의 난이도의 문제였다.

아마 코딩테스트에 출제된다면 거의 가장 쉬운 난이도의 문제일 것이다.

보통은 이것보다 어려운 실버 상위에서 골드 하위 수준의 문제가 출제되는 것으로 알고 있다.

하지만 이번 문제를 풀면서 그동안 생각하지 않았던 메모리를 고려해야 한다는 것과,

자료 구조의 필요성을 좀 더 학습할 수 있어서 좋은 경험이 된 문제였다.