99클럽 코테 스터디
1번 상당히 빡셌다. 1번 푸는데 오래 걸렸는데 2번은 백준에서 예전에 푼 문제라서 바로 끝나버렸다.
지금까지 내가 본 건 전부 프로그래머스 문제였다가 백준 문제가 처음 나왔는데 실버4에 이미 푼 문제라 싱겁게 끝났다.
1번 문제 고고학 최고의 발견 : https://school.programmers.co.kr/learn/courses/30/lessons/131702
2번 문제 균형잡힌 세상 : https://www.acmicpc.net/problem/4949
출처 : 프로그래머스, 백준
1번 문제 고고학 최고의 발견
풀이 접근
맨 윗줄의 모든 칸(최대 8칸)을 몇 번씩 돌릴 지(경우의 수 최대 65536) 확정지으면 그 아래 칸들은 전부 확정된다.
맨 윗줄을 돌리는 경우의 수는 최대 4^8 = 65536가지이다. 이를 픽스해 두면, 맨 윗줄의 각 칸들의 최종적인 상태는 그 아랫칸이 유일하게 결정하게 된다.
따라서 맨 윗줄의 각 칸의 화살표가 12시를 향하도록 그 아랫줄의 각 칸들을 결정하게 되고, 그러고 나면 3번째 줄을 유일하게 결정해서 2번째 줄이 다 12시를 향하도록 해야 하고 ... 맨 밑줄까지 반복할 수 있다.
맨 밑 줄은 그 아랫줄이 없으므로, 유일하게 결정되고 나면 맨 밑줄의 모든 칸이 12시를 향하는지 확인하고, 만약 그렇다면 solve에 성공한 것이므로 총 회전 횟수가 최소였는지만 체크해서 갱신하면 된다.
코드 (Python3, 통과, 최대 6067.64ms, 10.4MB)
구현 방식이 중구난방 의식의 흐름대로라 남이 알아보기 굉장히 어려운 코드이다.
rotate_number를 읽는 방향이 실제 표와 반대라거나, rotated의 테두리에 0을 두르는데 위랑 오른쪽에 두른다거나...
그나마 셀프 세션 발표하느라 주석이라도 많이 달았다.
def solution(clockHands):
answer = 0
n = len(clockHands)
least = 192
for rotate_number in range(4**n): # 첫 줄 돌리는 경우의 수 4**n(최대 65536)가지
rotated_cnt = 0 # 회전 횟수
solved = True # 첫줄 이상하게 돌리면 solve 실패할 수도 있음
rotated = [[0]*n] # rotated[i+1][j]는 clockHands[i][j] 칸을 몇 번 회전시켰는지이다. 테두리 바깥을 없는 걸로 처리하기 위해 0 둘러주기
for i in range(n-1):
rotated.append([])
next_rotate_number = 0
for j in range(n):
r = rotate_number % 4 # rotate_number(의 4진수)의 1의 자리가 맨 앞(왼쪽) 칸의 회전 횟수
rotated_cnt += r
rotate_number //= 4
rotated[i+1].append(r)
rotated[i+1].append(0) # 테두리 바깥을 없는 걸로 처리하기 위해 0 둘러주기
for j in range(n):
next_rotate_number += (-clockHands[i][j] - sum(rotated[i+1][j-k] for k in range(-1, 2)) - rotated[i][j])%4 * 4**j
# 위에서부터 아래로 내려오므로 ㅗ 모양 4개 칸이 (i,j) 칸에 영향을 이미 주었고 그 아래 칸이 다음 줄에서 영향을 줄 것
rotate_number = next_rotate_number
rotated.append([])
for j in range(n): # 맨 마지막 줄만 따로 돌려서 그 다음 줄로 맞추는 게 아니고 solve 확인
r = rotate_number % 4
rotated_cnt += r
rotate_number //= 4
rotated[n].append(r)
rotated[n].append(0)
for j in range(n):
if (clockHands[n-1][j] + sum(rotated[n][j-k] for k in range(-1, 2)) + rotated[n-1][j]) % 4:
solved = False # 맨밑줄에서 틀린 칸 있으면 배제
break
if solved and rotated_cnt < least: # 회전 횟수 최소이면 갱신
least = rotated_cnt
answer = least
return answer2번 문제 균형잡힌 세상
풀이 접근
작년 1월 31일에 푼 문제이다. 작년 1월 11일에 백준을 가입했으니 코딩 20일차에 푼 문제이므로... 굉장히 풀이가 구리다. 1번 문제를 풀고 시간이 충분히 남았으면 코드를 수정해서 최적화를 시켜볼 텐데, 그럴 시간이 부족했다.
코드를 읽어보니 그냥 조건 이해 + 구현 문제였다.
코드 (Python3, 통과, 최대 360ms, 31256KB)
while True:
sent=str(input())
if sent=='.':
break
sent=list(sent[:-1])
key=True
brackets=[]
while sent!=[]:
a=sent.pop()
if a in [')',']']:
brackets.append(a)
elif a=='(':
if brackets==[]:
key=False
break
b=brackets.pop()
if b==']':
key=False
break
elif a=='[':
if brackets==[]:
key=False
break
b=brackets.pop()
if b==')':
key=False
break
if brackets!=[]:
key=False
if key:
print('yes')
else:
print('no')