https://programmers.co.kr/learn/courses/30/lessons/42587

큐를 사용하면 쉽게 풀 수 있는 문제이다.

스택과 큐에 대해 익숙하지 않거나 까먹었다면 먼저 이전 포스팅을 참고하여 이해하고 오는 것을 추천한다.

2021.12.04 - [알고리즘/알고리즘 강의] - [알고리즘] 스택(Stack)과 큐(Queue) 데크(Deque)까지 (Python)

문제풀이

눈여겨봐야 할 점은 3가지다.

1. 대기목록에서 꺼낸 문서보다 중요도가 높은 문서가 대기목록에 남아있다면 꺼낸 문서를 다시 대기 목록에 넣는다.
2. 대기 목록에는 최대 100개의 문서가 있다.
3. 중요도는 숫자가 클수록 중요하다.

대기 목록인 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을 적게 주고 우선순위 큐의 결과를 나타낼 수 있도록 유도한 것 같다.

코테에서도 은근히 우선순위 큐를 사용하는 문제가 나오므로 우선순위 큐를 구현하는 힙에 대해서 포스팅하겠다.

https://programmers.co.kr/learn/courses/30/lessons/42586

프로그래머스의 분류에도 나와 있듯이 큐를 사용하면 쉽게 풀 수 있는 문제이다.

스택과 큐에 대해 익숙하지 않거나 까먹었다면 먼저 이전 포스팅을 참고하여 이해하고 오는 것을 추천한다.

https://khsung0.tistory.com/14?category=1038750 

문제 풀이

눈여겨봐야 할 점은 5가지다.

1. 작업의 개수는 100개 이하
2. 작업 진도는 100 미만의 자연수
3. 작업 속도는 100 이하의 자연수
4. progresses의 순서대로 배포한다.
5. 배포는 하루에 한 번만 이루어진다.

문제를 보자마자 떠올린 생각은 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번의 연산을 한다.

엄밀히 말하자면 큐로 푼 게 아니라 리스트의 인덱스 접근을 통해 풀었고 처음에는 상당히 비효율적인 방식을 생각했었다.

항상 문제의 조건을 정확히 파악하여 자신이 생각한 방식의 시간 복잡도를 계산해보고 보다 더 효율적인 방식이 있는지 끊임없이 고민하는 습관이 상당히 중요한 것 같다.

https://www.acmicpc.net/problem/1072

전형적으로 이진 탐색을 사용하는 문제이다.

혹시 이진 탐색을 처음 접하거나 익숙하지 않다면 관련 포스팅을 보고 이해한 뒤 문제를 푸는게 좋을 것 같다.

2021.12.02 - [알고리즘/알고리즘 강의] - (알고리즘) 이진탐색 / 이분탐색 (Binary Search)

문제 풀이

문제에서 전체 게임 횟수 : X, 이긴 게임 횟수 : Y, 승률 : Z이다.

주의해야 할 조건은 3가지다.

1. 승률을 뜻하는 Z는 소수점을 버린다.(반올림이 아니다)
2. Z가 절대 변하지 않으면 -1을 출력한다.
3. X는 최대 1,000,000,000 (10억)까지 가능하다.

Z에 대한 식을 나타내 보면 Z=(Y*100)/X이고 a만큼 수행했을 때 Z+1=((Y+a)*100)/(X+a)가 성립하는 최소 a를 구하는 문제이다. (승률 = 이긴 횟수/전체 횟수)

참고로 Python의 계산 방식 때문인지 처음에 Z=(Y//X)*100로 작성했더니 틀렸었다.

꼭 Z=(Y*100)//X로 작성해야하고 이 부분에 대해서 정확히 아시는 분이 계시다면 피드백 해주시면 감사합니다!!

이때 Z가 99 이상이라면 승률은 절대 변하지 않으므로 -1을 출력하고 98일 때 생각하면 X번만큼 추가할 때 99로 변하기 때문에 최대 X번까지만 반복하면 된다는 것을 알 수 있다.

이때 X는 최대 10억까지 가능하므로 순차적으로 탐색하는 O(n)의 시간 복잡도를 적용한다면 반드시 시간 초과가 날 수밖에 없다.

즉 1부터 X까지 오름차순인 상태에서 탐색 가능한 이분 탐색(이진 탐색)을 적용하면 풀 수 있을 것이다.

다음은 전체 코드다.

x,y=map(int,input().split()) 
z=(100*y)//x 
left=0 
right=x 
res=x 
if z>=99: 
    print(-1)
else: 
    while left<=right: 
        mid=(left+right)//2 
        if (100*(y+mid))//(x+mid)>z: 
            res=mid 
            right=mid-1 
        else: 
            left=mid+1
    print(res)

res는 정답인 최소 게임 수를 의미하는 변수로 최대 X번을 저장해놓고 더 작은 수가 있으면 갱신하는 방식으로 구현하였다.

승률이 99 이상이면 바로 -1을 출력하고 98 이하라면 이진 탐색을 실행한다.

초기 left는 0, right는 X로 설정하고 left와 right가 역전되지 않을 때까지 반복한다.

이때 left와 right 중간값을 기준으로 승률(Z)이 변하면 res를 갱신한 뒤 right는 중간값-1로, 변하지 않으면 left를 중간값+1로 변경함으로써 탐색해야 되는 범위를 절반씩 줄여준다.

즉 탐색 범위가 N이라면 범위를 절반씩 줄이므로 O(logn)의 시간 복잡도를 갖고, 10억의 Input이 들어와도 충분히 연산 가능해진다.

※조건을 잘 보고 Input의 크기에 따라 적절한 알고리즘을 적용하는 것이 중요한 것 같다.※

https://www.acmicpc.net/problem/23740

문제 풀이

눈여겨봐야 할 점은 3가지다.

1. 버스 노선의 개수인 N은 20만 이하이다.
2. 한 점 이상에서 겹쳐지면 연장 가능한 노선이다.
3. 개편된 노선의 요금은 개편할 때 사용된 노선의 최소 요금을 적용한다.

문제와 그림을 보고 바로 떠오른 생각은 노선의 정보를 오름차순으로 정렬한 뒤 개편된 노선과 겹친다면 포함하는 노선, 겹치는 부분이 없다면 새로운 개편된 노선으로 판단하는 방식이다.

이 방식대로 연산하면 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로 통과하는 경우가 많다.

즉 올바르게 작성한 것 같은데 시간 초과가 뜬다면 PyPy로 제출하길 추천한다.

https://www.acmicpc.net/contest/problem/725/1

문제 풀이

눈여겨봐야 할 조건은 3가지다.

1. 보이는 대로 읽어야 할 알파벳과 다르게 읽어야 할 알파벳이 구분되어있다.
2. 최대 100글자의 단어가 주어진다.
3. 영어 소문자로 나타내 출력해야 한다.

다르게 읽어야 할 알파벳은 다음과 같다.

B->v, E->ye, H->n, P->r, C->s, Y->u, X->h

해당 부분은 파이썬의 딕셔너리(Dictionary)를 사용하면 쉽게 치환 가능하다.

최대 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() 함수를 이용하여 대문자를 소문자로 치환한 다음 이어 붙인다.

완성된 문자열을 출력하면 정답이다.

파이썬의 딕셔너리를 사용해야겠다는 생각만 떠올리면 복잡한 인덱싱 과정도 필요 없기에 쉽게 풀 수 있는 문제였다.