코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
문제를 보고오면 일단 느낄 것 이다.
할만할꺼같은데?
그런데 문제를 풀면 느낄것이다
아 이거 처음에 이렇게 했어야했는데...
이거 뭐지? 왜 생각대로 했는데 테스트케이스가 통과가 안되지..
이건 뭐 어떻게 하지? 아 문제 다시봐야겠다.
내가 느꼇던 세가지는 아래와 같다.
1. 아 이거 처음에 이렇게 했어야했는데...
-> 처음에 2차원배열을 만들때, 정수가 아니라 배열을 가지는 2차원 배열을 만들껄. 이유는 한 좌표에 여러명이 있을수있어서.
2. 이거 뭐지? 왜 생각대로 했는데 테스트케이스가 통과가 안되지..
-> 특정 부분만 회전이 잘 안되는경우였다.
3. 이건 뭐 어떻게 하지? 아 문제 다시봐야겠다.
-> 출구와 가장가까운 사람을 포함하는 (0,0)에 가까운 정사각형을 잡는것
=> 위 문제에서 만났던 난관은 저렇게 3가지다.
풀면서 느낀점은 처음에 자료구조를 짜고 문제를 풀고 TC를 검증하는게 굉장히 중요하구나.
즉, 내가 문제에서 요구하는걸 하나하나 전부 반영을 한 자료구조를 만들었냐가 굉장히 중요하다 느꼇다.
내가 문제를 보고 크게 신경쓴것은
1. 2차원 배열에 배열을 가지게 선언
2.사람들의 정보값을 가지고있게 사람배열을 선언했다. ( 나중에 이놈때문에 풀이가 꽤 귀찮아졌다. )
3.정해진 위치에 특정 정사각형 길이만큼 시계방향 회전시키는 공식 ( 올해 상반기에는 시험보기직전에 외워갔었다. )
내가 2023년 상반기 오후1번문제로 이문제를 만났는데 출구와 가장가까운 정사각형을 잡는것에서 문제가 막혀서 풀지못했다. 내가 생각한 공식으로 정사각형을 잡았는데 완전 틀렸다는것.
지금와서 복기해보면, 사람들의 위치정보를가지는 배열, 출구 좌표의 최소, 최대값을 가지는 사각형을잡고 ,
그중에 가장 길이가 큰걸 정사각형의 한변으로 한뒤, 그냥 그걸 돌려버렸다.
이러니까 당연히 안되지.
왜냐하면 (0,0)에 가깝게 정사각형을 잡는 조건을 반영을 안했기 때문에 틀렸다.
3번 조건에대해 다시 알아보면,
이번에 풀어볼땐 그점을 염두해서
똑같이 각 사람(x,y)와 출구(exit_x,exit_y) 의 값을 min,max 로 비교해서 왼쪽위좌표 (x1,y1)값을 알아낸뒤,
그녀석을 x값을 -1 씩 해보고, y도 -1 씩 해봐서 출구값과 그 사람 좌표(x,y)를 벗어나는지 체크해서, 가장 작은 값을 가져오게 자료구조를 만들었다.
하지만 여기서 큰 문제가 발생했는데
예외가 너무 많았다.
예를들어, 동시에 같은 x1,y1 값을 가지는데 변의 크기는 같은데 사람 좌표를 어떤 기준으로 정렬할까가 문제였다.
(변길이,x1,y1,사람좌표x,사람좌표y) 의 형태로 튜플리스트로 저장했는데
sort(key=lambda x:x[0],x[1],x[2],x[3],x[4] 으로 정렬을 했다.
# 캬 미쳣다.. 드디어 sort 람다를 써버려서 풀어버리나 !! 했지만,
1 - (3,2,2,2,4)
2 - (3,2,2,0,4)
를 본다고 치면, 위 람다로 정렬해버리면,
list = [(3,2,2,0,4),(3,2,2,2,4)] 가 된다.
2번 인덱스가 가장 출구와 가깝고, x,y가 0,0에 가깝게 정렬이 된다.
나는 여기서 list(0) 값이 위정렬에서 가장 조건에 맞는값(변이 가장작고,시작x,시작,y값이 작아서.) 이라 생각하고
회전을 했지만, TC에서 빈번히 Fail 이 발생했다.
그도 그럴것이,
정답은 이게 아니라,
이것이기 때문이다. 그렇기 때문에 계속해서 문제가 나는것.
즉 내가 접근한 방식이 틀렸다는거다.
(( 여기서 망한것을 느끼고 새로운 방식을 친구에게 물어봤다. ))
그친구의 방식은 코드트리의 해설과 다른데,
1. 출구와 각 사람간의 좌표값을 비교하여, 가장 작은 정사각형 변을 찾는다.
그다음, 정사각형 변이 2라고 하면, 출구를 포함한 모든 정사각형을 탐색 한다.
가장 작은 정사각형을 탐색해보며 순서를 반드시 빨->파->노->핑 순으로 했다.
for i in range(n):
for j in range(n): -> 이것도 행은 고정이고 열을 바꿔 탐색하는거라 크게 어렵지 않았다.
그래야 탐색하던중 사람이 1명이상이라도 발견된다면 바로 탐색문을 break 하고,
그 꼭지점을 기준으로 회전을 하면, (0,0)에 가깝고, 출구와 가장 가깝고, 변이 작은 사람을 기준으로 탐색할 수 있기 때문이다.
얘는 왜 대기업안감?
그래새 이방법으로 탐색해보니 TC케이스를 모두 통과 할 수있었고, 여기서 코딩머리가 되는애들은 정말 대단하구나 느꼈다.
이제 나머지 1,2 번을 보면
결국 특정 부분을 시계방향으로 돌리는 공식만 외워가면 됐는데,
쉽게 외우는 방법이 있었다.
이 공식이다. 저 (x,y)가 왼쪽위 꼭지점이고, len이 얼마만큼 시계방향으로 돌릴지를 결정한다.
만약 배열 전체를 돌리고싶다면,
이렇게 x와 y 만 빼버리면 시계방향으로 돌릴수 있다.
이 공식을 꼭 외워가자. 은근 나오기 쉬운데 공식도 외우기 은근 쉬운거 같아서 시험전에 외워갔다가
잘 구현하고 혼자서 박수치고 쌩쇼를 하다가 위에 최소탐색<<에서 개털려서 완전 망쳤엇다. (테스트케이스 1번도 못통과 ㅋㅋ)
2차원배열을 만들고 안에 값을 배열로 만들어서 배열을 통째로 돌려버린뒤,
그 해당값들을 사람배열에 업데이트를 해줘야했는데 ( 그래야 출구와의 최소거리를 탐색하니까 )
생각해보면 그냥 출구를 기준으로 정사각형 길이 2부터~N까지(어차피 N은 얼마안되니까) 라서 이렇게 탐색한다음,
그 정사각형안에 사람이 1명이상이면 그 꼭지점을 가져오게하면, 굳이 저장할 필요가 없을꺼같다. (이러니까 오래걸리지)
대신에 이동할때, for문으로 11부터 탐색해야해서 시간복잡도 손해는 있을것같은데, 어차피 update로 똑같이 쓰니까 상관없다.
이렇게 복기가 끝났고, 작성한 코드를 올린다.
|
#상하좌우
dxs=[-1,1,0,0]
dys=[0,0,-1,1]
n,m,k = map(int,input().split())
maps = [ [[] for _ in range(n)] for _ in range(n)]
for q1 in range(n) :
temp = list(map(int,input().split()))
for q2 in range(n) :
maps[q1][q2].append(temp[q2])
next_maps = [ [0]*n for _ in range(n)]
people = []
for tt1 in range(m) :
r,c = map(int,input().split())
r-= 1
c-= 1
people.append((r,c))
if maps[r][c][0] == 0 :
maps[r][c][0] = (tt1+11)
else :
maps[r][c].append(tt1+11)
exit_x,exit_y = map(int,input().split())
exit_x -= 1
exit_y -= 1
maps[exit_x][exit_y][0] = -10
move_count= 0
def in_range(x,y) :
return 0<= x < n and 0<= y < n
def debug() :
global move_count
global exit_x,exit_y
print('maps')
for item in maps:
print(*item)
print('people')
for items in people:
print(*items)
print('탈출구:')
print(move_count)
def update() : #여러명의 참가자가 있을수있는게 중요하다. 이걸 안한거같음..
global exit_x,exit_y
global people
for plz in range(len(people)):
for i in range(n) :
for j in range(n) :
if maps[i][j][0] <= -10: # 출구 업데이트
exit_x,exit_y= i,j
for iitz in maps[i][j]:
if iitz == (plz+11) :
people[plz] = (i,j)
def rotate() :
global maps
min_num = 10
for peoples in range(len(people)):
people_x,people_y = people[peoples]
new_x = abs(exit_x-people_x)
new_y = abs(exit_y-people_y)
if min_num > max(new_x,new_y) :
min_num = max(new_x,new_y)
l=min_num
possible = True
for i in range(l,-1,-1) :
if not possible :
break
for j in range(l,-1,-1) :
if not possible :
break
kkoji_x,kkoji_y = exit_x-i,exit_y-j
if in_range(kkoji_x,kkoji_y) :
if not possible :
break
for square_x in range(l+1) :
if not possible :
break
for square_y in range(l+1):
if in_range(kkoji_x+square_x,kkoji_y+square_y):
if maps[kkoji_x+square_x][kkoji_y+square_y][0] > 10 :
possible = False
break
x_len = l
r_start_y,r_start_x= kkoji_x,kkoji_y
r_last_x,r_last_y=r_start_x+x_len,r_start_x+x_len
temp_maps = [ [[] for _ in range(n)] for _ in range(n)]
x_len += 1
for i in range(x_len) :
for j in range(x_len) :
temp_maps[r_start_y +j][r_start_x + x_len - i -1 ] = maps[r_start_y + i][r_start_x + j]
r_start_x,r_start_y=r_start_y,r_start_x
for i in range(x_len):
for j in range(x_len):
if 1<= temp_maps[i+r_start_x][j+r_start_y][0] < 10:
temp_maps[i+r_start_x][j+r_start_y][0] -= 1
maps[r_start_x + i][r_start_y + j] = temp_maps[i+r_start_x][j+r_start_y]
else :
maps[r_start_x + i][r_start_y + j] = temp_maps[i+r_start_x][j+r_start_y]
return
def move() :
global exit_x,exit_y
global people
die=[]
distance = 0
for peo in range(len(people)): #사람들 위치 빼기
x,y = people[peo]
min_dis = abs(exit_x-x) + abs(exit_y-y)
temp = []
for xs in range(4):
nx,ny = x+dxs[xs],y+dys[xs]
exit_dis = abs(exit_x-nx) + abs(exit_y-ny)
if exit_dis <= min_dis and in_range(nx,ny) and ((maps[nx][ny][0] <= 0) or maps[nx][ny][0] > 10) : #만약 더 짧아진다면,
temp.append(xs)
if not len(temp) == 0 :
xtt = temp[0] #상하 위주로 움직이게 바꾸기
nx,ny = x+dxs[xtt],y+dys[xtt]
people[peo] = (nx,ny)
maps[x][y].pop(0)
if len(maps[x][y]) == 0 :
maps[x][y].append(0)
#이동했는데 exit 있으면 터지기
if maps[nx][ny][0] < 0 :
die.append(peo)
elif maps[nx][ny][0] == 0 : #만약에 그냥 길이면
maps[nx][ny].pop(0) # 0빼버리기
maps[nx][ny].append(peo+11)
else : #그냥 사람있으면 추가
maps[nx][ny].append(peo+11)
distance += 1
die.sort(reverse=True)
for item in die :
if len(people) > 0:
people[item] = (-100,-100)
return distance
def check_peo():
global people
chk = 0
for sx,sy in people:
if sx>=0 and sy >=0 :
continue
else :
chk += 1
if chk == len(people):
return False
return True
for tc in range(k) :
move_count += move()
update()
if not check_peo() : #다 탈출했으면 종료
break
rotate()
update()
print(move_count)
print(exit_x+1,exit_y+1)
|
위 코드에서 개선사항
1번 특정부분을 회전하고 반영하는걸 함수화
2번 people 배열 사용하지 않고, update()도 사용하지 않게 수정하기.
3번 불필요한 조건들 지우기
위 사항들을 고려해서
맨처음부터 다시 풀어보자. (9월 17일 전까지 무조껀 한번더 풀어서 블로그에 글올리기, 안올리면 삼성탈락 ㅇㅇ)
ㅋㅋ 안올려서 삼탈했냐?
'코딩 테스트' 카테고리의 다른 글
| [코드트리] 서로 다른 숫자 = set() 의 사용처 공부 (0) | 2023.09.21 |
|---|---|
| [2022 삼성 코딩테스트 하반기 오후 1번] 코드트리 - 코드트리 빵 (0) | 2023.09.20 |
| [2023 삼성 코딩테스트 상반기 오전 1번] 코드트리 - 포탑부수기 파이썬 리뷰 (0) | 2023.09.18 |
| [코드트리 챌린지] K개 중 하나를 N번 선택하기(Simple) / k개 중에 1개를 n번 뽑기 (0) | 2023.09.13 |
| [코드트리 챌린지] 마지막으로 남은숫자 (0) | 2023.09.13 |