Day 4 코딩테스트_정렬

가연·2024년 12월 10일
ASAC7기python코딩테스트

정렬 코딩테스트 연습

기준을 가지고 기준에 맞춰 순서를 정리하는 것
(위치, 값의 크기, 알파벳 순 ...)

코테에서 정렬은 개별적인 알고리즘이 아니라 중간에 1~2줄 사용됨.
원하는 대로 정렬 규칙을 세팅하고 필요한 자료형을 구성하고 설정하는 것이 중요함.

정렬

  1. list.sort() method : 원본이 바로 변경 (사라짐)
  2. 파이썬 자체의 sorted(list) 함수 : 원본 유지, 변경된 결과를 따로 할당/연결해야함
  • 값 크기 기준으로 정렬
    True : 내림차순 / False : 오름차순 (defalut)
    list.sort(reverse=True)
  • 단순 순서상 재배치
    reverse() method / reversed() 함수 (값 크기가 아니라 위치 기준!)

특별한 정렬 기준 (lambda)

lambda 함수로 규칙 기술. 지정하지 않은 규칙의 경우 원본 순서를 따른다.
🆚 sorted는 순차적으로 정렬(동일하면 그 다음 것 크기 따짐)

ex/ 맨 앞 글자 1개 기준으로 정렬하려고 함. 그 외 글자는 신경 X, 겹치면 원본 순서대로
sorted(list, key=lambda x:x[0])
ex/ 2번째 글자 기준으로 정렬.
sorted(list, key=lambda x:x[1])
ex/ 길이 기준 내림차순 정렬.
sorted(list, key=lambda x: len(x), reverse=True)
ex/ 여러 가지 기준 정렬. ( 그냥 sorted처럼 정렬한다면? )
sorted(list, key=lambda x: (x[0], x[1], ..)

  • AM 적인 간단한 정렬
    +/- 부호
    sorted(list, key=lambda x: -x[1]) -> 내림차순 정렬

혼재된 방향성을 사용하는 경우

1정렬 기준 : 오름차순, 2정렬 기준 : 내림차순
→ +/- 부호 이용
sorted(list, key=lambda x: (x[0], -x[1])
🆚 reverse parameter 이용 = 다 같은 방향으로 정렬
sorted(list, key=lambda x: (x[0], x[1]), reverse=True

01. 정렬_실패율

Q.
실패율은 다음과 같이 정의한다.
= 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
 전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

[제한사항]
스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
stages의 길이는 1 이상 200,000 이하이다.
stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

[입출력 예]
N : 5
stages : [2,1,2,6,2,4,3,3]
result : [4,1,2,3]

1번 스테이지에는 총 8명의 사용자가 도전했으며, 이 중 1명의 사용자가 아직 클리어하지 못했다. 따라서 실패율은 다음과 같다.
1번 스테이지 실패율 : 1/8
2번 스테이지에는 총 7명의 사용자가 도전했으며, 이 중 3명의 사용자가 아직 클리어하지 못했다. 따라서 실패율은 다음과 같다.
2번 스테이지 실패율 : 3/7
마찬가지로 나머지 스테이지의 실패율은 다음과 같다.
3번 스테이지 실패율 : 2/4
4번 스테이지 실패율 : 1/2
5번 스테이지 실패율 : 0/1
각 스테이지의 번호를 실패율의 내림차순으로 정렬하면 다음과 같다.
[3,4,2,1,5]


A.
#입력
N : stage 개수
stages : 사용자가 현재 멈춰있는 stage 번호 list

#계산
i번째 stage에서
도전자 : (i-1)stage 도전자 - (i-1)stage의 실패자 = i-stage 도전자
 * i=1에서는 i-1 = 0번째 스테이지, 총 도전자=유저 수 len(stages)
실패자 : 값이 i인 것들의 개수
 * filtering/counting : list.count(x) or LC len([i for i in a if i==2])
실패율 : i_F = i_실패자 수/i_도전자 수
* i_도전자 수 = 0 이면 i_F = 0


def solution(N, stages):
answer = []

1. 필요한 정보들 세팅

1.1 dict로 기본 정보 처리. k : stage 번호, v : 실패율
fail_dict = { } # stage 돌아가며 추가
 * list로 정리할 경우 .append()로 추가, stage와 실패율 나눠서 list 생성해야함.

1.2 도전자 수 # stage 돌아가며 갱신
num_people = len(stages) # 첫 번째 stage 도전자 수

2. 큰 구조 - stage 돌아가며 실패율 계산 (range로 롤링)

for i_stage in range(1,N+1) : # i 번째 stage 롤링

2.1 i번째 stage에서 실패자 수 : counting(filtering)
fail_num = stages.count(i_stage)
or
fail_num = len([i for i in a if i==2])
2.2 실패율
if num_people > 0 : # 참가자 존재할 경우 계산
fail_dict[i_stage] = fail_num / num_people
else : # 참가자 0명일 경우 정의대로(0) 세팅
fail_dict[i_stage] = 0
2.3 다음 라운드의 참가자에 대한 정보 갱신
num_people -= fail_num

3. 출력을 위한 정리&정렬

정렬 1 기준 : 실패율, 내림차순 -x[1]
정렬 2 기준 : stage 번호, 오름차순 x[0]
# 정렬의 1기준은 key, 2기준은 value -> 둘 다 필요 -> .items() 사용
# fail_dict.items() -> [(stage 번호, 실패율), ( , ), ( , ) ...]
fail_list = sorted(fail_dict.items(), key=lambda x : (-x[1], x[0]))

4. 최종 출력(LC)

answer = [fail_info[0] for fail_info in fail_list]

답안 코드

def solution(N, stages):
    answer = []
    fail_dict = {} 
    num_people = len(stages) 
    for i_stage in range(1, N+1):
        fail_num = stages.count(i_stage)
        if num_people > 0: 
            fail_dict[i_stage] = fail_num / num_people
        else: 
            fail_dict[i_stage] = 0
        num_people -= fail_num
    fail_list = sorted(fail_dict.items(), key=lambda x:(x[1], x[0]))
    answer = [fail_info[0] for fail_info in fail_list]
    return answer

02. 정렬_파일이름

Q.

 저장소 서버에는 프로그램의 과거 버전을 모두 담고 있어, 이름 순으로 정렬된 파일 목록은 보기가 불편했다. 파일을 이름 순으로 정렬하면 나중에 만들어진 ver-10.zip이 ver-9.zip보다 먼저 표시되기 때문이다.

버전 번호 외에도 숫자가 포함된 파일 목록은 여러 면에서 관리하기 불편했다. 예컨대 파일 목록이 ["img12.png", "img10.png", "img2.png", "img1.png"]일 경우, 일반적인 정렬은 ["img1.png", "img10.png", "img12.png", "img2.png"] 순이 되지만, 숫자 순으로 정렬된 ["img1.png", "img2.png", "img10.png", img12.png"] 순이 훨씬 자연스럽다.

무지는 단순한 문자 코드 순이 아닌, 파일명에 포함된 숫자를 반영한 정렬 기능을 저장소 관리 프로그램에 구현하기로 했다.

소스 파일 저장소에 저장된 파일명은 100 글자 이내로, 영문 대소문자, 숫자, 공백(" "), 마침표("."), 빼기 부호("-")만으로 이루어져 있다. 파일명은 영문자로 시작하며, 숫자를 하나 이상 포함하고 있다.

파일명은 크게 HEAD, NUMBER, TAIL의 세 부분으로 구성된다.

HEAD는 숫자가 아닌 문자로 이루어져 있으며, 최소한 한 글자 이상이다.
NUMBER는 한 글자에서 최대 다섯 글자 사이의 연속된 숫자로 이루어져 있으며, 앞쪽에 0이 올 수 있다. 0부터 99999 사이의 숫자로, 00000이나 0101 등도 가능하다.
TAIL은 그 나머지 부분으로, 여기에는 숫자가 다시 나타날 수도 있으며, 아무 글자도 없을 수 있다.

파일명HEADNUMBERTAIL
foo9.txtfoo9.txt
foo010bar020.zipfoo010bar020.zip
F-15F-15(빈 문자열)

파일명을 세 부분으로 나눈 후, 다음 기준에 따라 파일명을 정렬한다.

  • 파일명은 우선 HEAD 부분을 기준으로 사전 순으로 정렬한다. 이때, 문자열 비교 시 대소문자 구분을 하지 않는다. MUZI와 muzi, MuZi는 정렬 시에 같은 순서로 취급된다.
  • 파일명의 HEAD 부분이 대소문자 차이 외에는 같을 경우, NUMBER의 숫자 순으로 정렬한다. 9 < 10 < 0011 < 012 < 13 < 014 순으로 정렬된다. 숫자 앞의 0은 무시되며, 012와 12는 정렬 시에 같은 같은 값으로 처리된다.
  • 두 파일의 HEAD 부분과, NUMBER의 숫자도 같을 경우, 원래 입력에 주어진 순서를 유지한다. MUZI01.zip과 muzi1.png가 입력으로 들어오면, 정렬 후에도 입력 시 주어진 두 파일의 순서가 바뀌어서는 안 된다.

무지를 도와 파일명 정렬 프로그램을 구현하라.

[입출력]
입력으로 배열 files가 주어진다.

files는 1000 개 이하의 파일명을 포함하는 문자열 배열이다.
각 파일명은 100 글자 이하 길이로, 영문 대소문자, 숫자, 공백(" "), 마침표("."), 빼기 부호("-")만으로 이루어져 있다. 파일명은 영문자로 시작하며, 숫자를 하나 이상 포함하고 있다.
중복된 파일명은 없으나, 대소문자나 숫자 앞부분의 0 차이가 있는 경우는 함께 주어질 수 있다. (muzi1.txt, MUZI1.txt, muzi001.txt, muzi1.TXT는 함께 입력으로 주어질 수 있다.)

입력: ["img12.png", "img10.png", "img02.png", "img1.png", "IMG01.GIF", "img2.JPG"]
출력: ["img1.png", "IMG01.GIF", "img02.png", "img2.JPG", "img10.png", "img12.png"]

입력: ["F-5 Freedom Fighter", "B-50 Superfortress", "A-10 Thunderbolt II", "F-14 Tomcat"]
출력: ["A-10 Thunderbolt II", "B-50 Superfortress", "F-5 Freedom Fighter", "F-14 Tomcat"]


A.
#제한조건
시작은 영문자(대/소)
head, number(숫자)는 무조건 1개 이상 포함
최대 길이 100글자
중복된 파일명은 없다

#입력
(HEAD(str) + NUMBER(int) + TAIL(str)) list

#계산
정보 추출하기 (원본파일명, head, number, 원본순서)
head(str) - 처음 숫자가 나타나기 전까지 / number(int) - 처음 숫자 덩어리 / 원본 순서 - index

  1. HEAD
    알파벳 순서대로 정렬 (오름차순)
    * 대/소문자 구별 X -> 하나로 통일 필요
  2. NUMBER
    if head 동일하다면 :
    number 순서대로 정렬
    * 첫 번째가 0일 때 0은 무시 ( 0010 zero padding. 00010 = 10)
  3. TAIL
    if head, number 동일하다면 :
    원본 순서 그대로. (tail은 정렬 기준에 포함되지 않음 -> 추출 안 함)

#출력
정렬된 원본파일명 list
(내가 세팅한 파일명 X)

정보 추출에 필요한 방법들

# head, number, 원본순서 필요
# 기준 : 파일명에서 처음 나타나는 숫자 (head 와 number의 경계)

  • 정규식 : re 패키지, import re
    문자열 내에서 원하는 패턴을 찾는 룰 (규칙화 문법)
    문자열 앞에 r -> 정규식의 규칙으로 작성된 문자열. 특수문자(+, *, ( ), \, ..)로 사전에 정의해놓은 규칙을 표현함.
    error가 나타나지 않아 엄밀하게 사용해야 함.
    • * : 원하는 패턴 0번 이상 (출현 빈도)
    • + : 원하는 패턴 1번 이상 (출현 빈도)
    • [ ] : [ ] 사이의 문자들과 매치, 하이픈(-)을 사용하면 두 문자 사이의 범위(From - To)를 의미. [a-z]
    • \d - 숫자와 매치, [0-9]와 동일한 표현식
    • \D - 숫자가 아닌 것과 매치, [^0-9]와 동일한 표현식
    • \s - whitespace 문자와 매치, [ \t\n\r\f\v]와 동일한 표현식, 맨 앞의 빈 칸은 공백문자(space)를 의미
    • \S - whitespace 문자가 아닌 것과 매치, [^ \t\n\r\f\v]와 동일한 표현식
    • \w - 문자+숫자(alphanumeric)와 매치, [a-zA-Z0-9_]와 동일한 표현식
    • \W - 문자+숫자 가 아닌 문자와 매치, [^a-zA-Z0-9_]와 동일한 표현식

     정규식을 특정 패턴에 대해 찾을 떄 : re.findall(패턴->규칙(정규식을), 어디서)
     ex/ re.findall(r"\d", temp) : temp에서 숫자(1개)로 이루어진 것 찾기 -> '1', '3', '5', '4', '8', '3' ..
     ex/ re.findall(r"\d+", temp) : temp에서 숫자 1개 이상으로 연결된 것 찾기 -> '13', '548', '3' ..
     ex/ re.findall(r"[a-e]+", temp) : a,b,c,d,e 중 1개 이상 연결된 것 찾기 -> 'abe', 'a', 'eb' ..

  • Zero padding
    : 숫자 앞에 붙은 0 제거 (00010 -> 10)
    자료형 변환 str ↔ int 을 이용함. int('00043') => 43

  • HEAD 추출, NUMBER 추출
    refindall(r"\d+", temp)[0] # 첫 번째 숫자 덩어리 찾기 # number 추출
    문자열.index(숫자) = 문자열에서 숫자가 나오는 곳 index
    temp[:temp.index(refindall(r"\d+", temp)[0])] # slicing하여 문자열(head) 추출

  • 문자열 대소문자 통일
    " ".lower( ) : 소문자 통일
    or
    " ".upper( ) : 대문자 통일


def solution(files):
     answer = []
     return answer

1) List 사용

(head, number, 원본위치, 원본파일명)

1) -1. 필요한 정보 세팅

my_files = []

1)- 2. 입력 files list 돌리면서 원하는 부분 추출하여 list에 담기

for idx, s in enumerate(files): # enumerate로 idx와 file명 추출. file명(s)에서 h, n 추출해야함.
numbers = re.finall(r"\d+", s)[0] # number 추출
real_number = int(numbers) # zero padding
head = s[:s.index(numbers)].lower() # head 추출
my_files.append([head, real_numbers, idx]) # list 형태로([h,n,idx]) list에 담기

1)- 3. 문제에서 주어진 조건대로 정렬

.sort(), .sorted() + key + lambda + (+/-)
my_files.sort(key=lambda x : (x[0], x[1], x[2]))

1)- 4. 최종 제출형으로 정리

원본 위치(idx)를 이용해 원본파일명 추출
answer = [files[j[2]] for h in my_files] #LC
or
for j in my_files :
     answer.append(files[j[2]])

🆚

2) Dict 사용

k : 파일명, v : (head, number, idx)
정렬의 기준은 오로지 value에만 존재

2)- 1. 세팅

my_files = {}

2)- 2. 롤링

for idx, s in enumerate(files): #동일하게 원하는 값들 추출
	p = re.findall(r"\d+", s)[0]
	head = s[:s.index(p)].lower()
	number = int(p)  
	my_files[s] = (head, number, idx) #key값인 파일명에 각 value값들을 tuple 형식으로 담기

2) -3. 정렬

file_list = my_files.items() #정렬하기 위해 list로 (파일명, (h,n,i)) 담기
file_list = sorted(file_list, key=lambda x : (x[1][0], x[1][1], x[1][2])) #정렬. 조건 3개(value의 첫번째(h) 비교, 두번째(n) 비교, 세번째(i) 비교)

or

file_list = sorted(my_files.keys(), key=lambda x :(my_files[x][0], my_files[x][1], my_files[x][2])) #dict 채로 정렬?
# answer = file_list

2) -4. 최종 출력

answer = [for i[0] in file_list]
profile
가연
이전 포스트

Day 3 코딩테스트_구현

다음 포스트

Day 5 정렬 기본 알고리즘, 자료형

0개의 댓글