99클럽 TIL (240810)

> [Middler] 큰 수 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/42883?language=python3#

 

 

🔥다시보기🔥

걸린 시간 : 1시간 15분

 

문제 풀이 과정

오늘도 그리디. 역시나 쉽지 않았다. 처음 생각한 방향은 '조합' 이었다. number 배열에서 n-k개를 뽑는 것과 동일하다고 생각했기 때문이다. 다른 과정이 생각나지 않아 itertools 라이브러리에서 combinations 메소드를 사용해서 풀었었다.

 

[첫번째 풀이과정 : 조합] 틀림

from itertools import combinations

def solution(number, k):
    answer = max(list([ ''.join(i) for i in combinations(number, len(number) - k)]))
    
    return answer

 

당연하게도 number의 길이가 최대 1,000,000이었기 때문에 시간초과 판정을 받았다.

다른 방법은 안타깝게도 생각나지 않아 다른 사람들의 풀이 과정에서 참고해 힌트를 얻었다.

 

[두번째 풀이 과정 : 스택] 정답

우선 이 과정에서 내가 아이데이션 하지 못한 부분에 대해 기록한다.

1. stack을 활용하는 것
   • 💡 최댓값을 알기 위해, 정렬하는 것이 아니라면 number의 순서를 지키며 최댓값을 출력할 수 있어야 한다. 이 때, stack은 LIFO한 자료구조로 number의 순서를 지킬 수 있다!
2. number를 for loop를 통해 순회하면서 stack의 top과 비교하며 num보다 작을때까지 stack 을 pop한다는 것
   • 💡 나는 왜 stack을 pop하는 과정을 한번만 하는 것에 대해서만 생각했을까? 조건에 탈출하기 전까지는 stack을 pop한다는 아이디어를 가지고 가자!

즉, 스택을 이용한 문제 풀이 로직은 아래와 같다.

 

문제 풀이

1. python

1. stack을 생성한다.
2. number를 for loop로 순회하면서 아래의 경우에는 stack을 pop하고 k를 -1한다.
   1. stack이 있고, k가 0보다 크고(=제거대상이 아직 존재), stack의 top이 현재 number 요소보다 작은 경우
3. number 반복문을 탈출한 뒤, k가 남아있다면 stack을 0부터 k이전까지 잘라 stack을 새로 만든다.
   1. (이유) for loop 반복문에서 만일 stack의 top이 num보다 크다면 stack에 num이 계속해서 append된다. 쌓인  stack에서 남은 제거대상 개수만큼 잘라주어야 하기 때문이다.
4. stack을 문자열로 join하여 반환한다.

def solution(number, k):
    stack = []
    
    for num in number :
        while stack and k > 0 and stack[-1] < num :
            stack.pop()
            k-=1
        stack.append(num)
    
    if k > 0 :
        stack = stack[:-k]
    
    return ''.join(stack)

 

2. javascript

코드는 동일하다. 다만 배열을 원하는 index만큼 자르는 과정에서 배운 내용을 기록한다.

 

slice vs splice

 

1. slice

: start 부터 end 전까지 새로운 배열 객체를 만들어 반환한다. 즉, 원본 배열 수정 X

Array.prototype.slice(start, end)

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

arr1 = arr.slice(3, 5);
arr2 = arr.slice(4, -4);
arr3 = arr.slice(-4);
console.log(arr1); // [4, 5]
console.log(arr2); // [5, 6]
console.log(arr3); // [7, 8, 9, 10]

 

 

2. splice 

: 기존의 배열 요소를 삭제하거나, 변경하거나 새로운 요소들을 추가할 수 있다. 즉, 원본 배열 수정 O

Array.prototype.splice(start, deleteCount, item1 배열)

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];

arr1 = arr.splice(10, 2, "a", "b", "c");
console.log(arr); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 'a', 'b', 'c']
console.log(arr1); //[11, 12]

 

시간복잡도 O(N)

스택 구조를 사용하였기 때문에 O(N) 시간복잡도를 가진다.

 

오늘의 회고 및 느낀점

내가 약한 부분은 문자열 같다. 아직 문제 풀이 과정을 생각하는 것이 많이 어렵다. 그래도 이렇게 생각해보고 다른 사람들의 문제 풀이 과정도 분석해보면서 구현 능력을 높일 수 있기를 바란다.

 

 

---

 

> [Beginner] 체육복

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

 

 

🔥다시보기🔥

 

문제 풀이 과정

[첫 문제 해결 과정 : 배열] 성공

처음 아이디어는 'n개의 student 배열을 만들어서 학생들의 체육복 개수를 저장한다' 이었다. 아직 리스트에 익숙한 나의 짧은 시야... 뭔가 더 pythonic하게 풀 생각은 못했다. 우선 생각의 흐름은 아래와 같다.

 

1. 체육복을 두고 온 학생들은  -1 한다. 여분을 챙겨온 학생들은 +1한다.

2. 그리고 student 배열을 돌면서 현재 student가 체육복이 없는데, 앞 혹은 뒤 학생이 여분이 있다면 현재 student에 나눠준다.

3. 체육복이 있는 학생의 수를 리턴한다.

def solution(n, lost, reserve):
    answer = 0
    
    # 체육복 개수 배열을 만든다.
    # 앞 혹은 뒤 순서의 학생이 체육백 개수가 1개이상이면 빌릴 수 있다.
    
    student = [1] * (n+1)
    for i in range(1, len(student)) :
        if i in lost :
            student[i] -= 1
        if i in reserve :
            student[i] += 1
    
    for i in range(1, len(student)) :
            if i>0 and student[i-1] > 1 and student[i] == 0:
                student[i-1] -= 1
                student[i] += 1
            if i < len(student)-1 and student[i+1] > 1 and student[i] == 0:
                student[i+1] -= 1
                student[i] += 1
            
    answer = len(list(filter(lambda x : x > 0, student[1:])))
            
    return answer

 

위의 풀이는 시간복잡도 O(N)을 가진다. 다행히도 학생의 수가 30명 이하이기 때문에 통과할 수 있었다. 그러나 위의 풀이보다 더 명확하고 효율적인 로직을 찾아 기록하고자 한다. 바로 'Set' 을 활용하는 방법이다. 

 

[다른 풀이 방법 : Set]

Set은 집합 자료형으로 중복을 허용하지 않는다. 집합 자료형의 연산에 대해 알아보자

s1 = set([1, 2, 3, 4, 5, 6])
s2 = set([4, 5, 6, 7, 8, 9])

 

교집합 : s1 & s2 or s1.intersection(s2) // {4, 5, 6}

합집합 : s1 | s2 or s1.union(s2) // {1, 2, 3, 4, 5, 6, 7, 8, 9}

차집합 : s1 - s2 or s1.difference(s2) // {1, 2, 3}

 

함수

값 1개 추가하기 (add) : s1.add(7) // {1, 2, 3, 4, 5, 6, 7}

값 여러 개 추가하기 (update) : s1.update([7, 8, 9]) // {1, 2, 3, 4, 5, 6, 7, 8, 9}

값 제거하기 (remove) : s1.remove(4) // {1, 2, 3, 5, 6}

 

 

set을 활용하면 아래처럼 더욱 간결해진 코드를 확인할 수 있다.

 

문제 풀이

1. python

def solution(n, lost, reserve):
    reserve_set = set(reserve) - set(lost) #체육복을 빌려줄 수 있는 학생들
    lost_set = set(lost) - set(reserve) #체육복을 빌려야 하는 학생들
    
    for r in reserve_set :
        if r-1 in lost_set :
            lost_set.remove(r-1) # 체육복을 빌렸으므로 제거
        elif r+1 in lost_set :
            lost_set.remove(r+1) # 체육복을 빌렸으므로 제거
    
    return n - len(lost_set)

 

2. javascript

function difference(setA, setB) {
    let difference = new Set(setA);
    
    setB.forEach(i=>{
        difference.delete(i)
    })
    return difference
}

function solution(n, lost, reserve) {
    // programmers 자바스크립트 node 16.17.0버전 호환
    // difference 메소드는 node 22.0.0 버전부터 호환..
    lost.sort()
    reserve.sort()
    
    let lost_set = difference(new Set(lost), new Set(reserve)) // 정말 빌려줘야 하는 학생들
    let reserve_set = difference(new Set(reserve), new Set(lost)) // 정말 빌려줄 수 있는 학생들
    
    
    reserve_set.forEach(r=>{
        if (lost_set.has(r-1)) {
            lost_set.delete(r-1)
        } else if (lost_set.has(r+1)) {
            lost_set.delete(r+1)
        }
    })
    
    return n - lost_set.size
}

 

💡 Javascript에서 Set() 사용 시 주의할점!

Javascript에서는 Set() 자료형을 이용할 때 유용한 함수와 메서드가 있다. (MDN) 차집합, 여집합, 합집합을 계산할 수 있는 메서드들이다.

const odds = new Set([1, 3, 5, 7, 9]);
const squares = new Set([1, 4, 9]);
console.log(odds.intersection(squares)); // Set(2) { 1, 9 }
console.log(odds.difference(squares)); // Set(3) { 3, 5, 7 }

const evens2 = new Set([2, 4, 6, 8]);
const squares2 = new Set([1, 4, 9]);
console.log(evens2.symmetricDifference(squares2)); // Set(5) { 2, 6, 8, 1, 9 }

const evens3 = new Set([2, 4, 6, 8]);
const squares3 = new Set([1, 4, 9]);
console.log(evens3.union(squares3)); // Set(6) { 2, 4, 6, 8, 1, 9 }

 

그러나 위의 메서드들은 node 버전 22.0.0 이상에서 사용할 수 있다. 안타깝게도...programmers의 javascript 컴파일 버전은 node 16.17.0이다. 그래서 만일 set을 합치거나, 빼려면 add(), delete() 함수를 사용해야 한다. 그리하여 사용한 코드는 위와 같다.

 

💡 배열을 정렬해야 한다!

정렬하지 않고 돌렸을 때, 테스트 18, 20번에서 실패했었다. 그래서 찾아본 반례는 5, [5, 3], [4, 2] 이다. 정렬을 하지 않으면, 체육복 여분이 있는 학생들이 줄 수 있는 체육복이 필요한 학생의 순번이 겹친다... 그래서 set에서 r-1, r+1을 제거해줄 때, 올바르게 제거되지 않는다.

 

다만 여기서 궁금한 점은 python 에서 set을 이용할 때는 sort하지 않아도 통과했는데,, 왜 jas에서는..? 라는 의문이 아직 풀리지 않았다.

 

오늘의 회고 및 느낀점

Set 자료구조 및 python과 javascript에서 다르게 사용되는 메서드들에 대해서 익혀두자