최댓값

[hsskey]

문제 설명 | 링크

9×9 격자판에 쓰여진 81개의 자연수 또는 0이 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 행 몇 열에 위치한 수인지 구하는 프로그램을 작성하시오.

📝 제약조건

• 격자판은 9×9 형태로 주어진다. 각 요소는 0 이상 100 이하의 자연수다.
• 최댓값이 여러 개일 경우, 가장 처음 등장한 위치를 출력한다.

💡 예시

• Input:

  3 23 85 34 17 74 25 52 65
  10 7 39 42 88 52 14 72 63
  87 42 18 78 53 45 18 84 53
  34 28 64 85 12 16 75 36 55
  21 77 45 35 28 75 90 76 1
  25 87 65 15 28 11 37 28 74
  65 27 75 41 7 89 78 64 39
  47 47 70 45 23 65 3 41 44
  87 13 82 38 31 12 29 29 80
  

  • Output:

  90
  5 7
  

문제 해결 과정

Step 1: 문제 이해하기

• Input 값의 특징:

  • 9개의 줄에 9개의 숫자가 주어진다. 각 숫자는 0 이상 100 이하의 자연수다.
  • 모든 입력값은 자연수 또는 0. 음수는 없다.

• Output 값의 특징:

  • 최댓값과 그 위치를 출력해야 한다. 위치는 1부터 시작하는 인덱스로 표현된다.

• Input size N 확인:

  • 입력은 9×9 크기이며 총 81개의 값이다.
  • 입력 크기가 작기 때문에 O(N²) 복잡도 정도의 완전탐색도 무리 없이 사용 가능하다.

• 제약조건 확인:

  • 모든 값은 자연수 또는 0이며, 최대 값은 100이다.
  • 최댓값이 여러 번 등장할 경우 가장 먼저 등장한 위치를 출력해야 한다.

• 예상할 수 있는 오류 파악:

  • 입력이 모두 0일 경우에도 최댓값은 0이며, 그 위치를 정확히 출력해야 한다.
  • 모든 행과 열에 대해 값을 비교해야 하기 때문에 인덱스 조작 시 실수할 가능성이 있다.

Step 2: 접근 방법

• 직관적으로 생각하기:

  • 9×9 크기의 배열을 모두 탐색하여 최댓값을 찾아야 한다.
  • 2중 반복문을 사용해 모든 요소를 비교하며 최댓값을 갱신하고, 최댓값이 갱신될 때마다 위치를 저장한다.

• 자료구조와 알고리즘 활용:

  • 배열을 사용해 입력을 저장하고, 이차원 배열을 탐색하는 방식으로 진행한다.

• 메모리 사용:

  • 메모리 제한이 없으며, 입력 크기가 작기 때문에 배열을 그대로 사용해 탐색해도 문제가 없다.

Step 3: 코드 설계 (의사코드)

1. 9×9 배열을 입력으로 받는다.
2. 최댓값을 저장할 변수를 초기화한다. (최솟값 또는 음수로 설정)
3. 각 행과 열을 순회하며 현재 값이 최댓값보다 크면 최댓값과 그 위치를 갱신한다.
4. 최댓값과 그 위치를 출력한다.

Step 4: 코드 구현

const fs = require('fs')
const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`
const input = fs.readFileSync(filePath).toString().split('\n')

const arr = []
for(let i = 0; i < input.length; i++) {
    arr.push(input[i].split(' ').map(Number))
}

let maxVal = -Infinity
let position = [1, 1] // 초기 위치를 (1, 1)로 설정합니다.

for(let i = 0; i < arr.length; i++) {
    for(let j = 0; j < arr[i].length; j++) {
        if (arr[i][j] > maxVal) {
            maxVal = arr[i][j]
            position = [i + 1, j + 1] // 새로운 최댓값의 위치를 저장합니다.
        }
    }
}

console.log(String(maxVal))
console.log(position.join(' '))