[Python] 2024-1 이퍼 준비(2)

# 난이도 <중>

 

1.문자열 압축

https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

# 정답 풀이
#들여쓰기에 주의하세요
def get_shortened_length(target, unit_length):
    length = len(target)
    new_length = length
    prev_substr = "" # 기준 문자열
    count = 1  # 반복 횟수

    # 부분 문자열 인덱스 [left, right)
    left = 0
    right = unit_length

    # 오른쪽 인덱스가 길이 초과하기 전까지
    while right <= length:
        # 새로운 부분 문자열
        curr_substr = target[left:right]

        if prev_substr == curr_substr:  # 반복되는 경우, 횟수 증가
            count += 1
        else:  # 반복되지 않는 경우
            # 압축한 경우
            if count > 1: 
                new_length += len(str(count)) # 숫자 길이 만큼 문자열 증가
                new_length -= (count - 1) * unit_length # 반복 횟수에 따른 문자열 단축
                    
            # 부분 문자열 교체, 횟수 초기화
            prev_substr = curr_substr
            count = 1
		#else-end

        # 부분 문자열 인덱스 증가
        left += unit_length
        right += unit_length
	#while-end

    # 남아있는 압축 문자열 반영하기
    if count > 1:
        new_length += len(str(count))
        new_length -= (count - 1) * unit_length
        
    return new_length


def solution(given_str):
    answer = len(given_str)
    for k in range(1, len(given_str) // 2 + 1):
        # k: 단위 길이        
        answer = min(answer, get_shortened_length(given_str, k))
    return answer

• 일단 문자열이 반복되는 지 검사할 때 1부터 문자열의 길이/2 +1 만큼 검사해야 한다. 반복문으로 검사함.
• 반복문으로 검사할 문자열과 반복 숫자(k)를 넣어서 검사 후 최솟값을 answer에 담는다.
• get_shortened_length() 함수를 따로 만들었다. 먼저 입력받은 문자열의 길이를 unit_length에따로 저장한다.(인덱스가 문자열을 넘어가는지 확인하기 위함) 바뀐 문자열의 길이를 저장할 new_length, 비교할 문자열 prev_substr, 반복 횟수를 저장할 count 선언.
• 문자열 슬라이싱으로 앞과 뒤의 문자열이 반복되는 지, 즉 같은지 검사할 것이다. 오른쪽 인덱스가 문자열 길이를 초과하기 전까지 prev_substr=문자열[left:right], curr_substr=문자열[left+unit_length:right+unit_length]로 저장 후 반복해서 비교한다.
• 부분 문자열을 계속 옮겨가면서 비교하므로 left와 right 인덱스는 unit_length만큼 계속 증가시킨다.
• 만약 반복되는 경우 count를 증가한다. 반복되지 않는 경우 count가 2이상이면(반복이 존재했었음) new_length에 압축한 문자열을 저장한다.
• 이것을 len(문자열)//2 + 1 만큼 반복하면 끝! return값을 answer와 계속 비교하며 최종적으로 최솟값이 남게한다.

---

2. 강의실 배정

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

11000번: 강의실 배정

# 정답 풀이
import sys
import heapq as hq

input = sys.stdin.readline

# 필요한 강의실 수를 구하는 함수
def get_min_classroom(lectures):
    lectures.sort() # 오름차순 정렬
    pq = [-1]   # 처음 인덱스 에러를 피하기 위해 음수 값 삽입. (첫번째 강의 때 갱신될 값)

    for start, end in lectures:
        if pq[0] <= start:  # 가장 빨리 끝나는 강의실을 사용할 수 있는 경우
            hq.heappop(pq)
        hq.heappush(pq, end)    # 끝나는 시간 삽입
    
    return len(pq)  # pq의 길이가 사용 중인 강의실의 수가 된다.


n = int(input())
lectures = [tuple(map(int, input().split())) for _ in range(n)]
# 연산 & 출력
print(get_min_classroom(lectures))

• 입력은 tuple 형태로 입력받기.(요소 값을 바꿀 수 없는 것은 빼고 리스트와 큰 차이가 없다...왜 굳이 큐플로 했지?)
• 일단 강의를 (첫번째 원소, 강의 시작시간)오름차순으로 정렬한다.
• 그 후 강의를 차례로 돌며 힙 구조에 최근에 삽입한 값(pop되는 값)이 강의 시작 시간보다 같거나 작으면 강의실을 사용할 수 있는 것이다. 그렇다면 해당 수를 pop한 후 end값을 삽입한다.
• 즉, 이전 강의의 end시간이 다음 강의의 start 시간보다 작거나 같으면 pop 한 후 다음 강의의 end 시간을 삽입하는 것이다.
• 해당 힙의 길이가 사용 중인 강의실의 수가 된다.

---

3. 3*N 타일

https://school.programmers.co.kr/learn/courses/30/lessons/12902

프로그래머스

# 정답 풀이
MOD = 1000000007

def solution(n):
    # n이 홀수인 경우는 만들 수 없음
    if n % 2 != 0:
        return 0

    dp = [0] * (n + 1) # dp 배열 생성
    dp[0] = 1 # dp[0]=1로 초기화해줘야 안쪽 for문을 돌면서 마지막에 dp[0]*2로 매번 추가되는 케이스가 더해짐.
    dp[2] = 3

    for i in range(4, n + 1, 2):
        dp[i] = dp[i - 2] * 3

        for j in range(i - 4, -1, -2):
            dp[i] += dp[j] * 2
        dp[i] %= MOD
        
    return dp[n]

# 다른 풀이
def solution(n):
    answer = 0
    dp = [3,11]
    if n <= 4:  return dp[n//2-1]
    else:
        for i in range(2,n//2):
            dp.append((dp[i-1]*4-dp[i-2])%1000000007)
    return dp[-1]

• 적혀있는 것처럼 n이 홀수면 만들 수 없다.
• dp(dynamic programming) 문제. 문제를 작게 나누어서 푸는 문제이다. 대표적인게 피보나치 함수!
• n=2이면 answer=3, n=4이면 answer = 11, n=6이면 answer = 41, n=8이면 answer = 153
• 즉, 점화식 f(n) = f(n-2)*4 - f(n-4)이 나온다.
• 정답 풀이에서는 f(n) = f(n-2)*3 + f(n-4) + f(n-6) + ... + f(0) 이다. 다른 풀이가 더 쉬워서 참고함.

---

4. 외판원 순회2

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

10971번: 외판원 순회 2

import sys

input = sys.stdin.readline

INF = 1e8

visited = [] # 방문 검사 배열
matrix = [] # 비용 행렬
ans = INF # 최소 비용 저장 위해 미리 최댓값으로 초기화

def backtracking(n, cnt, cur_city, cost):
    global ans, visited, matrix
    if cost >= ans:
        return
    if cnt == n: # 종료 조건 : n개의 도시를 순회했음
				# 출발 도시(0)로 다시 돌아올 수 있는지 확인
        if matrix[cur_city][0] != 0:
            ans = min(ans, cost + matrix[cur_city][0])
        return
    for i in range(n): # cur_city에서 도시 i로 이동
        if matrix[cur_city][i] and not visited[i]: # 길이 있고, 아직 방문하지 않은 도시
            visited[i] = True
            backtracking(n, cnt + 1, i, cost + matrix[cur_city][i])
            visited[i] = False

def solution(n, cost):
    global ans, visited, matrix

    visited = [False] * n
    matrix = cost

    # 연산
    visited[0] = True
    backtracking(n, 1, 0, 0)

    return ans

# 한 사이클을 만들면, 어느 도시에서 시작하든 값은 같으므로 0번 도시부터 시작하는 경우만 검사하면 된다.
 # 입력
n = int(input())
cost = [list(map(int, input().split())) for _ in range(n)]
answer = solution(n, cost)
print(answer)

 

• 비용은 행렬로 주어진다. 즉, 1번째 줄 2번째 수가 10이면 1번 도시에서 2번 도시로 가는데 10만큼의 비용이 드는 것!
• 먼저 해당 도시를 방문했는지 검사하는 배열 visitied, 비용 행렬 matrix, 최소 비용을 저장할 변수 ans(처음에는 최댓값으로 초기화)를 선언한다. 모두 global로!
• backtracking 함수에서, n개의 도시를 순회한 경우 이거나 cost가 최댓값을 넘으면 종료한다.(검사할 필요가 없으므로)
• backtracking 함수로는 순회할 도시의 수 n, 현재 순회한 도시의 수 cnt, 현재 도 cur_city, 비용 행렬 cost를 넘겨준다.
• 만약 종료 조건에서 현재 도시에서 첫번째 도시, 즉 matrix[cur_city][0]으로 가는 비용 함수가 0이 아니라면(갈 수 있는 경우) ans와 지금까지의 cost(마지막 도시까지의 비용을 합친 비용)를 비교 후 최소 값을 저장한다.
• 종료 조건이 아닌경우(대부분 도시를 다 돌지 않은 경우) 현재 도시에서 i번째 도시까지의 matrix[cur_city][i](길이 있는지)와 visited[i](방문하지 않았는지)를  검사한다. 길이 있고 방문하지 않았다면 visitied는 True로, 바꾼 후 backtracking 호출!
• backtracking(n, cnt+1, i, cost+matrix[cur_city][i])를 통해 현재 도시 검사 후 다음 도시로 이동하게 된다. 즉, cnt==n이 될때까지 함수를 호출하며 cur_city도 i부터 n까지 반복 하게 됨! cost는 계속 증가함.

---

# 회고

 

<중> 문제부터는 못풀겠다...ㅎ 기출 달달 외워 가야지..

제대로 된 DFS문제 같은 것도 안나왔는데 여기서 막혔다ㅜ 어려워요

학교 졸업하기가 왤케 빡센지