일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 자바
- exception
- 로버트마틴
- DesignPattern
- Rails
- 스택
- Spring
- Java
- 디자인패턴
- 겨울카카오인턴
- lambda calculus
- Collection
- Eclipse
- Pattern
- 람다 칼큘러스
- 함수형 프로그래밍
- Python
- tcp
- 프로그래머스
- 파이썬
- JavaScript
- javscript
- solid
- JDBC
- 백준
- functional programming
- Collections
- 큐
- Network
- design-pattern
Archives
- Today
- Total
개발자 노트
[백준]17822.원판돌리기 본문
문제설명
구현문제.
rotate는 삼성 기출 중 톱니바퀴라는 문제가 있다. 이를 참고하면 좋을 듯.
총 문제 풀이시간은 2시간 10분으로
접근 방법 정하기 및 절차 작성 => 30분소요
구현 1시간 30분 소요
- 첫 코드 작성 40분소요
- rotate 디버깅 30분 소요(;; 절망적.)
- 인접 부분 잘못 고려하여 20분 소요
접근
문제의 큰 틀 접근 자체는 크게 어렵지 않아 보였을 것이다. 그나마 포인트가 될 것은 다음과 같다.
1)인접하다
원형을 단순히 테이블로 변형하여 인접을 고려하는데 큰 어려움이 없을 것이다. 다음 부분만 제외하고.
i번째 원을 기준으로 1번째의 왼쪽인 M번째 수. M번째의 오른쪽인 1번째 수. 이것이 인접하다는 것만 고려해주면 큰 문제는 없다.
2)원판에 동일한 수가 있다면 삭제하는 알고리즘
이는 SWEA의 미생물 문제, 삼성 기출의 미세먼지 문제를 보면 알 수 있는데, board에서 값이 동일하다고 바로 삭제해버리면 안된다. 삭제된 값이 변경되어 그 값과 동일한 것을 삭제 못할 수 있기 때문
- (a,b)와 값이 같은 (a,b-1) 값 삭제(0으로 놨다고 하자.) (a,b-1)은 (a,b-2)와 값이 동일함에도 값을 수정했기 때문에 값이 다르다 판단하여 삭제하지 않아 오류 발생.
이 둘을 지켜주면 된다.
구현
def rotate(circle,k,d,m):
if d == 0:
return circle[m-k:]+circle[:m-k]
else:
return circle[k:]+circle[:k]
N,M,T = map(int,input().split())
circles = [[0]*M]
totalNumbers = N*M
direction = [[0,1],[0,-1],[1,0],[-1,0]]
for _ in range(N):
circles.append(list(map(int,input().split())))
for z in range(T):
x,d,k = map(int,input().split())
for i in range(1,N+1): #회전
if i%x == 0 :
circles[i] = rotate(circles[i],k,d,M)
#인접탐색
sumNumbers = 0
ajflag = False
delList = set()
for i in range(1,N+1):
for j in range(M):
number = circles[i][j]
flag = False
if number == 0:
continue
#해당 i,j에 대해 인접 탐색
for di,dj in direction:
ni = i+di
nj = j+dj
if nj == -1 :
nj = M-1
elif nj == M:
nj = 0
if ni<=0 or ni>N : #i의 0은 수채우기용, N번째까지 존재, j는 0번에서 M-1까지 존재.
continue
ajNumber = circles[ni][nj] #인접 수
if ajNumber == 0 :
continue
if ajNumber == number: #인접 수가 같다면 삭제해줘야 함. 삭제한다는 것은 0을 의미한다.
flag = True
delList.add((ni,nj))
if flag: #삭제가 발생했다면 i,j 위치 삭제해주고 전체 수 삭제
delList.add((i,j))
ajflag = True
if delList:
for delI,delJ in delList:
circles[delI][delJ] = 0
totalNumbers = totalNumbers - len(delList)
if totalNumbers == 0 :
break
sumNumbers = 0
for i in range(1,N+1):
sumNumbers+=sum(circles[i])
avg = sumNumbers/totalNumbers
if ajflag is False: #삭제가 발생하지 않았다면 평균구해서 가산연산 해줘야 함.
for i in range(1,N+1):
for j in range(M):
if circles[i][j] == 0 :
continue
elif avg>circles[i][j]:
circles[i][j] += 1
elif avg<circles[i][j]:
circles[i][j] -= 1
# 인접탐색
rst = 0
for i in range(1,N+1):
rst += sum(circles[i])
print(rst)
반성
함수로 작업의 모듈화를 시켜야겠다. input, output 작업에서 call by value를 하는데, 여기서 시간이 좀 더 소요되기 때문에 한 함수 내에서 모두 작업했는데 가독성이 안좋아져서 디버깅도 힘들어진다.
그리고 위 코드는 인접값 탐색시 중복작업이 많아 시간이 오래걸린다.
- (a,b)기준 상하좌우 탐색할 필요없이, r,c를 오름차순으로 탐색한다면 오른쪽과 아래만 탐색해도 모든 탐색이 가능하다. 명심!
반응형
'알고리즘 문제 풀이' 카테고리의 다른 글
[프로그래머스-2019겨울카카오인턴]호텔방배정 (0) | 2020.03.31 |
---|---|
[백준]5052 전화번호목록 (0) | 2020.03.31 |
[백준]2178.미로찾기 (0) | 2020.03.26 |
[2020카카오블라인드]자물쇠와 열쇠 (0) | 2020.03.25 |
[백준]2493.탑 (0) | 2020.03.19 |
Comments