Posts

백준 5430번 바로가기 첫 번째 풀이 t = int(input()) # 테스트 케이스의 개수 for _ in range(t): # 입력 p = input() # 수행할 함수 1~100,000 n = int(input()) # 배열에 들어있는 수의 개수 1~100,000 arr = input()[1:-1].split(',') if n == 0: arr = [] # 처리 for f in p: if f == "R": arr = arr[::-1] elif f == "D": if arr == []: print('error') break else: arr.pop(0) print('['+','.join(arr)+']') 두 번째 풀이 from collections import deque t = int(input()) # 테스트 케이스의 개수 for _ in range(t): # 입력 p = input() # 수행할 함수 1~100,000 n = int(input()) # 배열에 들어있는 수의 개수 1~100,000 arr = deque(input()[1:-1].split(',')) if n == 0: arr = deque() # 처리 for f in p: if f == "R": arr.reverse() elif f == "D": if arr: arr.popleft() else: print('error') break print('['+','.join(arr)+']') 세 번째 풀이 from collections import deque t = int(input()) # 테스트 케이스의 개수 for _ in range(t): # 입력 p = input() # 수행할 함수 1~100,000 n = int(input()) # 배열에 들어있는 수의 개수 1~100,000 arr = deque(input()[1:-1].split(',')) if n == 0: arr = deque() count = 0 # 처리 for f in p: if f == "R": count += 1 elif f == "D": if arr: if count%2 == 0: arr.popleft() else: arr.pop() else: print('error') break else: if count%2 == 1: arr.reverse() print('['+','.join(arr)+']') CODE REVIEW 첫 번째 풀이에서는 시간초과 에러로 걸렸다. list로 구현하다보니 탐색에 시간이 오래 걸린 모양이다. 두 번째 풀이에서는 deque를 활용했는데, 여전히 시간초과 에러가 발생했다. reverse()가 여러번 실행되면서 그런듯… 세 번쨰 풀이에서는 reverse()가 여러 번 호출되는 것을 방지하기 위해 count=0을 도입해서 홀짝성에 따라 pop() popleft()을 선택하고, reverse()는 한 번만 실행해주었다. 처음에는 만만하게 봤던 문제였는데, 생각보다 고려할게 많았다. 이런 기법들은 기억해두었다가 시간 단축이 필요할 때 써먹어야겠다.

백준 7569번 바로가기 나의 풀이 from collections import deque # 입력 m,n,h=map(int,input().split()) tomato = [] for i in range(h): tomato.append([list(map(int,input().split())) for _ in range(n)]) queue = deque([]) dx = [-1,1,0,0,0,0] dy = [0,0,-1,1,0,0] dz = [0,0,0,0,-1,1] # 처리 for i in range(h): for j in range(n): for k in range(m): if tomato[i][j][k] == 1: queue.append([i,j,k]) def ripe(): while queue: x,y,z = queue.popleft() for i in range(6): nx = x + dx[i] ny = y + dy[i] nz = z + dz[i] if 0<=nx<h and 0<=ny<n and 0<=nz<m and tomato[nx][ny][nz] == 0: tomato[nx][ny][nz] = tomato[x][y][z] + 1 queue.append([nx,ny,nz]) ripe() ans = 0 for t1 in tomato: for t2 in t1: for t3 in t2: if t3 == 0: print(-1) exit(0) ans = max(ans ,max(t2)) print(ans-1) CODE REVIEW 7569번 토마토의 3차원 버전. 기본 원리는 동일해서 조금만 수정하면 금세 구현할 수 있다. 이 문제도 마지막에 3차원 array에서 최댓값을 구하는 과정이 까다로웠는데, 3차원은 한번에 최댓값을 구할 수 없다. ans = max(ans,max(t2))와 같이 3차원 배열을 2차원들로 쪼개서 각각의 max값을 비교해서 더 큰 값으로 업데이트 하는 방법으로 구할 수 있다.

백준 7576번 바로가기 나의 풀이 from collections import deque # 입력 m,n=map(int,input().split()) tomato = [list(map(int,input().split())) for _ in range(n)] queue = deque([]) dx = [-1,1,0,0] dy = [0,0,-1,1] # 처리 for i in range(n): for j in range(m): if tomato[i][j] == 1: queue.append([i,j]) def ripe(): while queue: x,y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0<=nx<n and 0<=ny<m and tomato[nx][ny] == 0: tomato[nx][ny] = tomato[x][y] + 1 queue.append([nx,ny]) ripe() for i in range(n): for j in range(m): if tomato[i][j] == 0: print(-1) exit(0) print(max(map(max, tomato))-1) CODE REVIEW 2606번-바이러스문제와 1012번-유기농 배추와 결이 같은 문제. graph 문제를 풀다보니 이제는 다 비슷비슷해 보인다. stack에 익어있는 토마토를 집어놓고 하나씩 꺼내가며 옆의 토마토들을 익히는 과정을 반복한다. 모두 반복하고 마지막 결과물에서 익지 않은 토마토가 있는지 확인하고, 최댓값을 출력한다. 논리상에 문제가 없는데 2%에서 자꾸 틀렸습니다라길래 코드를 살펴봐도 문제를 찾을 수 없었다. 알고보니 출력 부분에서 최대값을 찾는 과정에서 문제가 생긴 것! 2차원 배열의 경우 그냥 max(max(array))로 구하면 안되고, max(map(max,array))로 구해야 한다. 7569번 토마토는 3차원 배열이던데 이것도 도전해보자.

달리기 경주 문제 바로가기 나의 풀이 def solution(players, callings): answer = [] names = {} ranks = {} for i,player in enumerate(players): ranks[i+1] = player names[player] = i+1 for call in callings: idx = names[call] p1 = ranks[idx-1] ranks[idx-1],ranks[idx] = call,p1 names[call],names[p1] = idx-1,idx answer=list(ranks.values()) return answer CODE REVIEW 처음에는 수열로 array[i],array[i-1]=array[i-1],array[i]처럼 구현했는데, 시간초과 문제가 발생하여 실패했다. 탐색 과정에서 소요되는 시간을 줄이기 위해 딕셔너리를 이용하여 구현했다. (순위,이름) (이름,순위) 순서쌍의 딕셔너리 두 개를 생성하고 call마다 각각의 딕셔너리를 업데이트 해주는 방식이다.

약수의 합 문제 바로가기 나의 풀이 def solution(n): answer = 0 for i in range(1,n+1): if n % i == 0: answer += i return answer CODE REVIEW 간단한 수학 문제. 범위만 주의하면 쉽게 해결 가능하다.