Algorithm/Greedy

[Python] 1083 소트

턴태 2022. 6. 19. 13:43

문제

크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 원소가 차례대로 주어진다. 이 값은 1000000보다 작거나 같은 자연수이다. 마지막 줄에는 S가 주어진다. S는 1000000보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

문제 풀이

A. 접근

권국원님의 「보통의 취준생을 위한 코딩 테스트 with 파이썬」을 참고하여 작성

솔직히 여전히 어려운 문제이다. 이 문제에서의 핵심은 사전순으로 가장 뒷서는 것을 출력하는 것이다. 즉 내림차순으로 정렬을 해야 한다는 것이다. 이때, 버블 정렬을 통해서 정렬한다는 것이 특징이다. 또한, 정렬을 S번 할 수 있다는 제약도 있다.

예를 들어, n = 7이고,
10 20 30 40 50 60 70이 입력으로 주어진 상황에서 s가 3이라고 가정했을 때,
40 10 20 30 50 60 70이 정답이다.

같은 입력에서 s가 4라고 가정했을 때,
50 10 20 30 40 60 70이 정답이다.

s가 5일 때는
60 10 20 30 40 50 70,

s가 6일 때는
70 10 20 30 40 50 60이 정답이다.

계속해서 s가 7일 때는
70 20 10 30 40 50 60이 정답이다.

for문으로 배열 전체를 한 번씩 돌고, 각 카운팅마다 모든 배열을 순회하며 i번째 인덱스보다 크며 s 횟수에서 가능한 수를 찾을 수 있게 작성하면 된다. s의 횟수는 인덱스의 차이와 관련이 있다. 배열의 앞쪽에는 더 큰 수가 와야 하며, 그 과정에서 인덱스의 차이 만큼 s를 사용하기 때문이다.

B. 문제 풀이

전체 코드

n = int(input())

num = [int(i) for i in input().split()]

s = int(input())

while True:
    switch = False
    for i in range(n):
        idx = i
        cmp = 0
        for j in range(n-1, i, -1):
            if num[idx] < num[j] and j - i <= s:
                idx = j
                switch = True
                cmp = j - i
        if idx != i:
            tmp = num[idx]
            del num[idx]
            num.insert(i, tmp)
            s -= cmp
            break
    if switch == False:
        break

print(*num)

B-1. 준비

n = int(input())

num = [int(i) for i in input().split()]

s = int(input())

while True:
    switch = False
    for i in range(n):
        idx = i
        cmp = 0

n과 배열, s를 받을 변수를 준비한다.

공백으로 구분된 입력을 리스트로 변환할 때는

arr = list(map(int, input().split()))

혹은

arr = [int(i) for i in input().split()]

둘 중 하나를 선택하면 된다. 실제 제출에서도 메모리나 시간 차이가 없었다. 굳이 차이는 코드 길이가 위의 경우가 2 바이트 더 적다는 것.

while 반복문을 통해 계속해서 반복하도록 구성하였고 switch는 특정 상황에서만 반복하도록 설정했다.

for문을 순회하며 값을 수정하도록 한다. 이때 카운팅 변수 i를 idx에 넣어서 바꿀 값을 정하였고, cmp는 얼마나 s를 사용했는지 기록하기 위한 변수이다.

B-2. 풀이

        for j in range(n-1, i, -1):
            if num[idx] < num[j] and j - i <= s:
                idx = j
                switch = True
                cmp = j - i
        if idx != i:
            tmp = num[idx]
            del num[idx]
            num.insert(i, tmp)
            s -= cmp
            break
    if switch == False:
        break

print(*num)

두 번째 for 문의 range 인자들은 i + 1, n으로 해도 사실 상관 없다. 교체를 해주기 위해서 가장 큰 값을 탐색한다. 이때, s의 횟수와 j, i의 인덱스 차이를 고려해서 탐색한다. 만약 만족하는 값을 찾으면 정렬을 더 할 수 있는 것으로 간주해 switch 변수를 True로 바꾼다. 그렇게 하여 idx(가장 큰 수 인덱스)와 i가 다르다면(소트가 발생했다면) 그 값을 i의 위치에 놓고 s 값을 빼준다.

break로 반복문을 탈출하는 이유는 다시 왼쪽에서부터 순회하기 위해서인데, 제출할 때 break를 주석처리해도 사실 프로세스는 동일해서 정답이다.

총평

왜 그리디 알고리즘인지 몰랐는데, 매번 큰 값을 찾아서 문제를 풀어야 하기 때문이다. 그리디가 꽤 까다로운 알고리즘인 것 같다. 그리디라고 해서 크게 특별한 알고리즘은 없으나 사고방식을 항상 탐욕스럽게 하여 구현한다는 점에서 전체적으로 알고리즘 문제를 풀 때 도움이 된다고 생각한다. 또한, while 문에서 switch 혹은 tof(true or false) 등의 변수를 통해서 반복문을 조건에 따라 반복하는 것도 좋은 방법이었다.

 

저작자표시 비영리