TIL 7일차 (바탕화면 정리 - Kotlin)

코드카타

 

바탕화면 정리

 

문제

 

파일을 모두 선택할 수 있는 최소 드래그 범위를 구하는 문제이다.

 

lux는 luy는 드래그 시작점의 X, Y 좌표에 해당,

rdx와 rdy는 드래그 끝점의 X, Y 좌표에 해당한다. 

 

 

입출력 예시

 

테스트 케이스에 포함되어 있지 않지만 맨 마지막 줄에 파일이 없는 경우도 고려해야 한다.

 

 

풀이

class Solution {
    fun solution(wallpaper: Array<String>): List<Int> {
        
        // 드래그 시작, 끝 점 X, Y 좌표 초기화
        var lux = 0 
        var luy = 50 // wallpaper의 최대 길이가 50이기 때문에 50으로 초기화
        var rdx = 0
        var rdy = 0
        
        // lux는 첫번째로 파일을 포함하고 있는 열을 값으로 가진다.
        for(i in wallpaper){
            if(i.contains("#") == false) lux ++
            else break
        }
        
        // luy는 파일이 위치한 인덱스 중 가장 작은 인덱스를 값으로 가진다.
        for(i in wallpaper){
            if(i.contains("#")){
                val file = i.indexOf("#")
                if(luy > file) luy = file
            } 
        }
        
        // rdx는 역순으로 월페이퍼를 순회해 처음으로 파일이 위치한 열을 값으로 가진다.
        for(i in wallpaper.size -1 downTo 0){
            if(wallpaper[i].contains("#")){
                rdx = i+1
                break
            }
            else continue
        }
        
        // luy는 파일이 위치한 인덱스 중 (가장 큰 인덱스 + 1)을 값으로 가진다.
        for(i in wallpaper){
            val file = i.lastIndexOf("#") + 1
            if(rdy < file) rdy = file
        }
        
        return listOf(lux, luy, rdx, rdy) // 드래그 최소 범위 반환
    }
}

나같은 경우는 각 좌표의 규칙성을 찾아 좌표값을 하나하나 구했다. 

 

해당 코드는 네 번의 반복문을 사용하므로 최악의 경우 시간 복잡도가 O(4n)가 된다.

좀 더 효율적인 풀이가 있을 거 같아 다른 풀이도 찾아보았다.

 

 

다른 풀이

class Solution {
    fun solution(wallpaper: Array<String>): List<Int> {
        
        // 최소값과 최대값을 구해야 하므로 초기값을 각각 최대값과 최소값으로 설정
        var minY = wallpaper.size
        var minX = wallpaper[0].length
        var maxY = -1
        var maxX = -1

        // 각 줄을 순회하면서 최소 드래그 범위를 구함
        for ((yIdx, row) in wallpaper.withIndex()) {
        
            // 행에 파일이 있을 때
            if ("#" in row) {
                if (yIdx < minY) minY = yIdx // 최상단 y 좌표
                
                if (yIdx + 1 > maxY) maxY = yIdx + 1 // 최하단 y 좌표
                
                val firstFileIdx = row.indexOf("#")
                if (firstFileIdx < minX) minX = firstFileIdx // 최상단 x 좌표

                val lastFileIdx = row.lastIndexOf("#") + 1
                if (lastFileIdx > maxX) maxX = lastFileIdx // 최하단 x 좌표
            }
        }

        return listOf(minY, minX, maxY, maxX)
    }
}

단일 반복문을 사용하여 모든 파일의 위치를 찾고, 최소 및 최대 좌표를 업데이트한다.

각 줄을 한 번만 순회하기 때문에 O(n)의 시간복잡도를 갖는다.

 

각 줄에서 파일이 포함된 경우에만 좌표를 업데이트 하여

조건 검사를 최소화 해 코드의 가독성이 향상시켰다.

 

 

생각난 거 바로 해버리기

 

문제 제목보고 바탕화면 정리가 땡겨서 바로 해버렸다.

 

원하는 앱을 실행시킬 땐 작업표시줄이나 파일 검색창을 이용하면 되기에

바로가기를 전부 지웠고 바탕화면에 존재하는 파일들은

나름의 기준으로 분류해 전부 폴더에다 집어넣었다.

 

오른쪽은 개인파일들을, 왼쪽은 프로젝트 폴더를 모아놨다.