프로그래머스 LV2 디펜스 게임

문제 유형 : heap
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/142085

프로그래머스

1. 문제 풀이
1) n에서 enemy[i]를 빼고 난 값을 그 다음라운드로 넘겨줘서 또 적을 제거하는 방식이다. 

2) 1번을 푸는 과정 중 병사 수가 부족하거나 없으면 종료, 이 과정에서 K 라는 무적권 방어를 사용해서 병사 손실 없이 적을 물리칠 수 있다.

3) 풀이법은 일단 K 즉, 무적권 횟수를 처음부터 써버리고 그 다음부터 라운드를 진행하게 해서 count를 해주는 것이었다. 

4) 이 과정에서 이전에 풀이 했던 방식 중 최대, 최소값을 구할 땐 heapq를 사용했기에 이번에도 heapq를 사용했다. 

5) 제일 적은 수의 적을 먼저 빼줘야 하기 때문에 noCost에 enemy[i]를 넣어주고 최소 값을 반환해주는 heappop 함수로 적은 수 부터 제거해나가면서 라운드를 늘렸다. 

 

2. 실패 코드

사실 아직 이해를 못한 부분인데 이렇게 하면 몇 가지 케이스는 통과이고 몇 가지 케이스는 실패가 된다. 

풀이 자체가 잘못된건 아닌 것 같아서 구글링을 해봤는데 파이썬에서 3.8버전 이후로 나온 Walus 연산자라는게 있다고 한다. ":="를 사용한다. 이것을 참고해서 풀었더니 정답이 됐다

 

3. 정답 코드

실패코드와 어떻게 차이가 있는 진 아직 모르겠다..ㅠ 

 

4. 시간복잡도 및 피드백
여기서 가장 큰 점은 바다코끼리 연산자라고도 불리는 Walrus 연산자이다

1) 바다코끼리 연산자 (Walrus 연산자)
 ":=" 로 사용하며 표현식에 이름을 부여하고 재사용할 수 있도록 하는 것이다.
사용 예시는 아래와 같다

myWord = "hello"
c1 = len(myWord)
if c1 > 2:
    print("hello")
 # 위 내용을 아래 코드로 바꿀 수 있음
if c2:=len(myWord)>2:
    print("hello")

2) 시간복잡도

시간복잡도는 for문을 k번 돌릴 때 생기는 O(K) 와 while문을 돌릴 때 사용하는 O(N)이다 이 두개를 더하면 결론은 O(N)이 될 것이다. 

공간복잡도 또한 K, N , enemy 길이에 따라 달라지기 때문에 O(N)이 될 것이다.