[백준 20127] Y-수열

1. 문제

www.acmicpc.net/problem/20127

20127번: Y-수열

2. 접근 방법

드디어 풀었다 ㅠ

못 푼 문제에 들어있는게 싫어서 ^^,, 몇 번이나 시도했는지 모르겠다 후우 ~!,,

 

나는 계속 증가 or 감소 둘 중 하나로만 풀려고 했는데,

 

결국

 

1. 증가 수열이라고 생각했을 때

2. 감소 수열이라고 생각했을 때

 

이렇게 두 개로 나눠서 풀었다.

 

1. 증가 수열이라고 생각 했을 때

1-1. 앞에서부터 쭈욱 확인하다가 감소하는 지점이 존재하면, cnt += 1

1-2. 만약 cnt가 1을 넘긴다면 !! (즉, 감소하는 지점이 여러 개라면)

1-2-1. 옮겨도 증가 수열이 되지 않으므로 return False

1-3.

수열을 다 확인한 뒤, 현재 수열의 맨 뒤와 맨 앞을 확인했을 때 맨 뒤의 숫자가 맨 앞의 숫자보다 작거나 같을 경우 --> 옮길 수 있으므로 감소한 지점을 return

혹은

감소한 지점이 하나도 없을 경우 -1을 return (증가 수열이 되지 않는 경우를 False로 return 했기 때문)

1-4.

1-3을 제외한 경우 (ex. 현재 수열의 맨 뒤와 맨 앞의 숫자를 비교했을 때 맨 뒤의 숫자가 맨 앞보다 큰 경우)

--> 옮겨도 증가수열이 되지 않으므로 return False

 

2. 감소 수열이라고 생각했을 때도 증가 수열과 동일

 

---

main

 

1. 만약 입력된 값이 1개라면 -> 이동 없어도 되니까 0

2. 만약 입력된 수열이 한 숫자로 이루어졌다면 -> 이동 없어도 되니까 0

exit()로 프로그램 종료 ^^

 

3. 1, 2의 경우가 아니라면, 증가 수열인지 확인하는 함수와 감소 수열인지 확인하는 함수 모두 실행 후 결과 값 저장

4. 각각의 결과 값을 비교

4-1. 만약 현재 수열이 증가 수열이거나 감소 수열이라면 --> 옮길 필요가 없으므로 print(0)

4-2. 4-1의 경우가 아닐경우

4-2-1. 증가 수열, 감소 수열 모두가 되는 경우 -> 더 작은 값으로 반환 (ex. 3 3 4 4 3 3)

4-2-2. 증가 수열만 가능한 경우 -> idx 반환

4-2-3. 감소 수열만 가능한 경우 -> idx 반환

4-2-4. 증가 수열, 감소 수열 모두 불가능한 경우 -> -1반환

3. 코드

python

# 증가수열
def isBig():
    global N, inputs
    cnt = 0
    small = -1
    for i in range(1, N):
        if inputs[i-1] > inputs[i]:
            cnt += 1
            small = i
        if cnt > 1:
            return False
    if inputs[-1] <= inputs[0] or cnt == 0:
        return small
    else:
        return False

# 감소수열
def isSmall():
    global N, inputs
    cnt = 0
    big = -1
    for i in range(1, N):
        if inputs[i-1] < inputs[i]:
            cnt += 1
            big = i
        if cnt > 1:
            return False
    if inputs[-1] >= inputs[0] or cnt == 0:
        return big
    else:
        return False

N = int(input())
inputs = list(map(int, input().split()))

if N == 1 or len(set(inputs)) == 1:
    print(0)
    exit()

big_answer = isBig()
small_answer = isSmall()
print(big_answer, small_answer)
if big_answer == -1 or small_answer == -1:
    print(0)
else:
    if small_answer and big_answer:
        print(min(small_answer, big_answer))
    elif small_answer and not big_answer:
        print(small_answer)
    elif big_answer and not small_answer:
        print(big_answer)
    else:
        print(-1)

4. 마치며

드디어 풀이한 내 오랜 .. 숙제같은 문제였음

 

흥

 

참고로 테스트 케이스를 추가하자면

'''
10
3 3 3 3 4 3 3 3 3 3
-> 4

6
2 2 3 3 4 4
-> 0

4
1 1 2 2
-> 0
'''

요런 것들이 있습니다.