대문자 하나에 대응하는 소문자 문자열이 정해져 있으므로 Python의 딕셔너리를 사용하면 쉽게 해결할 수 있다.
대응하는 문자들을 딕셔너리에 저장하고 압축된 문자열이 들어왔을 때 차례대로 소문자 문자열로 치환하면 쉽게 풀 수 있는 문제다.
바로 전체 코드로 넘어가겠다.
n=int(input())
word={}
res=""
for i in range(n):
temp=list(input().split())
word[temp[1]]=temp[0]
question=input()
for i in question:
res+=word[i]
num=list(map(int,input().split()))
print(res[num[0]-1:num[1]])
2번째 word는 딕셔너리를 선언했고 for문을 돌면서 입력받은 값을 저장하면 된다.
이때 주의해야 할 점은 압축된 문자열을 풀어야 하므로 입력받은 대문자를 딕셔너리의 키, 소문자 문자열 패턴을 딕셔너리의 값으로 저장해야 한다는 것이다.
res에 치환한 문자열을 저장하고 입력받은 인덱스를 기준으로 출력하면 쉽게 풀 수 있다.
인덱스로 범위 출력 시 왼쪽 인덱스는 포함, 오른쪽 인덱스는 미만까지 출력하는 점을 주의해야 한다.
대기목록에서 꺼낸 문서보다 중요도가 높은 문서가 대기목록에 남아있다면 꺼낸 문서를 다시 대기 목록에 넣는다.
대기 목록에는 최대 100개의 문서가 있다.
중요도는 숫자가 클수록 중요하다.
대기 목록인 priorities의 첫 원소를 차례대로 빼면서 나머지 원소 중 최대 중요도를 비교하여 뺀 문서보다 중요도 높은 문서가 있다면 뒤에 추가하는 형식으로 풀면 될 것이다.
이때 최대 100개의 문서밖에 없으므로 O(n)의 시간 복잡도를 가지는 max 함수로 최대 중요도를 비교하면 된다.
동시에 location에 해당하는 문서가 몇 번째에 출력되는지 묻는 문제이므로 원소를 pop 할 때마다 location을 감소시키고 음수가 되면 대기 목록의 마지막에 추가되었다고 생각하면 된다.
간단한 문제이므로 바로 전체 코드로 넘어가겠다.
def solution(priorities, location):
answer = 0
while len(priorities)>0: #대기 목록에 문서가 있는 동안 반복
temp=priorities.pop(0) #첫 번째 문서 꺼내기
if len(priorities)==0: #껴낸 문서가 마지막 일때 종료
answer+=1
else:
if temp>=max(priorities): #꺼낸 문서의 중요도가 제일 높을 때
if location==0: #찾고자 하는 문서일 때 종료
answer+=1
break
else:
location-=1
answer+=1
#꺼낸 문서보다 중요도가 높은 문서가 대기 목록에 존재할 때
else:
priorities.append(temp)
location-=1
if location<0:
location=len(priorities)-1
return answer
3번째 줄은 대기 목록에 문서가 있는 동안 반복하기 위해 while문을 선언하였고 4번째 줄은 pop(0)을 통해 0번째 인덱스의 원소를 제거하며 반환한다.
또한 5번째 줄은 꺼낸 문서가 마지막 문서일 때 (더 이상 대기 목록에 문서가 없을 때) 고려할 조건이 없으므로 answer을 증가시킨 후 바로 종료한다.
8번째 줄의 if문은 max로 대기 목록의 중요도를 비교하여 더 높은 중요도가 없으면 출력하는 문서로 판단하고 location을 감소시킨다.
이때 location이 0이라면 꺼낸 문서가 찾는 문서이므로 answer을 증가시킨 뒤 break를 통해 반복문을 빠져나온다.
17번째 else는 대기 목록에 더 높은 중요도가 있을 때 뒤에 추가하는 구문으로 만약 location이 음수가 되면 대기 목록의 마지막에 추가했다는 의미이므로 현재 priorities 길이의 -1로 변경하면 된다.
결과 화면
이 문제는 Input Size가 상당히 작아서 굳이 시간 복잡도를 계산할 필요까진 없었던 것 같다.
조건만 잘 확인하고 구현한다면 충분히 쉽게 통과할 수 있을 것이다.
이 프린터 문제는 우선순위 큐란 알고리즘이다.
다만 우선순위 큐는 힙(Heap)이란 자료 구조를 사용하고 내부 구조에서 최댓값, 최솟값을 갱신하는데 O(logn)의 효율적인 시간 복잡도를 가진다.
파이썬은 Heapq란 모듈을 통해 쉽게 우선순위 큐를 구현 가능하며 해당 문제에서는 큐를 연습하기 위해 일부러 Input을 적게 주고 우선순위 큐의 결과를 나타낼 수 있도록 유도한 것 같다.
코테에서도 은근히 우선순위 큐를 사용하는 문제가 나오므로 우선순위 큐를 구현하는 힙에 대해서 포스팅하겠다.
문제를 보자마자 떠올린 생각은 day를 하루씩 증가시키면서 progresses 리스트에 speeds 리스트의 원소를 계속 더하고 progresses의 길이가 0이 될 때까지 같은 날에 0번째 인덱스의 원소가 100 이상이면 pop 하면서 카운트하여 answer에 추가하는 방식이었다.
애초에 작업의 개수가 100개 이하고 작업 진도가 1, 작업 속도가 1일 때 최대 99일이므로 Input이 작아 가능성은 있어 보였다.
하지만 Python의 pop함수에서 0번째 인덱스를 제거하는 pop(0)은 O(n)의 시간 복잡도를 가지므로 원소를 제거하는 과정에서 추가적으로 불필요한 연산이 생기기에 상당히 비효율적인 방식이라 다른 방법을 생각해봤다.
그 결과 굳이 매번 원소들을 더하는 게 아니라 day를 증가시키면서 같은 day일 경우를 카운트하여 answer에 추가하고 기존의 리스트에 대한 변경 없이 현재 어떤 인덱스를 가리키는지 알려주는curr_index를 선언한다면 매번 원소를 제거할 때 드는 시간 복잡도도 없어질 것이라 판단하였다.
전체 코드를 통해 설명하면 이해가 더 빠를 것이다.
def solution(progresses, speeds):
answer = []
day=0 #개발 일수
curr_index=0 #현재 작업 Index
#작업 Index를 0번 부터 끝까지 반복
while curr_index<len(progresses):
#현재 작업이 100% 넘을 때까지 day 증가
while progresses[curr_index]+speeds[curr_index]*day<100:
day+=1
#완료된 작업 개수 카운트
cnt=0
#완료된 작업 카운트
while curr_index<len(progresses) and progresses[curr_index]+speeds[curr_index]*day>=100:
cnt+=1
curr_index+=1
answer.append(cnt)
return answer
7번째 줄을 통해 progresses 리스트를 전체 반복하고 10번째 줄을 통해 현재 작업이 100%가 될 때까지 day를 증가시킨다.
day를 찾으면 같은 날일 때 몇 개의 작업을 배포할 수 있는지 세기 위해 14번째 줄에 cnt를 선언하여 0으로 초기화한다.
초기화된 cnt를 기반으로 17번째 줄에서 배포 가능한 작업들을 세며 curr_index를 증가시킨다.
이때 while문에서 curr_index<len(progresses)를 먼저 선언한 이유는 curr_index가 증가할 때 progresses의 리스트 범위를 벗어나 Index Error를 일으킬 수 있기 때문이다.
프로그래밍 언어에서 조건을 판단할 때앞에 있는 조건이 False라면 뒤에 있는 조건을 확인하지 않기 때문에이처럼 Index Error를 방지하는 조건이나 시간 복잡도를 최대한 줄일 수 있는 조건은되도록이면 앞에 쓰는 습관을 들이자.
마지막으로 카운트한 작업 수를 answer에 추가하면 끝이다.
결과 화면
이렇게 구현한 방식은 리스트의 원소를 제거하는 등 불필요한 연산을 줄였기 때문에 day를 증가시키는 연산(최대 99번), progresses 리스트를 탐색하는 연산(최대 100번)을 하면 최대 약 10,000번의 연산을 한다.
엄밀히 말하자면 큐로 푼 게 아니라 리스트의 인덱스 접근을 통해 풀었고 처음에는 상당히 비효율적인 방식을 생각했었다.
항상 문제의 조건을 정확히 파악하여 자신이 생각한 방식의 시간 복잡도를 계산해보고 보다 더 효율적인 방식이 있는지 끊임없이 고민하는 습관이 상당히 중요한 것 같다.
문제와 그림을 보고 바로 떠오른 생각은 노선의 정보를 오름차순으로 정렬한 뒤 개편된 노선과 겹친다면 포함하는 노선, 겹치는 부분이 없다면 새로운 개편된 노선으로 판단하는 방식이다.
이 방식대로 연산하면 Sort를 이용하여 정렬할 때 O(nlogn), 오름차순 된 노선 정보를 처음부터 훑을 때 O(n)으로 총 O(nlogn)의 시간 복잡도가 걸린다고 생각했다.
따라서 소스 코드는 다음과 같다.
n=int(input())
bus=[]
res=[]
for i in range(n):
bus.append(list(map(int,input().split())))
bus.sort(key=lambda x:(x[0],x[1]))
check=True
for i in bus:
if check:
res.append(i)
check=False
else:
if i[0]<=res[len(res)-1][1]:
if i[1]>res[len(res)-1][1]:
res[len(res)-1][1]=i[1]
if res[len(res)-1][2]>i[2]:
res[len(res)-1][2]=i[2]
else:
res.append(i)
print(len(res))
for i in res:
print(i[0],i[1],i[2])
bus는 기존 노선 정보를 저장하고 res는 개편된 노선 정보를 저장할 리스트이다.
6번째 줄에서 lambda를 키로 이용하여 0번째 원소, 1번째 원소를 기준으로 오름차순 정렬한다는 뜻이다.
check 변수를 통해 첫 노선을 개편된 노선으로 잡았고 겹치는 부분이 있을 경우로 나눠 14번째 if문은 현재 노선 정보가 개편된 노선보다 길어서 연장해야 될 때, 16번째 if문은 최소 요금으로 갱신하는 문장이다.
또한 겹치는 부분이 없으면 기존 노선을 개편된 노선으로 추가한다.
한 줄씩 원리를 따라가 보면 쉽게 이해할 수 있을 것이다.
결과 화면
Python으로 제출하면 시간 초과가 뜨길래 PyPy로 제출했더니 통과했다.
PyPy는 한 줄씩 해석하는 인터프리터 방식인 Python의 느린 동작에서 컴파일 방식을 개선하여 나온 언어로 상당히 빠른 수행 속도가 특징이다.
따라서 동일한 문법이기에 애초에 시간 복잡도를 비효율적으로 작성한 경우가 아니라면 Python으론 시간 초과 뜨는 코드가 PyPy로 통과하는 경우가 많다.
최대 100글자이므로 시간 복잡도는 고려할 필요가 없을 정도로 Input Size가 작다.
입력이 대문자로 들어오고 출력은 소문자로 해야 하므로 보이는 대로 읽어야 할 알파벳은 소문자로 치환시켜야 된다.
다음은 전체 코드이다.
word=input()
russ={"B":"v","E":"ye","H":"n","P":"r","C":"s","Y":"u","X":"h"}
res=""
for i in word:
if i in russ:
res+=russ[i]
else:
res+=i.lower()
print(res)
먼저 russ란 딕셔너리에 치환해야 될 알파벳들을 넣어 놓고 Input 문자열을 하나씩 반복한다.
만약 딕셔너리에 있는 문자라면 해당 값을 res에 이어 붙이고 없는 문자라면 lower() 함수를 이용하여 대문자를 소문자로 치환한 다음 이어 붙인다.
완성된 문자열을 출력하면 정답이다.
결과 화면
파이썬의 딕셔너리를 사용해야겠다는 생각만 떠올리면 복잡한 인덱싱 과정도 필요 없기에 쉽게 풀 수 있는 문제였다.
이 중 가장 처음으로 접하는 테스트인 알고리즘 구현 능력은 주어진 문제를 해결하는 과정을 평가하므로 적절한 상황에 적합한 알고리즘을 적용하기 위해 자료구조와 알고리즘 학습이 필수입니다.
따라서 이 책은 취업 준비를 위해 자료구조와 알고리즘을 복습, 독학하는 과정에서 프로그래밍 언어에 대한 자료는 많이 있지만 자료구조와 알고리즘을 같이 묶은 집약된 자료를 찾기 어려웠고 국비지원 강의를 들을 때 비전공자 분들과 협업한 경험을 통해 프로그래밍 자체에 어려움을 겪는다는 것을 알게 되어 도움이 되고자 작성하게 되었습니다.
이 부분에 착안하여 고등학교 수리 과외 경험을 살려 언어만 알고 있다면비전공자도 최대한 쉽게 이해할 수 있도록 작성한 PDF 형태의 전자책입니다.
언어는 가장 기본으로 여겨지는 C와 이해가 쉬운 Python을 기반으로 작성하였으며 목차에서 목록을 클릭하면 해당 본문 페이지로, 본문 페이지의 제목을 클릭하면 다시 목차로 넘어올 수 있도록 만들었기에전자책의 편의성을극대화하였습니다.
공부가 주목적이라 마케팅이 전혀 없었기에 몇 권 팔리진 않았지만 지인을 포함한 구매하신 분들 전부 좋은 자료라는 호평이 이어졌습니다.
![data=[1,2,4,5,6,8,9]](https://blog.kakaocdn.net/dn/Dq4Jk/btrmK0xgMr0/KbsYQmG4kYb8n1a8m9Nsv0/img.jpg)
