2월28일 TIL

프로그래머스 코딩테스트 [ 모음사전 ]

Github 링크

• 이 문제는 알파벳 5개로 만들 수 있는 모든 단어를 찾고, 주어진 단어가 몇번째 순서에 있는지 확인하는 문제이다.
• 우선 머리속으로는 당연히 완전 탐색을 써야된다는걸 알았지만, 정확히 어떤 방식으로 접근을 해야할지 고민을 많이 했다.
• 단어 길이가 최대 5글자이기 때문에, 재귀함수를 써도 시간초과가 뜨지 않을꺼 같아서, 재귀함수로 시도를 해봤다.
• 단어 길이 별로 for loop을 돌려서, 단어 generateWordsHelper 함수를 이용해서 단어를 만들고 저장하는 방식으로 사용했다.
• generateWordHelper는 currentWord, length를 변수로 받는다. 만약 length가 0 이면 currentWord를 dictionary라는 arr에 저장한다.
• length가 0 이 아니면, alphabet array에 있는 알파벳 순서대로 하나씩 추가혹, genereateWordsHelper(currentWord + letter, length -1)로 다시 재귀함수를 호출한다.
• 정리하자면, 단어길이가 1,2,3,4,5 이런식으로 접근을 하고, 단어길이의 맞게 알파벳에 있는 모든 알파벳을 한번씩 더한다.
• 다만 이렇게 더하면, 문제에서 요구하는 순서랑 다르다, 사전적 순서로 정렬을 다시 해줘야한다.
• 정렬한 다음에 arr.firstIndex(of: string) 함수를 사용해서 index를 찾고, 0부터 시작하는 index이기 떄문에 +1 를 해주고 return 한다.

import Foundation

func solution(_ word:String) -> Int {
    var dictionary : [String] = []
    
    let alphabet = ["A", "E", "I", "O", "U"]
    
    func generateWords() {
        for length in 1...5 {
            generateWordsHelper("", length)
        }
    }

    func generateWordsHelper(_ currentWord: String, _ length: Int) {
        if length == 0 {
            dictionary.append(currentWord)
            return
        }
    
        for letter in alphabet {
            let newWord = currentWord + letter
            generateWordsHelper(newWord, length - 1)
        }
    }
    generateWords()
    dictionary = dictionary.sorted(by: <)
    let ans = dictionary.firstIndex(of: word)! + 1
    //test
    return ans
}

프로그래머스 코딩테스트 [ 뒤에 있는 큰 수 찾기 ]

Github 링크

• 이 문제는 단순히 주어진 숫자 배열에서 각 인덱스 기준 뒤에 있는 숫자중 제일 먼저 만나는 자기보다 큰 숫자를 표시하는 문제인다.
• 이 문제의 핵심은 결국 시간초과를 어떻게 해결하냐인것 같다.
• 배열의 최대길이가 1,000,000 이기 때문에, 이것을 중요시 생각해야 하는 문제다.
• 처음에는 단순히 배열로 바로 풀었지만, 결국 시간초과가 떠서, 다른 방법을 생각해서 결국 stack을 사용하기로 했다.
• 일단 정답 배열을 주어진 숫자 배열과 같은 사이즈로 -1로 채우고, 주어진 배열을 하나씩 순회한다.
• while문을 해석하면, stack이 비어있지 않으며, 현재 numbers[i] 가 stack에 맨위에 있는 인덱스의 숫자보다 크다면
  - 결과 배열에 스택에 맨위에 있는 인덱스 위치에 numbers[i]를 넣는다.
• 그리고 현재 인덱스 (i)를 stack에 넣는다.

  예시를 한번 들어보자.

// given Array
var numbers = [2,3,3,5]
//reset result Array
var result: [Int] = Array(repeating: -1, count: numbers.count)
//numbers 0번째 인덱스부터 순회시작.

// # 1  
result 현재 상태 [-1,-1,-1,-1]
// i = 0 , number[i] = 2
stack 현재 상태 []
// stack이 비어 있으니깐 바로 stack에 현재 인덱스 넣기
stack 현재 상태 [0]

// # 2  
result 현재 상태 [-1,-1,-1,-1]
// i = 1 , number[i] = 3
stack 현재 상태 [0]
// stack이 비어 있지 않고, numbers[stack.last] < numbers [i]
result 현재 상태 [3,-1,-1,-1]
stack 현재 상태 [1]

// # 3  
result 현재 상태 [3,-1,-1,-1]
// i = 2 , number[i] = 3
stack 현재 상태 [1]
// stack이 비어 있지 않지만, numbers[stack.last] == numbers [i]
result 현재 상태 [3,-1,-1,-1]
stack 현재 상태 [1,2]

// # 4  
result 현재 상태 [3,-1,-1,-1]
// i = 3 , number[i] = 5
stack 현재 상태 [1]
// stack이 비어 있지 않고, numbers[stack.last] < numbers [i]
result 현재 상태 [3,5,-1,-1]
stack 현재 상태 [1]
// stack이 비어 있지 않고, numbers[stack.last] < numbers [i]
result 현재 상태 [3,5,5,-1]
stack 현재 상태 [0]

끝!

• 아래는 전체 코드다.

import Foundation

func solution(_ numbers:[Int]) -> [Int] {
    var stack: [Int] = []
    var result: [Int] = Array(repeating: -1, count: numbers.count)
    
    for i in 0..<numbers.count {
        while !stack.isEmpty && numbers[i] > numbers[stack.last!] {
            let idx = stack.removeLast()
            result[idx] = numbers[i]
        }
        
        stack.append(i)
    }
    
    return result
}