[프로그래머스] 조이스틱 (lv.2 그리디)

🟠 문제

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

프로그래머스

 

🟠 나의 풀이

문제를 보자마자, 아스키코드로 변환해서 접근해야겠다고 판단했다. 조이스틱을 위로 올리든 아래를 올리든 위치를 변경하든 어차피 숫자로 카운트 되는 거니까! 그리고, 두가지를 나눠서 생각하기로 했다. 

1. 첫번째로 먼저, 방향키를 몇번 움직여야하는지 판단해주려고 한다. A가 아닌 아이들의 위치를 알아내서 👈 이쪽 방향으로 갈지, 👉이쪽 방향으로 갈지 둘중에 어떤 방향으로 움직이는게 최소인지 판단하면 될 것 같다.

만약 JAZ 라면, J에서 A를 거쳐서 Z로 가지 않고, J에서 바로 Z로 움직이는게 횟수가 작다. 그래서 나는 두가지 방향 모두 살펴보고 더 적은 값을 찾아서 count에 더해주려고 했다.

2. 입력받은 문자들을 전부 아스키코드로 바꿔서, 마찬가지로 A방향으로 바꾸는것과 Z방향쪽으로 바꾸는것을 비교했다. 이 모든 과정은 아스키코드로 변경해서 비교했다. 아스키코드로 A는 65, Z는 90의 값을 가지기 때문에 덧셈뺄셈을 활용해서 몇번 카운트되는지 판단할 수 있다.

ABCY 같은경우
B는 A에서 하나 커지는 방향으로, 
C는 A에서 두개 커지는 방향으로 가는 것이 더 카운트가 적고
Y 같은 경우는 A에서 Y로 차례대로 가는 것보다는, A -> Z -> Y 로 가는것이 훨씬 카운트가 적다. 

 

❌ 첫번재 시도 - 실패 밭이다 밭

엄청나게 많이 틀렸다. 중간에 문법적인 오류도 있는것 같다. 그래도, 앞에부분은 맞은 걸로 보니, 내가 풀이한 방향이 완전 틀리진 않은 것 같다. 이제 조건들을 다시 살펴보고 다시 코드를 작성해보자.

func solution(_ name:String) -> Int {
    let nameArr = name.map{ String($0) }
    var count = 0

    // 어느방향으로 순회할건지
    // A의 인덱스 전부 알아보자
    var charIndex = [Int]()
    for i in 0..<nameArr.count {
        if nameArr[i] != "A" {
            charIndex.append(i+1)
        }
    }
    charIndex.sort(by: <)
    // -> 방향 순회 (마지막꺼 - 첫번쨰꺼), <- 방향 순회 (본인 + (namearr길이 - 두번쨰))
    count += min(charIndex[charIndex.count-1] - charIndex[0], charIndex[0] + (nameArr.count - charIndex[1]))

    // A로 바꾸는데 얼만큼 움직여야하는가
    for char in nameArr {
        if char != "A" {
            let now = Int(UnicodeScalar(char)!.value)
            count += min(now-65, 90-now+1)
        }
    }

    return count
}

 

✅ (여러번의 시도) 내가 놓친 것들

1. AAAA 같이 charIndex 배열이 비어있는 경우를 판단해주지 않았다. 이것 때문에 중간중간 문법적인 오류가 낫다. charindex가 없는데 어떻게 min값을 판단행!! 하고 ,,, 중간에 아래 if 문을 하나 넣어주었다.

if charIndex.isEmpty {
    return 0
}

2. name의 길이가 1인경우를 판단해주지 않았다.
맞다, 내 코드에서는 어느방향으로 순회할지 정해주는 과정에서 아래와 같은 공식을 사용한다.

 // -> 방향 순회 (마지막꺼 - 첫번쨰꺼), <- 방향 순회 (본인 + (namearr길이 - 두번쨰))
count += min(charIndex[charIndex.count-1] - charIndex[0], charIndex[0] + (nameArr.count - charIndex[1]))

만약 nameArr가 1이어서 charIndex에 int 1 밖에 들어있지 않다면, charIndex[1]의 값이 존재하지 않는다. 이것도 한번 분기처리를 해주었다.

3.  한방향으로 돌아갈 것 이라고 생각했다. 왔다가 되돌아갈 수도 있지 않나?  그래서 커서의 이동 횟수를 결정하는 코드를 대폭 수정했다. 이렇게 수정해서 돌렸는데,,, 아나... 또 계속 틀려 계속... 아마 예외케이스 때문인거같은데 뭘까 도대체가 ;;; 

왔다가 되돌아가는 경우를 생각해보자.

• 일단 판단하려고 하는 인덱스 부분이 A면 넘어간다.
• next: 다음으로 바꿀 인덱스
• prev; 직전에 조작을 가한 인덱스
• 지금 판단하고 있는 i 를 기준으로 다시 for 를 돌려서 다음으로 바꿔줄 인덱스가 있는지 봐주기 → 다음으로 봐줄 인덱스가 결정됐다면 break, next에 j를 넣어주고, 이전에 조작을 가한애 (다음번에 판단해야하니까 prev 에도 넣어줌)
• 만약 next가 -1 그대로라면 다음으로 조작을 가할 애가 없다는 뜻이니까 
  기존 cursor와 현재 보고있는 i 까지 (i그자체가 거리), 이전에 조작을가한 부분에서 거꾸로 돌아와서 뒤로 돌아올때 이 세가지 case 중 최소값을 구함
• 만약 다음응로 조작을 가할 애가 존재한다면
  기존 cursor 와, 되돌아와서 뒤로 돌아서 next까지 오는 거리를 더한 수 중 최소값을 cursor에 저장해준다. 

 // 커서전환
for i in 0..<nameArr.count {
    if nameArr[i] == "A" {
        continue
    }

    var next = -1

    for j in i+1..<nameArr.count {
        if nameArr[j] != "A" {
            next = j
            prev = j
            break
        }
    }

    if next == -1 {
        cursor = min(cursor, i, prev * 2 + nameArr.count - i)
    } else {
        cursor = min(cursor, i*2+nameArr.count-next)
    }
}

위에 설명이 이해가 잘 안될 수도 있다. 그니까, 그림으로 그려보면

그래 이렇게 되돌아오는거 까지 고려했어. 근데..? 왜 ..? 아노대ㅙ대도됃?

4. 테스트케이스 추가됐다고하는데,, 아진짜 미치겠네 이거 예외케이스를 못찾겟다... 미쳐 돌아가시겠네

미쳐돌아가시기전에 인터넷을 참고했고? 또 예외사항을 찾아버렸다. ㅋㅋㅋ.ㅋ.ㅋ.ㅋ.ㅋ.ㅋ.ㅋ... 지금 내가 고려한 케이스는 모두 아예 오른쪽으로 가거나, 아예 왼쪽으로 가거나(어? 이건 수정된 코드에서 빠진듯한데..?하,, ), 오른쪽으로 갔다가 돌아오거나이다. 한가지 빠진건,, 바로 뒤로 갔다가 돌아오는것... 

이렇게 2번재 경우처럼 아예 처음부터 뒤로 돌아가서 마지맊꺼부터 탐색하고, 그다음 다시 앞으로 돌아오는 경우를 생각해주어야한다. 내가 참고한 코드에서는 이것을 A의 길이로 비교했다. A가 연속되는 길이를 알아보고, 앞으로 돌아가는게 빠른지, 뒤로 돌아가는게 빠른지 판단해주었다. 하... 길고 길었다... 

 

🟠 정답코드

import Foundation

func solution(_ name:String) -> Int {
    let nameArr = name.map{ String($0) }
    var count = 0
    var idx = 0
    var cursor = nameArr.count - 1
    
    for char in nameArr {
        if char != "A" {
            let now = Int(UnicodeScalar(char)!.value)
            count += min(now-65, 91-now)
        }
    }

    if count == 0 {
        return count
    }

    // 커서전환
    for i in 0..<nameArr.count {
        idx = i + 1
        while idx < nameArr.count, nameArr[idx] == "A" {
            idx += 1
        }

        cursor = min(cursor, i * 2 + nameArr.count - idx, (nameArr.count - idx) * 2 + i)
    }

    return name.count == 1 ? count : count + cursor
}

 

 

💬 소감..을 적어보자

아,, 이 문제는 예외케이스가 정말 까다로웠다. 문제도 보면, 계속적으로 예외케이스가 추가되고 있었고 현재 기준으로 1월달에도 케이스가 추가되었다. 그래서 인터넷의 모든 코드가 돌아가지 않았다 ㅋㅋㅋㅋㅋㅋ... 

아직 다양한 방면에서 생각하는 힘이 부족하다고 생각된다. 커서를 옮긴다고 했을 때

1. 오른쪽으로 움직이거나
2. 왼쪽으로 움직이거나

이렇게 두 가지 경우 밖에 생각하지 않았다.  오른쪽으로 갔다가 되돌아가서 뒤로 돌아가는 방법이랑, 아예 뒤쪽먼저 탐색하고 다시 돌아와서 오른쪽으로 탐색하는 경우 까지 모두 고려해줘야했다. 

이 경우에서 index를 이용하거나 길이를 이용하는데 아주그냥 머리가 터질 것 같았다. ... 하... 
코딩테스트 문제를 접하면서 예외케이스를 생각해내는 힘이 가장 중요한것같다고 느끼는 요즘이다. 매번 알고리즘을 풀긴 푸는데, 몇가지의 테스트에서 걸리거나,,,, 몇가지의 테스트에서만 인덱스오류를 내거나 이런다. 이런 경우를 줄이기 위해서는 모든 경우를 생각할 줄 아는 사람이 되어야겟지?  허,, 힘내자 🫠