Q 10825. 국영수(시간 1초, 메모리 256MB)
https://www.acmicpc.net/problem/10825
input :
- 학생 N 명의 이름, 국. 영. 수 점수 공백으로 구분 N(1 <= N <= 100,000) (1 <= 점수 <= 100) 이름.(입력시 문자열로 받음)
output :
- 정렬된 학생의 이름을 출력.
조건 :
1. 국어 점수 감소하는 순서 (내림차순)
2. 국어 점수 동일 -> 영어 점수 증가하는 순서 (오름차순)
3. 국. 영. 점수 동일 -> 수학 점수 감소하는 순서. (내림차순)
4. 모든 점수 동일 -> 이름이 사전 순으로 증가 (오름차순)
--------------------------------------------------------------------
공간 복잡도를 많이 이용하면 쉽게 갈수 있지 않을까?
50 80 60 70 (국어 점수 체크)
삽입 정렬의 알고리즘 따라서, 첫째(정렬되어 있는 요소)와 비교 하며 앞의 원소보다 클 경우 교체.
인제 80 안에서 (영어 점수 체크)
삽입 정렬의 알고리즘 따라서. 첫째(정렬되어 있는 요소)와 비교 하며 앞의 원소보다 작을 경우 교체.
(수학 점수 체크)
삽입 정렬의 알고리즘 따라서. 첫째(정렬되어 있는 요소)와 비교 하며 앞의 원소보다 클 경우 교체.
(이름 체크)
모든 점수가 동일 하다는 것. 표시가 필요하다. <<- 현재 다른 분류는 다 마친 상태.
만약 모든 점수가 동일한 요소가 있다면 연속적으로 있는 상황. 전체 리스트를 iterate하면서 점수가 동일한 요소 있으면 비교하게 하자.
응 너무 오래 걸려.
내가 만들려 하지 말고 있는걸 쓰자.
sort(array, key = ) 키를 이용해서
https://velog.io/@aonee/Python-%EC%A0%95%EB%A0%AC-sort-sorted-reverse
튜플, 리스트 둘 다 이용할 수 있지만,
튜플이 더 나을 듯.
key = lambda x : (-(int)x[1], (int)x[2], -(int)x[3], x[0])
Q 18310. 안테나(시간 1초, 메모리 256MB)
https://www.acmicpc.net/problem/18310
input :
- 집의 수 N(1 <= N <= 200,000) 집의 위치 공백으로 구분. (1 <= 집의 위치 <= 100,000)
output :
- 안테나를 설치할 위치 출력. (여러 개의 값일 경우 가장 작은 값 출력.)
조건 :
특정 위치의 집에 한 개의 안테나를 설치하기로 결정.
안테나로부터 모든 집까지의 거리의 총합이 최소가 되도록.
안테나는 집이 위치한 곳에만 설치.
동일한 위치에 여러 개의 집이 존재하는 것 가능.
어차피 집 에만 설치 가능.
모든 집에 설치해보게 하며 거리를 구할 경우의 시간 복잡도는?
O(N^2)40억은 1초로 안 되니 실패.
1, 5, 7, 9 거리가 최소가 되려면. 끝 부분에 있으면 안 되고 가운데에 있어야 함.
입력 받은 값을 우선 정렬.(NlogN(?))
입력 받은 값이 홀수 일 경우 -> 한 가운데에 존재하는 집이 있다.
입력 받은 값이 짝수 일 경우 -> 중심에 위치하는 2집중 하나가 정답.
중간 값을 구해야함.
정답의 조건중 여러 개의 값일 경우 가장 작은 값을 출력하기 때문에 중간 값을 구할 때.
N // 2 가 아닌 N - 1 // 2 를 하여 주면 여러 개 중 작은 값을 구할 수 있다.
