코딩테스트를 준비하는 머쓱이는 프로그래머스에서 문제를 풀고 나중에 다시 코드를 보면서 공부하려고 작성한 코드를 컴퓨터 바탕화면에 아무 위치에나 저장해 둡니다. 저장한 코드가 많아지면서 머쓱이는 본인의 컴퓨터 바탕화면이 너무 지저분하다고 생각했습니다. 프로그래머스에서 작성했던 코드는 그 문제에 가서 다시 볼 수 있기 때문에 저장해 둔 파일들을 전부 삭제하기로 했습니다. 컴퓨터 바탕화면은 각 칸이 정사각형인 격자판입니다. 이때 컴퓨터 바탕화면의 상태를 나타낸 문자열 배열 wallpaper가 주어집니다. 파일들은 바탕화면의 격자칸에 위치하고 바탕화면의 격자점들은 바탕화면의 가장 왼쪽 위를 (0, 0)으로 시작해 (세로 좌표, 가로 좌표)로 표현합니다. 빈칸은 ".", 파일이 있는 칸은 "#"의 값을 가집니다. 드래그를 하면 파일들을 선택할 수 있고, 선택된 파일들을 삭제할 수 있습니다. 머쓱이는 최소한의 이동거리를 갖는 한 번의 드래그로 모든 파일을 선택해서 한 번에 지우려고 하며 드래그로 파일들을 선택하는 방법은 다음과 같습니다.
드래그는 바탕화면의 격자점 S(lux, luy)를 마우스 왼쪽 버튼으로 클릭한 상태로 격자점 E(rdx, rdy)로 이동한 뒤 마우스 왼쪽 버튼을 떼는 행동입니다. 이때, "점 S에서 점 E로 드래그한다"고 표현하고 점 S와 점 E를 각각 드래그의 시작점, 끝점이라고 표현합니다. 점 S(lux, luy)에서 점 E(rdx, rdy)로 드래그를 할 때, "드래그 한 거리"는 |rdx - lux| + |rdy - luy|로 정의합니다. 점 S에서 점 E로 드래그를 하면 바탕화면에서 두 격자점을 각각 왼쪽 위, 오른쪽 아래로 하는 직사각형 내부에 있는 모든 파일이 선택됩니다.
예를 들어 wallpaper = [".#...", "..#..", "...#."]인 바탕화면을 그림으로 나타내면 다음과 같습니다. 이러한 바탕화면에서 다음 그림과 같이 S(0, 1)에서 E(3, 4)로 드래그하면 세 개의 파일이 모두 선택되므로 드래그 한 거리 (3 - 0) + (4 - 1) = 6을 최솟값으로 모든 파일을 선택 가능합니다.
(0, 0)에서 (3, 5)로 드래그해도 모든 파일을 선택할 수 있지만 이때 드래그 한 거리는 (3 - 0) + (5 - 0) = 8이고 이전의 방법보다 거리가 늘어납니다. 머쓱이의 컴퓨터 바탕화면의 상태를 나타내는 문자열 배열 wallpaper가 매개변수로 주어질 때 바탕화면의 파일들을 한 번에 삭제하기 위해 최소한의 이동거리를 갖는 드래그의 시작점과 끝점을 담은 정수 배열을 return하는 solution 함수를 작성해 주세요. 드래그의 시작점이 (lux, luy), 끝점이 (rdx, rdy)라면 정수 배열 [lux, luy, rdx, rdy]를 return하면 됩니다.
제한사항 - 1 ≤wallpaper의 길이 ≤ 50 - 1 ≤wallpaper[i]의 길이 ≤ 50
- wallpaper의 모든 원소의 길이는 동일합니다. - wallpaper[i][j]는 바탕화면에서i + 1행j + 1열에 해당하는 칸의 상태를 나타냅니다. - wallpaper[i][j]는 "#" 또는 "."의 값만 가집니다. - 바탕화면에는 적어도 하나의 파일이 있습니다. - 드래그 시작점 (lux,luy)와 끝점 (rdx,rdy)는lux<rdx,luy<rdy를 만족해야 합니다.
문제 풀이
처음에 answer=[file_x[0],file_y[0],file_x[-1],file_y[-1]] 라고 써서 틀림. 만약 파일이 (0,0)의 위치에 있다고 하면 드래그는 (1,1)의 위치까지 해주어야 하기 때문에 드래그 끝점에는 +1을 해줘야함. 즉 answer=[file_x[0],file_y[0],file_x[-1]+1,file_y[-1]+1] 으로 해줘야됨. 파일이 있는 위치를 알아야 함. wallpaper를 for문을 이용해 돌려서 파일이 있는 값의 위치를 리스트로 저장함. 처음에는 (x,y)의 형태로 저장하려고 했는데 x값과 y값을 정렬이 따로 필요해서 나눠서 리스트로 저장하는게 더 편할거라고 생각. x값과 y값의 리스트를 각각 구한 후 정렬함. answer에는 각 리스트의 처음값과 마지막 값만 필요함.
내코드
def solution(wallpaper):
file_x=[]
file_y=[]
for i in range(len(wallpaper)):
for j,n in enumerate(wallpaper[i]):
if n=='#':
file_x.append(i)
file_y.append(j)
file_x.sort()
file_y.sort()
answer=[file_x[0],file_y[0],file_x[-1]+1,file_y[-1]+1]
return answer
def solution(wall):
a, b = [], []
for i in range(len(wall)):
for j in range(len(wall[i])):
if wall[i][j] == "#":
a.append(i)
b.append(j)
return [min(a), min(b), max(a) + 1, max(b) + 1]
정렬을 안하고 min과 max를 이용하여 구할 수 있다. 왠지 속도면에서 더 빠를 거 같다는 생각이 들다가 min과 max 두번씩 연산하니까 정렬 한번만 하는 데 더 빠르려나? 싶어서 궁금해서 피티씨한테 물어봤다.
♠ 속도면에서 뭐가 더 빠를까?
🔍 속도 비교 이유
정렬(sort()) 연산의 유무
첫 번째 코드(wall)는 단순히 min(), max()를 사용하여 좌표의 최솟값과 최댓값을 찾습니다.
두 번째 코드(wallpaper)는 sort()를 사용하여 정렬한 뒤 최솟값과 최댓값을 찾습니다.
**정렬 연산의 시간 복잡도는 O(N log N)**이므로, min(), max()만 사용하는 첫 번째 코드(O(N))가 더 빠릅니다.
enumerate() 사용 여부
첫 번째 코드에서는 wall[i][j]를 직접 조회하여 값을 확인합니다.
두 번째 코드에서는 enumerate()를 사용하여 j 값을 얻지만, 이는 속도에 큰 영향을 미치지는 않습니다.
최댓값과 최솟값을 찾는 방식
첫 번째 코드: min(a), max(a), min(b), max(b)를 사용 (O(N))
두 번째 코드: sort() 후 [0], [-1] 인덱스로 접근 (O(N log N))
정렬을 사용한 두 번째 코드가 상대적으로 비효율적입니다.
⏳ 결론
첫 번째 코드: O(N)
두 번째 코드: O(N log N) (sort() 연산 포함)
➡ 첫 번째 코드가 더 빠름! 🚀
즉, 정렬(sort())을 사용하지 않는 첫 번째 코드가 더 효율적이므로, 속도를 더 빠르게 하려면 첫 번째 방식이 유리합니다.
♠ O(1)과 O(N)의 차이
🔍 O(1) (상수 시간)
입력 크기(N)에 관계없이 일정한 시간 안에 실행됨.
데이터가 10개든, 100만 개든 실행 시간은 거의 동일.
예제:
defget_first_element(arr): return arr[0] # O(1)
리스트에서 첫 번째 원소를 가져오는 것은 항상 같은 시간 안에 실행됨.
arr의 길이가 10이든 1,000,000이든 실행 속도는 거의 변하지 않음.
🔥 O(N) (선형 시간)
입력 크기(N)에 비례해서 실행 시간이 증가함.
N이 10이면 10번, N이 100만이면 100만 번 실행됨.
예제:
deffind_max(arr): max_val = arr[0] for num in arr: # O(N)if num > max_val: max_val = num return max_val
리스트의 모든 원소를 검사해야 해서 N번 반복 실행됨.
arr의 길이가 10이면 10번 반복, 100만이면 100만 번 반복!
⏳ O(1) vs O(N) 비교 예제
✅ 정리하자면:
O(1): 입력 크기와 관계없이 일정한 속도로 실행
O(N): 입력 크기에 따라 실행 시간이 선형적으로 증가
즉, O(1)은 아무리 데이터가 많아도 빠르지만, O(N)은 데이터가 많아질수록 느려진다! 🚀
