백준 18870
실버 2를 풀다니.. 감격 !!
문제
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
문제 풀이
처음에 이게 뭔 문제인가.. 싶었다.
그러니까 좌표는 중복된 정렬되지 않은 수열이고,
좌표 압축의 뜻은 중복되지 않은 정렬된 수열이라는 뜻이다.
풀이
내가 생각한 알고리즘 : 시간초과
- 좌표값을 전부 입력받는다. (리스트 1)
- 다른 리스트에 리스트 1번을 정렬하고, 중복된 수를 없애 저장한다. (리스트 2)
- 리스트 1을 하나씩 돌면서 리스트 2의 인덱스를 다른 리스트에 저장한다. (리스트 3)
-> 파이썬 함수의 list.index() 활용 - 리스트 3을 출력한다. 사실 나는 원래 set로 접근을 했는데, 그러면 인덱싱과 정렬을 할 수 없다는 것을 깨닫고, set -> list로 변환하는 로직을 사용했다.
틀린 코드 : 시간초과
n = int(input()) num_list = list(map(int, input().split(' '))) num_list_sort = num_list.copy()
num_list_sort.sort(reverse=True)
num_list_sort = sorted(set(num_list_sort))
result = []
for i in range(0, n):
result.append(num_list_sort.index(num_list[i]))
print(' '.join(map(str, result)))
#### 시간 초과의 이유
바로 파이썬 내장 함수의 로직 list.index() 사용 때문이다.
다음을 보면 알 수 있다.
``` python
def index(self, __value: _T, __start: SupportsIndex = 0, __stop: SupportsIndex = sys.maxsize) -> int: ...
즉, 0번째부터 해당하는 원소가 나올 때까지 순환을 하는 것이다.
이렇게 로직을 짜니 매번 들어오는 원소마다 0 ~ 해당 index 까지 계속 반복을 하는 것이다.
리스트가 짧을 때는 괜찮지만, 만약 리스트 길이가 10000000 이라면?
정말 에-바.
개선한 알고리즘 : 정답
위의 index 검색 알고리즘을 이진 탐색으로 구현 하였다.
덕분에 이진 탐색 알고리즘을 복기 하였다.
last = list의 마지막 인덱스
start = list의 첫번째 인덱스
mid = ( last + start ) / 2
이렇게 하면서 만약 내가 찾고자 하는 num이
list[mid] 의 원소보다 작다면,
last = mid - 1
list[mid] 의 원소보다 크다면,
start = mid + 1
으로 설정한 뒤에 반복하면 되는 것이다.
정답 코드
n = int(input())
num_list = list(map(int, input().split(' ')))
num_list_sort = num_list.copy()
num_list_sort = sorted(set(num_list_sort))
def find_index(num):
last = len(num_list_sort)
start = 0
mid = int((last + start)/2)
while(True):
mid = int((last + start)/2)
if num == num_list_sort[mid]:
return mid
elif num > num_list_sort[mid]:
start = mid
elif num < num_list_sort[mid]:
last = mid
return mid
result = []
for i in range(0, n):
index = find_index(num_list[i])
result.append(index)
print(' '.join(map(str, result)))Lesson Learn
이 문제를 풀면서 파이썬 문법을 반드시 짚고 넘어가야 한다는 생각을 했다.
map( ) 함수는 iterator를 반환한다 : 내가 원하는 형식 설정하기 !
num_list = list(map(int, input().split(' ')))나는 원래 list()를 안쓰고 num_list = map(int, input().split(' ')) 이렇게 쓰면 자동으로 list로 되겠지? 했는데 아니더라.. ㅎㅎ
저렇게 쓰면 iterator를 반환하니까 원하는 형식으로 반드시 설정하자 !
list를 = 으로 동일하다고 하면 수정사항까지 동일해진다. : copy() 활용하기
num_list 변수에 할당된 리스트를 num_list_sort 변수에 할당하게 되면, 두 변수가 동일한 리스트 객체를 참조하게 됩니다.
따라서 num_list_sort.sort(reverse=True) 라인에서 num_list가 정렬되면 num_list_sort도 같은 리스트를 참조하기 때문에 정렬된다.
원본 리스트인 num_list를 유지한 채 정렬된 결과를 얻으려면 num_list를 복사한 후 정렬하면 됩니다.
## 잘못된 코드
num_list_sort = num_list
# num_list를 복사하여 num_list_sort에 할당하는 방법
num_list_sort = num_list.copy()sort() 메서드는 리스트를 정렬하고 None을 반환한다. : sorted() 사용하기
나는 원래 num_list_sort = list(set(num_list.sort())).sort() 이렇게 했다.
그런데 문제가 발생했다.
1. num_list가 sort되어 저장되는 것. (num_list는 un sort 여야 한다.)
2. None이 저장되는 것.
알고보니 sort() 함수는 정렬만 하는 역할을 하고, 객체 반환은 하지 않는다.
만약 정렬된 리스트를 사용하고 싶다면 sorted() 를 사용하면 된다.
sorted() 함수는 Python에서 내장 함수 중 하나로, iterable 객체(예: 리스트, 튜플, 문자열 등)를 정렬하여 새로운 리스트로 반환합니다. sorted() 함수는 원본 iterable 객체를 변경하지 않고 정렬된 결과를 반환합니다.
예를 들어, 다음과 같이 사용할 수 있습니다:
my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5]
sorted_list = sorted(my_list)
print(sorted_list) # 출력: [1, 1, 2, 3, 4, 5, 5, 6, 9]위 코드에서 sorted() 함수는 my_list의 요소를 정렬하여 새로운 리스트를 반환합니다. 원본 리스트 my_list는 변경되지 않습니다.
또한 sorted() 함수는 기본적으로 오름차순으로 정렬하지만, reverse 매개변수를 사용하여 내림차순으로 정렬할 수도 있습니다. 예를 들어:
my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5]
sorted_list_reverse = sorted(my_list, reverse=True)
print(sorted_list_reverse) # 출력: [9, 6, 5, 5, 4, 3, 2, 1, 1]이렇게 함으로써 sorted() 함수는 원본 리스트를 변경하지 않고도 정렬된 결과를 얻을 수 있습니다.
리스트 출력할때 원소 사이에 공백 두고 출력하는 방법
이건 외우자 !
print(' '.join(map(str, result)))정렬 알고리즘 복습하기
이거는 내일 다시 공부하면서 정리해야겠다.
