[ASAC 5일차] 정렬, 정규식

 

3월 27일의 기록

---

매일 일찍와야지 하는 생각과는 다르게 그만.. 늦잠을 자버렸다.

알람 없이도 일어날 수 있을 거라고 생각했는데 나를 너무 믿었나보다.. 아무튼 매일 반복 알람을 다시 맞춰놨으니 늦지말자.

오늘은 어제에 이어서 정렬의 기본 알고리즘을 리뷰하고 이어서 카카오의 2018년 파일명 정리 문제를 풀어보면서 간단한 정렬 연습 문제를 풀어보았다.

0. 목차

---

1. 정렬 기본 알고리즘
   1. 삽입정렬
   2. 선택정렬
   3. 버블정렬
2. 연습 문제) 2018 카카오 블라인드 코딩테스트
3. 자료형 Dict3-2) 연습문제 : 신고 결과 받기
4. 3-1) 연습문제 : 완주하지 못한 선수

1. 정렬 기본 알고리즘

---

삽입 정렬, 선택정렬, 버블 정렬의 차이

1. 선택 정렬 :
   1. 그 단계에서 누가 제일 잘하는지/대장 & 기록
   2. 그 단계에서 대장을 찾고, swap
2. 삽입 정렬:
   1. 카드 정리 —> 정리가 되어 있는 상태에서 하나씩 중간 위치 조정
   2. 중간에 기록지가 필요가 없음.
   3. 새로운 친구가 탐색의 대상이 정리가 끝난 애들 중 자기 자리 찾기
3. 버블 정렬:
   1. 계속 2개씩 뒤로, 뒤로 비교를 진행
   2. 그 단계의 대장을 찾는 것은 선택정렬과 유사하다, 그러나 기록지가 없다
   3. 계속 계속 전진 삽입정렬과 유사하지만 정리가 안 되어 있는 애들 속에서 비교 한다.

2. 연습문제) 2018 카카오 블라인드 코딩테스트 : 파일명 정렬

---

참고) 2018 카카오 블라인드 코딩테스트 : 파일명 정렬

+ 사전 지식) 정규식

• 정규식은 텍스트 문자열을 어떠한 패턴으로 파악하여 식별하는데 사용이 된다. → 내가 지정한 규칙에 해당하는지, 해당하지 않는지에 대해서 알려주게 된다.
• 특정한 패턴을 지닌 문자열을 찾을 수 있어서 텍스트 데이터의 사전처리 및 사후 처리, 필요한 데이터만 추출을 하는데 널리 사용되고 있음.

정규식을 왜 사용할까?

• 문자열에서 원하는 패턴 찾기에 유용하다].
• 따라서, 텍스트 데이터 처리, 수집, 크롤링을 할때

정규식의 특징

• 모든 개발 언어에 다 존재
• 큰 틀은 모든 언어에서 유사하지만 언어마다 조금 다르게 동작한다
• 파이썬 : re 패키지
  • 정규식 사용을 위한 패키지
  • 모른다면 구글링, 부서 스타일, chatGPT etc

기본 정규식 규칙

• 참고) https://greeksharifa.github.io/정규표현식(re)/2018/07/20/regex-usage-01-basic/
• 참고) https://www.delftstack.com/ko/tutorial/python-modules-tutorial/python-regular-expression/
• 참고) https://wikidocs.net/46744
• 메타 문자 : 문자 그대로가 아니라 특정한 기능, 의미를 부여해서 사용하는 문자를 말함

정규식 기본룰

예시)

 

1. “ * “ vs “ + “ : 원하는 패턴이 0번 이상 vs 1번 이상 ⇒ ” [Pp]ython” : "Python" 혹은 "python”

2. [0123456789] : 내가 원하는 것들을 리스트업 & 귀찮음

3. \d == [0-9] : 편하지만 원하는 것들을 리스트업할 수 없다.

4. 예) : 주민번호 XXXXXX - [1~4]XXXXX

5. “hello, 100$” ⇒ 일반 문자열

6. r”hello, 100$” ⇒ 일반 문자열 앞에 r을 붙여 나타냄

7. 정규식에서 사용하는 룰을 나타내는 문자로 인식 한다 .

문제 분석

---

1. 기존 이름 순서 정렬 —> 숫자 크기를 반영을 못함!
2. 따라서, 숫자 크기를 반영해서 정렬 하자

조건

1. 파일명 100글자 이내
2. 영문 대/소
3. 숫자
4. 공백
5. 특수문자(마침표, -)
6. 파일명의 시작 : 영문자로 시작
7. 파일명에 숫자는 무조건 1개 이상
8. 파일명 : head/number/tail
   • head : 오로지 영문/최소 1개 이상
   • number : 숫자 5자리 (제로패딩)
   • tail : 그외, 숫,문/특수 etc

⇒ 코드적으로 정보를

head/number/tail로 구성해야겠다.

---

(정렬 기준) : head/number/tail

• 1기준
  • head → 사전순(오름)
  • 영문 대소문자 구분 X
• 2기준
  • 숫자순으로 정렬(오름차순)
  • 숫자 앞의 0은 무시된다. == zeropadding 신경 안씀
• 3기준
  • 기존 입력에 주어진 순서대로

+) 여기서 생각해야할 것은

• 정렬 기준에서는 tail은 상관 없다.
• 정렬시 필요한 핵심 정보 : head, number, 원본순서

방법 1) 리스트형을 사용해서 만들기

#방법 1) 리스트 사용하여 만들기

def solution(files):
    my_files = []
    # 큰 틀 : 입력으로 받은 files를 다 돌려가면서 원하는 정보
    number_pattern = r"\\d+" #--> ["0012", "333"]

## 내가 모을 정보에 원본의 순서/index가 있기 때문에
    for idx, s in enumerate(files): #files에 (index, file명)
        # 개별 파일에서 필요한 정보를 어떻게 추출 : h,n,i
        # 2-1) 기준 숫자 파트 --> 정규식을 숫자 추출
        number = re.findall(number_pattern, s) #--> ["0012", "333"]
        real_number = int(number[0]) # "0012"(문자열로)
        # 2-2) 앞 부분 head 추출 : 처음부터 ~~~ 숫자파트
        head = s[:s.index(number[0])] # "iMgf0012" --> "iMgf"
        head = head.lower() # "iMgf" -> imgf 소문자로 변환

        # 2-3) 정렬에 필요한 정보들을 모으자!! my_files에 쌓자
        my_files.append([head,real_number,idx])
        # ==> [["imgf", 12,0], ["iaa"], 3, 1]
    # --> 입력으로 받은 모든 파일에 대해 다 처리가 된 상태가 된다.
    # 2) 문제에서 주어진대로 정렬을 수행한다.
    # 기존 룰이 아니라 내가 직접 핸드메이드 해야한다.
    # .sort(), sorted()
    # ==> 원본 파일명 files에 있으니... 그냥 바로 변경
    my_files.sort(key=lambda x:(x[0], x[1], x[2]))
    # 3) 최종 제출 양식으로 스타일 정리
    #    원본 파일 명을 가지고, 기준대로 정리 해서,
    #    파일명을 원소로 가지는 리스트로 출력
    # ==> 원본에 필요한 것들 모으자 : 리스트 컴프리핸션
    answer = [ files[idx[2]] for idx in my_files ]
    return answer

방법 2) Dict을 사용해서 만들어보기

---

# 방법 2) Dict을 사용해서 -> 무엇을 키로 할까?, 무엇을 value로 해볼까
# key는 유니크해야한다. 문제에서 개별 파일명은 중복이 없다했으니! 파일명을 key로 해봐야지!
# value : 정렬에 필요한 정보 ("head", "number")
# 그럼 정렬 기준 1/2까지 같으면 어쩔? ==> 파이썬의 정렬 함수들 동일하면 ... 원본 순서
# dict.items()를 쓰면 원본 순서의 index로 사용가능
import re
#정규식 필요하니까 패키지 임포트하기

def solution(files) :
    my_files = {}
    # 딕셔너리 배열 하나 지정
    answer = []
    
    for f in files:
        # 기준이 되는 숫자 파트 이전까지의 문자열을 저장
        p = re.findall(r"\\d+", f)[0]
        
        # 위에서 저장한 p를 가져와서 비교 가능하도록 소문자로 변겨 
        head = f[:f.index(p)].lower()
        number = int(p)
        my_files[f] = (head,number)
        # {"aa01.png" : ("aa",1), "aaa31.jpg": ("a",3),,,}
    # --> Dict에서 정렬!!!
    file_list = my_files.items()
    # 형태 [("aa01.png",("aa",1)),,,,]

    file_list = sorted(file_list, key= lambda x: (x[1][0],x[1][1],x[0]))

    answer = [ file_list[idx[0]] for idx in file_list ]
    return answer
    # key를 개별 파일명으로

3. 자료형 Dict

---

기본 구조

• dict = {key : value}

특징

• 이전에 동일한 key가 있었다면 value를 갱신하게 된다.
• 키 값이 이미 존재한다면 이후에는 키 값의 value를 갱신
• 키 값이 없었다면 k-value 쌍을 새로 생성
• 따라서, 키 값이 유니크하지 않으면 이전에 기록된 값이 소실 될 수 있으므로 주의

3-1) 연습문제 : 완주하지 못한 선수

Dict을 활용해서 만들어내기

# 시도2) 자료형을 Dict 해보자!!!

# --> dict으로 자료형을 바꾼다고 하면
# dict = {이름 : 몇 명}
# p = ["mislav", "stanko", "mislav", "ana"]
# {"mislav": 1}
# {"mislav": 1, "stanko" : 2}
# {"mislav": 1+1, "stanko" : 2}
# value에는 무조건1 이상 있을 것이다.

# 완주자 명단
# c ={"stanko", "ana", "mislav"}
# ==> {"mislav":2, "stanko":1, "ana":1}
# stanko가 완주했다면 ==> {"mislav":2, "ana":1}
# ana 완주 ==> {"mislav":2}
# misalv 완주 ==> {"mislav":2-1}
# 남은 원소의 키값을 출력해주면 완료된다.

def solution(participant, completion):
    answer = ''

    people_dict = {}

    for p in participant:
        # 기준 : 기존에 등록된 이름 or 처음 등록되는 이름..
        if p in people_dict: # --> key가 있냐? : 추가 등록
            people_dict[p] += 1
        else: # 신규등록
            people_dict[p] = 1
# --> 참가 명단이 Dict으로 정리 : 누가 몇 명 참가했는지

# 2) 완주자 명단으로 돌려가면서, 하나씩 -빼면 된다.

    for c in completion: 
        # 1명이 있어서 완전히 key를 제거할지, 여러 명 중 1명만 감소
        if people_dict[c] == 1:
            del people_dict[c]
        else:
            people_dict[c] -=1
    
    answer = list(people_dict.keys())[0]
    return answer

3-2) 연습문제 2 : 신고 결과 받기

---

참고) 연습문제 2 : 신고 결과 받기

 

실체 기출 문제

• 1번 기출 문제

 

문제 분석

---

• 여러 번 신고는 가능, but 카운팅 1로 중복에 대한 처리
• 정지할 기준 값이 가변적으로 들어온다. ⇒ 정리 처리
• 신고 접수를 다 집계해서 최종적으로 처리하겠다.
• id_list 의 길이가 ≤ 1000 임 ⇒ 리스트로 쓰면 효율성이 떨어질 수 있음
• id_list 의 원소는 이용자의 id를 나타내는 문자열이며 알파벳 소문자로만 이루어짐
• id_list 에는 같은 아이디가 중복해서 들어있지 않다.
• report의 길이가 ≤ 200,000 이다.
  • report의 원소 길이는 3이상 21 이하
  • report의 원소는 “이용자 id 신고한 id” 형태의 문자열이다.
  • ex) “muzi frodo” 의 경우 “muzi” 가 “frodo”를 신고했다
  • id는 알파벳 소문자로만 이루어짐
  • 이용자 id와 신고한 id는 공백(스페이스)하나로 구분되어짐
  • 자기 자신을 신고하는 경우는 없다
• 제한 시간
  • 정확성 테스트는 10초
• 주어진 조건에 따라 한 유저가 같은 유저를 여러번 신고 == 1회로 처리

나의 첫 풀이 코드

---

#혼자서 해보기
def solution(id_list, report, k):
   
    answer = []
    
    report = list(set(report))
    #report는 A가 B라는 사람을 여러번 똑같이 신고할 수 있으므로 set형으로 변환해서 중복을 제거하고
    # 이를 다시 다루기 쉽게 list로 변환했음.
    
    report_dict = {}
    # 1. 리스트를 계속 참조해서 사용해야 하므로 딕셔너리를 사용하기로 결정
    
		# 2. id_list를 한번씩 돌리면서 딕셔너리에 key 값을 생성하기
    for id in id_list:
        report_dict[id] = []
		
		# 3. report의 예시를 보면 공백을 기준으로 신고한 사람과 신고당한 사람이 나뉨 
		# report = ["muzi frodo","apeach frodo",
	  #           "frodo neo","muzi neo","apeach muzi"]
	  # 우선, 신고한 사람과 신고당한 사람을 나눠서 저장하자
	  # 이때, 신고 당한 사람을 report_dict의 key값으로 사용하고
	  # value를 key값을 신고한 사람의 list로 저장 --> 이 아이디어는 혼자서 생각해내지는 못했음
	  
    for i in report:
        report_dict[i.split(" ")[1]].append(i.split(" ")[0])
        
    
    # 여기서 다시 report_dict의 키와 밸류를 가져와서
    # 신고한 사람의 길이가 곧 신고 횟수 일테니, 이를 k 기준과 비교해서 k보다 높거나 같으면
    # 그 사람은 blacklist, 밴 목록에 추가
    for i,v in report_dict.items():
        if k <= len(i):
            blacklist.append = i
   
   #... 이후는 진행 못함
   # 밴 목록에 추가하는 것 까지는 했는데, 이후 어떻게 blacklist 값을 활용해서
   # 메일을 보내야 할지... 정리가 되지 않아 최종 코드 작성을 하지 못하였다.
    return answer

정답 코드

---

def solution(id_list, report, k):
    answer = [0] * len(id_list)
    # 출력 방식을 맞추기 위해 미리 answer의 형태를 만들어 두기

    report_dict = {id:set([]) for id in id_list}
    # 딕셔너리를 리스트 컴프리핸션 사용해서 id를 키값으로 하고 빈 set를 값으로 추가

    for report_pair in report:
        reporter,reported  = report_pair.split(" ")[0],report_pair.split(" ")[1]
        report_dict[reported].add(reporter)
    # 리포트 

    k_reported = [key_id for key_id,v in report_dict.items() if len(v) >=k ]
    # 리스트 컴프리핸션 사용해서 list로 바로 만들기

    for ban_id in k_reported:
        mail_res_ids = report_dict[ban_id]
        for id in mail_res_ids:
            id_index = id_list.index(id)
            answer[id_index] +=1
            
    return answer

• answer의 출력 형태를 위해 미리 지정해두는데, 이를 통해 return 값에서 원하는 answer = [0,0,0,0] 등의 형태를 만들어내기 좋았다.
• 딕셔너리를 리스트 컴프리핸션을 사용해서 set형태로 지정해서 중복을 방지하고 한줄로 바로 선언과 동시에 생성하는 스킬을 사용했는데, 이를 통해 가독성이 좋아지고 한 줄로 코드를 이해하기 좋다.
• 밴을 해야하는 리스트인 k_reported에서 벤 id를 키값으로 해당 유저를 신고했던 유저 리스트를 mail_res_ids에 저장했다. ⇒ 벤 받은 유저를 신고한 모든 유저에게 메일을 보내야 하므로
• 그 이후 mail_res_ids에 저장된 유저 id의 인덱스 값을 통해 미리 저장한 answer와 인덱스가 동일하다는 것을 이용해 최종적으로 id_index에 해당하는 위치에 있는 정답을 올려준다.