[알고리즘/프로그래머스] 스택/큐 - 기능개발, 프린터

< 기능개발 >

코딩테스트 연습 - 기능개발

 

progresses -- 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열
speeds -- 각 작업의 개발 속도가 적힌 정수 배열
각 배포마다 몇개의 기능이 배포되는지 ?

 

접근 방법

- stack을 사용( python에서는 list로 구현 가능 )

- progresses 리스트에 speeds를 더해주면서 첫번째 값이 100 이상이 되면 배포가 가능한 작업을 모두 카운트 후 제거

- progresses 리스트가 비게 되면 반복문 종료

 

def solution(progresses, speeds):
    answer = []
    
    while progresses:
        cnt = 0
        progresses = list(map(lambda x: progresses[x] + speeds[x], [i for i in range(len(progresses))]))
        while progresses[:1] >= [100]:
            cnt+=1
            del progresses[0]
            del speeds[0]
        if cnt != 0:
            answer.append(cnt)
    return answer

 

수정할 부분

- 내 코드 시간 복잡도 O(n**2)

- 다른사람 풀이에서는 zip을 사용한 후 한번에 -((p-100)//s)를 사용해서 구한다. (시간 복잡도 O(n))

 

ceil((100 - progresses[x]) / speeds[x]))
#이렇게 쓰거나 ceil 함수를 쓰지 않기 위해서 -(p-100) 사용

 

---

< 프린터 >

코딩테스트 연습 - 프린터

 

중요도가 높은 문서를 먼저 인쇄하는 프린터 개발
1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.

 

접근 방법

- queue 사용( python list로 구현 )

- max 값 이상이면 인쇄(제거), 아니면 다시 대기목록 마지막 추가(append)

- location은 location = (location+len(priorities)-1)%len(priorities) 식으로 업데이트

- location이 0이 되면 return

 

def solution(priorities, location):
    answer = 0
    while priorities:
        if priorities[0] >= max(priorities):
            answer+=1
            if location == 0:
                return answer
        else:
            priorities.append(priorities[0])
        del priorities[0]
        location = (location+len(priorities)-1)%len(priorities)

 

다른 사람의 풀이

- key와 element로 풀어서 key와 location 비교
- any 함수를 사용하여 큰 값이 존재하는지 확인

def solution(priorities, location):
    queue =  [(i,p) for i,p in enumerate(priorities)]
    answer = 0
    while True:
        cur = queue.pop(0)
        if any(cur[1] < q[1] for q in queue):
            queue.append(cur)
        else:
            answer += 1
            if cur[0] == location:
                return answer