졍's 기술 블로그

이전 순열

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 구현, 조합론

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

예제 입출력

Algorithm

Greedy 이용
1. 입력 순열을 리스트로 받음
2. N이 1이거나 리스트가 오름차순 정렬되어있으면 -1 출력
3. 리스트의 마지막 숫자가 1보다 크면
3.1. 리스트의 끝에서부터 내림차순 정렬되어있는 부분 모두 pop
3.2. 리스트의 (마지막 숫자 - 1) % (N+1)을 저장하고 pop한 후 저장된 숫자 append
    ☞ (마지막 숫자 - 1) % (N+1)가 리스트 내에 존재하지 않아야 함
4. 리스트의 마지막 숫자가 1이면
4.1. pop하고 리스트의 (마지막 숫자 - 1) % (N+1)을 저장하고 pop한 후 저장된 숫자 append
    ☞ (마지막 숫자 - 1) % (N+1)가 리스트 내에 존재하지 않아야 함
5. 남은 자리수 stack에 포함되어있지 않은 값으로 채우기

Code

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

# N이 1이거나 리스트가 오름차순 정렬되어있으면 -1 출력
if N == 1 or stack == list(range(1, N+1)):
    print(-1)
else:
    # 리스트의 마지막 숫자가 1보다 크면
    if stack[-1] > 1:
        # 리스트의 끝에서부터 처음으로 가면서 내림차순 정렬되어있는 부분 모두 pop
        for index in range(N-1, 0, -1):
            if stack[index-1] < stack[index]:
                stack.pop()
            else:
                break
        stack.pop()
        
        # 다음에 들어가야할 숫자 저장
        next_num = (stack[-1] - 1) % (N+1)
        if next_num == 0:
            next_num = N-1
        while next_num in stack:
            next_num = (next_num - 1) % (N+1)
            if next_num == 0:
                next_num = N-1

        # 리스트의 마지막 원소를 새로운 숫자로 변경
        stack.pop()
        stack.append(next_num)
        
        # 리스트 나머지 자리 채우기
        for num in range(N, 0, -1):
            if num not in stack:
                stack.append(num)
    else:
        stack.pop()

        # 다음에 들어가야할 숫자 저장
        next_num = (stack[-1] - 1) % (N+1)
        if next_num == 0:
            next_num = N-1
        while next_num in stack:
            next_num = (next_num - 1) % (N+1)
            if next_num == 0:
                next_num = N-1

        # 리스트의 마지막 원소를 새로운 숫자로 변경
        stack.pop()
        stack.append(next_num)
        
        # 리스트 나머지 자리 채우기
        for num in range(N, 0, -1):
            if num not in stack:
                stack.append(num)

    print(' '.join(list(map(str, stack))))

메모리: 30864 KB
시간: 640 ms

다음 순열

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 조합론

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

예제 입출력

Algorithm

Greedy 이용
1. 입력 숫자를 리스트에 받음
2. N이 1이면 -1 출력
3. nums의 마지막 숫자가 N보다 작으면
3.1. 끝에서부터 증가하는 숫자인 경우 모두 pop
3.2. 리스트가 비어있으면 -1 pop
3.3. 리스트가 비어있지 않으면 마지막 값 + 1을 저장해두고 pop후 저장해둔 값 append해서 출력
    ☞ 마지막 값 + 1이 N을 넘지 않아야하고 리스트에 들어있지 않은 숫자여야 함
4. nums의 마지막 숫자가 N이면
4.1. 2번 pop
4.2. 마지막 값 + 1을 저장해두고 pop후 저장해둔 값 append해서 출력
   ☞ 마지막 값 + 1이 N을 넘지 않아야하고 리스트에 들어있지 않은 숫자여야 함

Code

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

# 한자리숫자이면 -1 출력
if N == 1:
    print(-1)
# nums의 마지막 숫자가 N보다 작으면 끝에서부터 1씩 증가하는 부분 모두 pop
elif nums[-1] < N:
    for index in range(N-1, 0, -1):
        if nums[index-1] > nums[index]:
            nums.pop()
            # nums의 길이가 1인데 값이 N이면 -1출력
            if len(nums) == 1 and nums[0] == N:
                print(-1)
                break
        else:
            break
    nums.pop()
    # nums가 빈 리스트가 아니면
    if nums:
        # 다음에 올 숫자 저장
        num = (nums[-1] + 1) % (N + 1)
        if num == 0:
            num += 1
        # 이미 포함되어있는 숫자인지 확인
        while num in nums:
            if num in nums:
                num = (num + 1) % (N+1)
        
        nums.pop()
        nums.append(num)
        
        for num in range(1, N+1):
            if num not in nums:
                nums.append(num)
        print(' '.join(list(map(str, nums))))
# nums의 마지막 숫자가 N이면 2번 pop
else:
    nums.pop()
    num = (nums[-1]+1)%(N+1)
    if num == 0:
            num += 1
    # 이미 포함되어있는 숫자인지 확인
    while num in nums:
        if num in nums:
            num = (num + 1) % (N+1)

    nums.pop()
    nums.append(num)

    # 숫자를 1부터 N까지 확인하면서 들어있지 않은 숫자이면 append
    for num in range(1, N+1):
        if num not in nums:
            nums.append(num)
    print(' '.join(list(map(str, nums))))

메모리: 30864 KB
시간: 996 ms

1. Greedy(탐욕법)

: 현재 상황에서 지금 당장 좋은 것만 고르는 방법

• 정당성 분석이 중요하다.
  : 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야 한다.
• 일반적인 상황에서는 최적의 해를 보장할 수 없지만 코딩 테스트에서는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제된다.

참고

https://youtu.be/2zjoKjt97vQ