[코딩테스트 입문] 양꼬치

문제 설명:

  머쓱이네 양꼬치 가게는 10인분을 먹으면 음료수 하나를 서비스로 줍니다. 양꼬치는 1인분에 12,000원, 음료수는 2,000원입니다. 정수 n과 k가 매개변수로 주어졌을 때, 양꼬치 n인분과 음료수 k개를 먹었다면 총얼마를 지불해야 하는지 return 하도록 solution 함수를 완성해보세요.

 

 

 

 

내 풀이:

import Foundation

func solution(_ n:Int, _ k:Int) -> Int {
    // 양꼬치 가격
    let sheep = n * 12000
    // 마신 음료수 가격
    let drink = k * 2000
    // [총가격, 할인가격]
    var price = [sheep + drink, (n/10) * 2000]
    return price[0] - price[1]
}

 

 

 

회고:

  간단하게 2가지 정도의 요소를 사용해야 하는 경우, 여러개의 변수를 만드는 것보단 배열에 값들을 정리해서 넣는 것을 좋아하는 것 같다.

그래서 배열의 시간 복잡도를 알아보았다.

  배열의 값에 접근하는 경우, 접근하고 싶은 index를 안다면 시간 복잡도는 O(1)이다.

반대로, 검색을 하는 경우엔 배열의 검색 방식은 순차검색(0번째 index부터 n번째까지 검색)이므로 시간 복잡도는 O(n)이 된다.

 

  그렇다면 배열의 추가 삭제를 생각해보자면, 단순히 배열의 맨 뒤에 요소를 추가하고 삭제하는 것은 "어디에 추가하지?"의 '어디에'를 찾을 필요가 없기에 시간복잡도가 O(1)일 것이다.

  하지만 "a가 있는 곳에 추가하고 싶은데 a가 몇번째 index의 값인질 모르겠어~" 같은 경우엔 배열의 검색이 필요하므로 시간 복잡도는 O(n)이 된다.

  즉, 배열은 '어디에'를 아느냐 모르느냐에 따라 시간복잡도가 달라진다..!

 

 

   요약하자면,

  1. 어디에 넣을지 안다면, '접근' - O(1)

  2. 어디에 넣을지 모른다면, '검색' - O(n) 

  3. 배열의 추가 삭제는 '접근'이냐 '검색'이냐에 따라 시간복잡도가 결정된다.