[백준 2566번 최댓값] (알고리즘)

문제

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

예를 들어, 다음과 같이 81개의 수가 주어지면

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

이들 중 최댓값은 90이고, 이 값은 5행 7열에 위치한다.

입력

첫째 줄부터 아홉 번째 줄까지 한 줄에 아홉 개씩 수가 주어진다. 주어지는 수는 100보다 작은 자연수 또는 0이다.

출력

첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다. 최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

90 5 7

스스로 고민

크기가 정해져 있으니 9번 반복문을 돌리고 열 값은 리스트로 받아서 맥 스값 비교 및 다음 행으로 넘어가면서 최대 값을 업데이트 하면서 행과 열의 좌표를 업데이트 하면 된다고 생각했다.

구현 코드

import sys

max_value = 0
coordinate=None
for i in range(9):

    a = list(map(int, sys.stdin.readline().split()))
    temp = max(a)
    if temp > max_value:
        coordinate = [i+1, a.index(temp)+1]
        max_value = temp

print(max_value)
print(*coordinate)

• 로컬 환경에서는 잘 나오지만 백준에서는 런타입 에러가 발생하고 None 부분 때문에 발생하는 것 같았다.
• 해당 부분을 [] 로 변경했지만 틀렸다고 나오길래 아마 테스트 환경에서 좀 다른 부분이 있엇서 그냥 구조를 아래와 같이 바꿔봤다.

import sys

max_value = 0
a = 0
b = 0
for i in range(9):

    z = list(map(int, sys.stdin.readline().split()))
    temp = max(z)
    if temp > max_value:
        a = i
        b = z.index(temp)
        max_value = temp

print(max_value)
print(a+1, b+1)

None 값 부분을 그냥 변수 값으로 받아서 마지막에만 1을 더해주는 방법으로 문제를 해결했다.

시간 복잡도와 공간 복잡도

시간 복잡도:

1. max_value, a, b 변수를 초기화하는 부분은 O(1) 시간이 소요된다.
2. for 루프는 9번 반복하며, 각 반복에서 sys.stdin.readline().split()을 사용하여 9개의 정수를 입력받는다. 각 반복에서 최댓값을 찾는 데에는 9개의 정수 중 최댓값을 찾는데 필요한 O(9) = O(1)의 시간이 소요된다.
3. 각 반복에서 최댓값을 찾고, 이 값이 현재까지의 max_value보다 큰지 확인하고, 필요한 변수를 업데이트하는 부분은 O(1) 시간이 소요된다.

따라서 전체 코드의 시간 복잡도는 O(1) (상수 시간) 다.

공간 복잡도:

1. max_value, a, b, z, temp 등 변수는 상수 개수로 사용되며, 공간 복잡도는 O(1)다.
2. 입력값을 저장하는 리스트 z는 9개의 정수를 저장하므로 길이가 9다. 이것은 입력 데이터의 크기에 따라 달라진다. 따라서 추가적인 입력값을 저장하기 위한 공간 복잡도는 O(9) = O(1) 다.

따라서 전체 코드의 공간 복잡도 O(1)다.

회고 과정

• 이게 테스팅 환경 때문에 문제가 안풀린건지 그냥 내가 파이썬을 제대로 이해하지 못 해서 틀렸던건지 좀 헷갈렸다.
• 틀렸을 경우 백준에서 왜 틀렸는지 알 수 가 없으니 좀 답답할 뿐. ㅜ

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

L=*map(int,open(0).read().split()),
a=L.index(M:=max(L))
print(M,a//9+1,a%9+1)

굉장히 짧은 코드로 문제를 해결했는데 메모리나 계산속도는 동일하다.
성능면에서 이점이 없다보니 가독성 면에서 안좋다고 생각했다.
한편으로는 이렇게 생각해내는 것도 대단하다고 생각했다