99클럽 코테 스터디
늦은 시각에 풀게 되었다. 챌린저 문제는 99클럽 1기 때 이미 풀고 TIL까지 작성한 것이 있어 TIL 링크로 대체하였다. (코드 자체는 맨 밑에 있다)
주제가 Greedy인데다 반례찾기나 구현 면에서 빡센 부분이 있어 미들러 문제도 꽤 빡센 편이었다.
그리고 예전의 TIL에 자세한 풀이 접근과 설명을 써 두었는데, 챌린저 문제도 제대로 풀면 꽤 빡세다.
비기너 문제 체육복 : https://school.programmers.co.kr/learn/courses/30/lessons/42862
미들러 문제 조이스틱 : https://school.programmers.co.kr/learn/courses/30/lessons/42860
챌린저 문제 섬 연결하기 : https://school.programmers.co.kr/learn/courses/30/lessons/42861
섬 연결하기 TIL (99클럽 1기) : https://velog.io/@sogur928/TIL3
출처 : 프로그래머스
비기너 문제 : 체육복
풀이 접근
greedy + 구현 문제이다. 그리고 조건 중 하나를 간과하면 반례찾기가 조금 어려운 면이 있다(찾지 못하면 테스트케이스 3개 정도 틀리더라). 그리고 입출력 예시만 보고 lost와 reserve를 정렬 안하고 풀면 이것도 테케에서 갈린다.
사람 수가 30명에 불과한 만큼 그 어떤 무식한 방법으로도 통과 가능하지만, 투 포인터를 이용해서 lost와 reserve의 인덱스를 각각 파라미터로 while문을 이용해 greedy한 풀이로 최적의 시간복잡도 내에서 해결했다.
코드(Python3, 통과, 0.02ms, 10.4MB)
본인의 체육복을 도난당했는데 여벌이 있는 사람(lost와 reserve에 같은 숫자가 있는 경우)을 먼저 체크해서 lost와 reserve에서 빼버리고 시작하는 방법도 있다. 시간복잡도 자체는 O(n)으로 똑같이 풀 수 있다. 하지만 이게 순회 횟수가 더 적은 것 같아 이렇게 풀었다.
def solution(n, lost, reserve):
l = len(lost)
r = len(reserve)
lost.sort()
reserve.sort()
answer = n - l
pl = 0 # lost의 인덱스
pr = 0 # reserver의 인덱스
while pl < l and pr < r: # 파라미터 2개로 투포인터 비스무리하게 greedy 풀이 진행
if -1 <= lost[pl] - reserve[pr] <= 1: # 빌려줄수있는경우
answer += 1
if lost[pl] > reserve[pr] and pr + 1 < r and reserve[pr + 1] == lost[pl]:
# 근데 빌려줄 사람이 본인체육복을 도난당한경우 다른사람 못빌려주므로 뒷사람 못빌려줌
pr += 2
pl += 1
elif lost[pl] < reserve[pr] and pl + 1 < l and reserve[pr] == lost[pl + 1]:
# 마찬가지로 앞사람 못빌려주는경우
pl += 2
pr += 1
else:
pl += 1
pr += 1
elif lost[pl] > reserve[pr]: # 못빌려주는경우
pr += 1
else: # 못빌려주는경우2
pl += 1
return answer미들러 문제 : 조이스틱
풀이 접근
미들러치고 꽤나 빡세다(99클럽 카톡방에도 어렵다는 얘기가 올라왔다).
알파벳 이동은 아마 쉽게 풀 수 있을 것이나, 커서 이동에 관해서는 반례 생각하기나 구현하기 둘 다 빡세다.
코드(Python3, 통과, 0.02ms, 10.4MB)
대부분의 설명은 주석으로 달아두었다. a_seq 선언부터가 '최선의 커서 무브 횟수 찾기'이다.
요지는 'A'가 연속된 덩어리의 위치를 파악하고,
'해당 덩어리의 왼쪽까지 >이동으로 찍고 나서 <이동으로 오른쪽찍기'와
'해당 덩어리의 오른쪽까지 <이동으로 찍고 왼쪽까지 >이동으로 찍기'
둘 중에 현재까지 나온 최선보다 좋은(이동 횟수가 적은) 방법이 있으면 그 횟수로 갱신하는 것이다.
def solution(name):
n = len(name)
answer = 0
# ord('A') = 65, 1씩늘어남, 14번째 알파벳인 N은 앞으로든 뒤로든 13번
# 하드코딩으로 {'A':0, 'B':1, ... 'N':13, 'O':12, ... 'Z':1}을 넣는 게 더 효율적인 대신 코드가 길어짐
moves = {}
for num in range(65, 79):
moves[chr(num)] = num - 65
for num in range(79, 91):
moves[chr(num)] = 91 - num
a = [False] * n # 이름이 'A'인 위치만 True
for i in range(n):
answer += moves[name[i]]
if name[i] == 'A':
a[i] = True
# 커서 무브를 줄일 수 있는지 체크해야함
# 왼쪽으로 바로 역행하는 경우도 있지만, 순행->역행(like 'BBAAAZZZZ')이나 역행->순행(like 'BBBBAAAZ')하는 경우도 있음
a_seq = [] # a_seq의 원소 [i,j]는 인덱스 i부터 j까지 연속된 A라는 뜻
p = 1 # parameter
aa = False # 직전에 a였는지
while p < n:
if aa and not a[p]: # 연속된 'A'가 끝나는 곳
aa = False
a_seq[-1].append(p - 1)
elif not aa and a[p]: # 연속된 'A'가 시작되는 곳
aa = True
a_seq.append([p])
p += 1
if aa: # 마지막까지 'A'여서 아직 끝점 기록안된 경우
a_seq[-1].append(n - 1)
best = n - 1 # 기본적으론 커서 무브 n-1번
for i,j in a_seq:
if 2 * (i - 1) + n - j - 1 < best: # 순행->역행이 더 빠른 경우
best = 2 * (i - 1) + n - j - 1
if 2 * (n - j - 1) + i - 1 < best: # 역행->순행이 더 빠른 경우
best = 2 * (n - j - 1) + i - 1
answer += best
return answer챌린저 문제 : 섬 연결하기
풀이 접근
https://velog.io/@sogur928/TIL3
과거의 TIL로 대체
코드(Python3, 통과, 최대 0.05ms, 10.4MB)
코드 설명도 과거의 TIL에 있다. 주석에 대부분을 써 놓긴 했다.
def solution(n, costs):
answer = 0
rn = [i for i in range(n + 1)] # representative number
costs.sort(key=lambda bridge: bridge[2])
def union(a, b): # a번 섬과 b번 섬을 연결하고 대표자를 더 작은 숫자로 통일, a와 b 모두 대표여야함
rn[max(a,b)] = min(a,b)
return
def find(a): # a번 섬이 속한 그룹의 대표 번호 찾기
if rn[a] == a:
return a
b = find(rn[a])
rn[a] = b # find 함수의 재귀 횟수가 계속 늘어나는 걸 방지하기 위해 중간에 바뀐 번호가 있으면 최신화한다
return b
bridges = 0 # 선택된 다리 개수
cost = 0 # 누적 비용
now = 0 # 현재 다리 번호
while bridges < n - 1:
a, b, c = costs[now]
ra, rb = find(a), find(b) # a섬과 b섬의 대표 번호 찾기
if ra != rb: # 대표가 다르면 = 서로 다른 그룹에 속해있으면
union(ra, rb) # 대표끼리 union해서 대표 통일
bridges += 1 # 다리 선택했음
cost += c # 비용 추가
now += 1 # 다음 다리
answer = cost
return answer