[프로그래머스][시뮬레이션] 99클럽 코테 스터디 3일차 TIL + 바탕화면 정리

오늘의 학습 키워드

시뮬레이션

 

오늘의 회고

🌱 오늘의 문제

https://school.programmers.co.kr/learn/courses/30/lessons/161990

프로그래머스

 

컴퓨터 바탕화면을 좌표로 가정한다. 전체 파일을 모두 선택하기 위하여 왼쪽 위 지점부터 오른쪽 아래지점까지 드래그할 때, 최단 거리를 만들기 위한 시작점과 끝점을 찾는 문제이다.

 

 

 

🌱 나의 시도

이 문제에 대해 내가 해결한 알고리즘의 시간 복잡도는 이중 반복문을 사용하므로 O(n^2)이다. 그러나 wallpaper의 길이가 최대 50, wallpaper의 내부 길이가 최대 50으로 최악의 경우라고 해도 2500번밖에 돌지 않으므로 효율성 측면에서 문제가 없다.

 

1. 파일이 있는 위치를 확인하면서, -> O(n^2)

1-1. 가장 작은 값을 갖는(x는 왼쪽, y는 위쪽) 좌표를 찾아 시작점으로 지정한다.

1-2. 가장 큰 값을 갖는(x는 오른쪽, y는 아래쪽) 좌표를 찾아 끝점으로 지정한다.

2. 끝점의 좌표에 있는 파일도 포함해야 하므로 (x, y) 좌표에 각각 +1을 해준다.

def solution(wallpaper):
    answer = [len(wallpaper), len(wallpaper[0]), -1, -1]
    
    for x, line in enumerate(wallpaper):
        for y, pos in enumerate(line):
            if pos == '#': 
                if answer[0] > x: answer[0] = x
                if answer[1] > y: answer[1] = y
                if answer[2] < x: answer[2] = x
                if answer[3] < y: answer[3] = y
    
    answer[2] = answer[2] + 1
    answer[3] = answer[3] + 1
    return answer

 

 

🌱 새롭게 알게 된 점

다른 사람들의 풀이를 살펴보았다. 

1. x 좌표 위치, y 좌표 위치를 각각 리스트에 저장한다음 최소값, 최대값을 각각의 위치에 넣어주었다. 코드 가독성 측면에서 더 좋아 보였으나 메모리 효율성 측면에서는 비효율적으로 보였다.

2. 조건절 대신 min, max 함수를 이용해서 바로 대입하는 방식을 이용하니 코드 가독성이 더 좋았다.

def solution(wallpaper):
    answer = [len(wallpaper), len(wallpaper[0]), -1, -1]
    
    for x, line in enumerate(wallpaper):
        for y, pos in enumerate(line):
            if pos == '#': 
                answer[0] = min(x, answer[0])
                answer[1] = min(y, answer[1])
                answer[2] = max(x, answer[2])
                answer[3] = max(y, answer[3])
    
    answer[2] = answer[2] + 1
    answer[3] = answer[3] + 1
    return answer

 

 

 

오늘의 후기

나는 좌표 문제에 약한 것 같다. 좌표 문제를 처음 마주했을 때엔 풀기 싫은 마음도 들었다.

정작 풀어보니 어렵지 않았는데도 말이다. 이건 내가 약한 부분이라는 증거라고 생각한다.

BFS, DFS 정리한 부분을 좀 더 꼼꼼히 공부해서 흥미롭게 느끼도록 만들어야겠다.