Do it 알고리즘 코딩 테스트 - 16번

문제.

https://www.acmicpc.net/problem/1377

1377번: 버블 소트

---

코드.

n = int(input())
a = []
c = []

for i in range(n):
    x = int(input())
    a.append(x)

b = sorted(a)

for i in range(n):
    num = 0
    while a[i] != b[num]:
        num += 1
    y = i - num
    c.append(y)

z = max(c)
print(z+1)

입력 값	출력 값
5 10 1 5 2 3	3

---

해석 및 풀이.

★ 이 문제는 N만큼의 정수를 입력받고 그 수들을 오름차순으로 정렬을 해준 뒤 기존의 인덱스와 변동한 위치의 인덱스를 빼서 결과값의 최대값을 구하고 거기에 +1 을 해서 출력하는 프로그램을 만드는 문제입니다. 

이때 sort(reverse=True) 함수를 쓰지 않을것을 권장하는데 저는 주저없이 사용했다는 점 참고 부탁드립니다. 

n = int(input())
a = []
c = []

먼저 N만큼의 정수를 입력받을 input() 함수를 만들어주고 숫자를 입력 순서대로 넣어줄 리스트 a 와 인덱스의 위치변화값을 넣어줄 리스트 c 를 만들어 줍니다. 

for i in range(n):
    x = int(input())
    a.append(x)

b = sorted(a)

다음으로는 입력 받은 정수만큼 임의로 받은 숫자들을 리스트 a 넣어주고 sorted() 함수를 이용하여 오름차순으로 리스트 b 에 넣어줍니다.

for i in range(n):
    num = 0
    while a[i] != b[num]:
        num += 1
    y = i - num
    c.append(y)

이후 기존에 있던 리스트 a 와 새로 배치된 리스트 b  데이터들의 인덱스를 파악해 그 값을 빼주는데 반복문을 이용해서 범위만큼 돌려주고 반복문을 한번 더 이용해서 같은 값이 어느 위치에 있는지 파악해줍니다. 만약 그 값을 찾았을 경우 기존의 위치와 변경된 위치를 바로 계산하여 리스트 c 에 추가해줍니다.

z = max(c)
print(z+1)

마지막으로 리스트 c 의 최대값을 출력하여 +1 을 해준다음 print로 출력해줍니다.