[프로그래머스 lv2]방문 길이

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

프로그래머스

문제설명

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

 

U: 위쪽으로 한 칸 가기

 

D: 아래쪽으로 한 칸 가기

 

R: 오른쪽으로 한 칸 가기

 

L: 왼쪽으로 한 칸 가기

 

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.

 

제한사항

dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.

dirs의 길이는 500 이하의 자연수입니다.

 

입출력 예

dirs      answer

"ULURRDLLU"     7

"LULLLLLLU"       7

 

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

 

입출력 예 #2

문제의 예시와 같습니다.

 

문제 해결 방법

1. 우선 음수 좌표의 끝(-5,-5)를 (0,0)으로 생각하고 구현했다. 

2. set() 함수를 통해 중복을 제거함

3. U,D,L,R은 조건문을 통해서 처리되게 하였고, 제한하는 영역을 벗어나면 돌아올 수 있게 해줌

4. 지나간 거리는 예를들어 하나의 거리를 왼쪽에서 오른쪽으로 지나든, 오른쪽에서 왼쪽으로 지나든 방향 상관이 없기 때문에 해당 부분을 잘 체크해주었음 

코드 구현

개선한 코드 

def solution(dirs):
    answer = 0
    
    c = [[0]*11 for _ in range(11)]
    # 나는 (5, 5)에 있다. 거기서부터 시작한다. 
    arr=[]
    now = [5, 5]
    
    result = set()
    
    for dir in dirs:

        n1, n2 = now[0], now[1]
        if dir == "U":
            now[1]+=1
            if now[1]==11:
                now[1]=10
                
        elif dir == "D":
            now[1]-=1
            if now[1]==-1:
                now[1]=0
                
        elif dir == "L":
            now[0]-=1
            if now[0]==-1:
                now[0]=0
                
        elif dir == "R":
            now[0]+=1
            if now[0]==11:
                now[0]=10
        xtox, ytoy = now[0], now[1]

        if n1==xtox and n2==ytoy:
            pass
        else:
            result.add((n1, n2, xtox, ytoy))
            result.add((xtox, ytoy, n1, n2))
        
    answer=len(result)/2
    
    return answer

 

 

기존의 코드 

def solution(dirs):
    answer = 0
    
    c = [[0]*11 for _ in range(11)]
    # 나는 (5, 5)에 있다. 거기서부터 시작한다. 
    
    print(c)
    
    arr=[]
    
    now = [5, 5]
    arr.append([5,5])
    
    for dir in dirs:
        if dir == "U":
            now[1]+=1
            if now[1]==11:
                now[1]=10
                
        elif dir == "D":
            now[1]-=1
            if now[1]==-1:
                now[1]=0
                
        elif dir == "L":
            now[0]-=1
            if now[0]==-1:
                now[0]=0
                
        elif dir == "R":
            now[0]+=1
            if now[0]==11:
                now[0]=10
                
        print(now)    
        one=now[0]
        two=now[1]
        c[one][two]=1
        arr.append([one, two])
        
    print(arr)
    #중복제거를 먼저하고
    #이전에 갖고있던 원소랑 
    
    cnt=0
    for i in c:
        cnt += i.count(1)
        
    print("cnt:", cnt)
    
    return answer

 

 

시간/공간 복잡도

O(N)

최적화 및 개선

처음에는 좌표만큼의 이차원 배열을 0으로 채워 구현하고 그 좌표를 지나면 좌표에 대한 자리를 1로 바꿔주었다. 그런데 문제 예시 1번과 2번의 케이스에 대해 답이 다르게 나왔다. 이 케이스를 공통적으로 해결하기 위해서는 반드시 어디에서 출발했는지도 포함이 되어야 답이 나오는 문제였다. 

따라서 어떤 좌표에 도착했는지만 메기던 기존 코드에서 어디에서 출발했는지도 추가해서 4요소를 set을 통해서 추가하였다. 

어려웠던 점

아직 내공이 부족하구나~ 혼자 힘으로 해결하는 것도 좋지만, 안되겠다 싶으면 빠르게 인정하고 배움의 자세로 바로 공부하고 다음에 또 도전하는 것이 나에게 더 좋은 방법인것 같다~ 고집 이제 안녕~