[Python] 1015번 : 수열 정렬

 

문제 설명 3줄 요약

 

1. 길이가 N인 수열 P(0부터 N-1까지의 수를 한번씩 포함), 길이가 N인 배열 A, 길이가 N인 배열 B가 있다.

2. 수열 P를 배열 A에 적용하면 배열 B가 된다. B[P[i]] = A[i]

3. 배열 A가 주어졌을 때, 수열 P를 적용하면 비내림차순이 된다. 수열 P를 찾아라!

 

 

 

문제에서 포인트는

비내림차순 과 B[P[i]] = A[i] 식을 만족하는 것!

 

여기서 비내림차순은

이해하기로는.. 오름차순에서 같은 원소가 있을 때를

고려해준 정렬 방법이라고 이해하고 풀었다!

 

Ex) 1, 2, 3 = 오름차순, 비내림차순

      1, 2, 2, 3 = 비내림차순

 

이해했다면

입력 조건을 만족하는 틀 부터 짜보자!

 

# 배열 A의 크기 N 입력, ex) 3
N = int(input())

# 배열 A의 원소 입력, ex) A = 2 3 1
A = list(map(int, input().split()))

# 배열 A를 정렬한 배열 B, ex) B = 1 2 3
B = A.copy()
B.sort()

# 수열 p
p = list()

 

그냥 오름차순이라면 쉽겠지만,

비내림차순 이기 때문에

같은 숫자가 있을 때, 사전순 이라는 조건을 만족해줘야한다!

 

if __name__ == '__main__':
    for i in range(N):
        # 정렬된 배열 B에 A[i] 원소가 있으면, 위치 반환
        # ex) A[0] = 2, B.index(2) = 1 따라서 catch = 1 
        # B[P[i]] = A[i] 이므로 곧 catch가 P[i]이다.
        catch = B.index(A[i])
        
        # catch가 마지막 원소인 경우
        if (catch < N-1):
            # 다음 원소와 같지 않을 때
            if (B[catch] != B[catch+1]):
                p.append(B.index(A[i]))
            # 다음 원소와 같다면, 사전순으로 넣기
            elif (B[catch] == B[catch+1]):
                p.append(B.index(A[i]))
                B[catch] = -1
        # catch가 마지막 원소가 아닌 경우
        elif ~(catch < N-1):
            p.append(B.index(A[i]))
    
    # list p 문자열로 합치기
    answer = " ".join(str(value) for value in p)
    print(answer)

 

A가 예시와 같이

A[0] = 2, A[1] = 3, A[2] = 1 이고

B[0] = 1, B[1] = 2, B[2] = 3 일 때,

 

B[P[I]] = A[I]   →   B[P[0]] = A[0]   →    B[P[0]] = 2    →     P[0] = 1

위의 코드에서 catch 는 P[i] 를 의미한다!

 

 

결과

 

 

마지막에 list를 문자열로 바꿔주지 않아서

뭐가 틀린건지 계속 고민하고 있었다..!

 

제출 형식도 잊지말고 확인할 것