Q 2566 최댓값

💡 문제 요약 및 분석

9x9 행렬에 81개의 자연수 및 0 이 주어질 때, 최댓값과 그 숫자의 위치를 답하면 된다.

💡 알고리즘 설계

✅ 핵심 아이디어 : 배열이 필요 없을 것 같다. 최댓값과 위치만 저장하자.

1. 입력

   • StringTokenizer 로 한 줄씩 입력받는다.

2. 연산

   • 이중 for문 사용
   • i = 0 부터 한 줄씩 토큰으로 쪼개고, j = 0 부터 이전 숫자와 비교하여 최댓값, 위치를 저장한다.

3. 출력

   • StringBuilder 로 한 번에 출력한다.

💡 코드

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

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

        int max = 0;
        int x = 0;
        int y = 0;
        for (int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                int num = Integer.parseInt(st.nextToken());
                if (max < num) {
                    max = num;
                    x = j;
                    y = i;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(max).append("\n");
        sb.append(y + 1).append(" ").append(x + 1);
        System.out.println(sb);
    }
}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(1)	O(1)

💡 다른 풀이

지금까지는 StringTokenizer 만 사용했는데 split() 을 사용했을 때의 속도 차이가 궁금해서 바꿔보았다. 결론적으로는 StringTokenizer 가 미세하게 더 빨랐는데, 이유는 split 의 경우 정규 표현식을 사용하여 문자를 분리하기 때문이란다. 심지어 결과를 배열로 할당하기 때문에 메모리를 더 먹는다. 반대로 StringTokenizer 는 단순하게 문자열을 한 번에 하나씩만 분리한다. 일반적으로는 StringTokenizer 속도가 더 빠르다고 보면 될 듯 하다.

for (int i = 0; i < 9; i++) {
    String[] ary = br.readLine().split(" ");
    for (int j = 0; j < 9; j++) {
        int num = Integer.parseInt(ary[j]);
        if (max < num) {
            max = num;
            x = j + 1;
            y = i + 1;
        }
    }
}