[softeer] 소프티어(파이썬): 징검다리 ★★★

문제

Softeer

- 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다.

- 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다.

- 밟을 수 있는 돌의 최대 개수를 구하는 문제이다.

- 돌의 개수가 N일때 1 ≤ N ≤ 10^4 인 정수이다.

- 돌의 높이가 A일때 1 ≤ A ≤ 10^8 인 정수이다.

알고리즘

- 시간 복잡도는 N^2 ≤ 10^8 이기때문에 O(N^2)으로 풀 수 있다.

- 돌의 개수를 입력받는다.

- 돌의 높이를 차례대로 입력받는다.

- 계수정렬을 위해 1이 들어간 리스트를 돌의 개수만큼 만들어주어 리스트 변수에 넣는다.

- 반복문을 통해 다음 밟을 돌보다 그전에 있는 모든 돌의 높이를 비교한다.

- 다음 밟을 돌이 그전에 있는 돌의 높이보다 높고 돌의 계수가 작다면 돌의 계수를 초기화하고 카운트 한다.

- 돌의 계수가 있는 리스트에서 제일 큰 수를 출력한다.

코드

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
# 돌의 계수 리스트
result = [1] * n

for i in range(1, n):
    # 돌의 계수를 비교할 변수 초기화
    result_max = 0
    for j in range(i):

        # 다음 밟을 돌의 높이와 그전에 있는 모든 돌의 높이 비교
        if a[i] > a[j]:
            # 돌의 계수 비교
            if result_max < result[j]:
                result_max = result[j]

    # 돌의 계수 카운트
    result[i] = result_max + 1

# 리스트에서 제일 큰 수를 출력
print(max(result))

결과

위 코드 밑에 print(result)를 작성하여 돌의 계수 리스트를 확인해보면 돌의 계수가 돌의 높이의 증가함에 따라 돌의 계수가 카운트 된 것을 확인할 수 있다.

<출력화면>

위 출력화면을 보게 되면 2는 3보다 크지 않고 1은 3, 2보다 크지 않기 때문에 계수 카운트가 1이다. 그런데 4는 3, 2, 1 보다 크기 때문에 계수 카운트가 1 증가한 2가 된다. 5는 3, 2, 1, 4 보다 크기 때문에 그중에서 제일 계수가 높았던 4의 계수인 2를 받고 계수 카운트를 1을 더해준 3이 되는 것이다. 따라서 밟을 수 있는 돌의 최대 개수는 3이 되는 것이다.

<출력화면>

위 다른 예시의 출력화면을 보게 되면 3번째 돌까지는 돌의 높이가 크지 않기 때문에 계수가 1이다. 그런데 6은 3, 2, 1보다 크기 때문에 계수 카운트가 1 증가한 2가 된다. 7은 3, 2, 1, 6 보다 크기 때문에 그중에서 제일 계수가 높았던 6의 계수인 2를 받고 계수 카운트를 1을 더해준 3이 되는 것이다. 그리고 4는 3, 2, 1보다는 크기 때문에 그중에서 제일 계수인 1을 받고 계수 카운트를 1을 더해준 2가 되는 것이다. 5는 3, 2, 1, 4 보다는 크고 6, 7보다는 작기 때문에 3, 2, 1, 4의 계수 중에서 제일 큰 계수인 2를 받고 계수 카운트를 1을 더해준 3이 되는 것이다.

따라서 코드를 분석하게 되면 다음 밟을 돌의 높이가 비교하고 있는 돌보다 높고, 돌의 계수를 비교할 변수가 비교하고 있는 돌의 계수보다 작으면 다음 밟을 돌의 계수의 변수를 비교하고 있는 돌의 계수로 초기화시켜주는 것이다. 그리고 반복문을 나왔을 때 1을 더해주어 돌의 계수를 카운트 해주고 마지막에 제일 큰 계수 값을 출력해주는 것이다.

github

junjange/CodingTest