[백준] 15966번 python 풀이 _ 군계일학

 

출처 : https://www.acmicpc.net/problem/15966 

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 (언어별 추가 시간 없음)256 MB149726621363.582%

문제

효빈이는 어떤 수열에서 군계일학 수열을 뽑아내고자 한다. 단, 뽑은 항의 순서는 기존 수열에서의 순서를 유지해야 한다. 군계일학 수열은 각 항이 서로 연속적인 수열을 의미한다. 정확한 정의는 다음과 같다.

수열 중에 어떤 임의의 항 i에 대해서, ai=a1+(i-1)을 만족해야한다.

길이가 N이고 정수로 이루어진 수열이 주어진다. 효빈이는 가장 긴 군계일학 수열을 가져가서 김승호 선생님께 자랑하려고 한다. 효빈이가 뽑아낼 수 있는 가장 긴 군계일학 수열의 크기를 출력하라.

입력

첫 째줄에 수열의 길이 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에, ai (1 ≤ i ≤ N, 1 ≤ ai ≤ 1,000,000)이 주어진다.

출력

수열에서 뽑아낼 수 있는 가장 긴 군계일학 수열의 길이를 출력한다.

서브태스크 1 (20점)

  • N ≤ 10

서브태스크 2 (15점)

  • N ≤ 1,000

서브태스크 3 (65점)

  • 문제에서 주어진 제약 조건 외 조건 없음

예제 입력 1 

6
1 2 3 4 5 6

예제 출력 1 

6

예제 입력 2 

3
1 5 2

예제 출력 2 

2

출처

High School 부산일과학고 BSIS배 Code Festival E번

  • 문제의 오타를 찾은 사람: jh05013

채점

  • 예제는 채점하지 않는다.

풀이

https://github.com/Zeta611/Baekjoon/blob/master/15966%20%EA%B5%B0%EA%B3%84%EC%9D%BC%ED%95%99.py 

를 참조했습니다. map 과 배열을 적절히 섞어야 하는 문제입니다. 자세한 내용은 소스코드를 참조해주세요!! 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#-*- coding: utf-8 -*-
= input()
num_arr = map(intraw_input().split())
# 최대 길이를 기록하는 배열
long_arr = [1* n
# 숫자 : 숫자의 배열에 해당하는 인덱스 -> key : value 로 넣는다. 
num_idx_map = {num_arr[0]: 0}
max_long = 1
 
for i in xrange(1, n):
    # 현재 숫자보다 1 작은 숫자가 존재하면 
    # 해당 숫자의 인덱스의 길이에 + 1 을 한 값을 현재 숫자의 길이로 설정
    if num_arr[i] - 1 in num_idx_map:
        long_arr[i] = long_arr[num_idx_map[num_arr[i] - 1]] + 1
        
    # 현재 숫자보다 1 작은 숫자가 없으면, 길이를 1로 설정 
    else:
        long_arr[i] = 1
        
    # max 보다 현재 숫자의 길이가 크면 갱신 
    if long_arr[i] > max_long: 
        max_long = long_arr[i]
        
    # map 에 현재 숫자와 인덱스를 넣어준다
    num_idx_map[num_arr[i]] = i
    
print max_long
cs