본문 바로가기

study/알고리즘

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

< 기능개발 >

 

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

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는

programmers.co.kr

 

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) 사용

 


< 프린터 >

 

코딩테스트 연습 - 프린터

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린

programmers.co.kr

 

중요도가 높은 문서를 먼저 인쇄하는 프린터 개발
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