문제:

풀이방법:

여러가지 푸는 방법이 있겠지만, 가장 단순하면서 쉬운 방법을 사용하고자 한다. 브루트 포스 방식으로 가능한 모든 경우의 수를 만들고 그 중에서 해당하는 조건을 찾는 방법으로 했다.

 우선 python의 itertools의 permutation을 사용해서 모든 경우의 수를 만든다. 그리고 각 조건에 맞는지 확인을 하는데, 조건의 길이와 다르면 바로 False로 가도록 하고, 길이가 같다면 그 때 조건을 비교하도록 한다.

 이렇게 조건에 맞는 경우를 찾았다면 중복을 방지하기 위해서 set으로 값을 넣도록 한다.

1s
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import itertools
 
def check(case,banned_id):
    for i in range(len(banned_id)):
        if len(banned_id[i]) !=len(case[i]):
            return False
        else:
            for j in range(len(banned_id[i])):
                if banned_id[i][j]=="*":
                    continue
                elif banned_id[i][j] != case[i][j]:
                    return False
    return True
 
def solution(user_id,banned_id):
    answer=[]
    cases=list(itertools.permutations(user_id,len(banned_id)))
    for case in cases:
        if check(case,banned_id):
            case=set(case)
            if case not in answer:
                answer.append(case)
    return len(answer)
 cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/64064

 

코딩테스트 연습 - 불량 사용자

개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 ��

programmers.co.kr

 

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]9506. 약수들의 합  (0) 2020.06.09
[Programmers]2018 Kakao[1차]추석 트래픽  (0) 2020.05.26
[BOJ]2468. 안전 영역  (0) 2020.05.19
[BOJ]2167. 2차원 배열의 합  (0) 2020.05.14
[BOJ]1350. 진짜 공간  (0) 2020.05.12

문제:

풀이방법:

트리 구조를 알고 있는지 물어보는 문제인 것 같다. 따라서 Tree라는 class를 만들고, 이 클래스는 x,y 좌표와 left, right를 만들어서 node 연결을 하도록 한다.

 

우선 부모 노드를 찾고, 자식 노드들을 알기 위해서 정렬을 하는 작업을 먼저 한다. y가 큰 순으로, x가 작은 순으로 정렬하도록 하기 위해 sorted의 key를 사용하였다.

 

이렇게 root를 찾고 남은 node들은 root부터 시작하여서 x 좌표를 비교해서 이 값이 left 혹은 right인지 확인을 한다. 만약 현재 node에서 이미 left나 right 값이 있다면 그 노드로 이동해서 다시 비교를 하고 지정해주는 작업을 계속해서 반복한다. 따라서 얼마나 많은 반복을 해야할지 모르기 때문에 while을 사용하였으며, 연결을 완료하면 break로 나오도록 하였다.

 

node 연결을 마친 뒤에 preorder와 postorder는 정의대로 재귀를 사용해서 배열에 담아서 return 하도록 한다. 다만 이 때 많은 node들이 있으면 python의 재귀 메커니즘상 런타임 에러가 발생한다고 한다.

(python은 재귀가 최대 1000회로 제한되어 있다.)

따라서 이를 해결하기 위해서 sys.setrecursionlimit()를 사용해서 최댓값을 넉넉히 늘려주도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import sys
 
sys.setrecursionlimit(10**6)
 
class Tree:
    def __init__(self,data,left=None,right=None):
        self.data = data
        self.left = left
        self.right = right
        
preorderList=[]
postorderList=[]
        
        
def preorder(node,nodeinfo):
    preorderList.append(nodeinfo.index(node.data)+1)
    if node.left:
        preorder(node.left,nodeinfo)
    if node.right:
        preorder(node.right,nodeinfo)
 
def postorder(node,nodeinfo):
    if node.left:
        postorder(node.left,nodeinfo)
    if node.right:
        postorder(node.right,nodeinfo)
    postorderList.append(nodeinfo.index(node.data)+1)
    
        
    
def solution(nodeinfo):
    
    answer=[]
    sortedNodeinfo=sorted(nodeinfo,key=lambda x : (-x[1],x[0]))
    
    root = None
    for node in sortedNodeinfo:
        if not root:
            root = Tree(node)
        else:
            current=root
            while True:
                if node[0] < current.data[0]:
                    if current.left:
                        current = current.left
                        continue
                    else:
                        current.left = Tree(node)
                        break
                if node[0] > current.data[0]:
                    if current.right:
                        current = current.right
                        continue
                    else:
                        current.right = Tree(node)
                        break
                break
                
    preorder(root,nodeinfo)
    postorder(root,nodeinfo)
    answer.append(preorderList)
    answer.append(postorderList)
    
    return answer
 cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/42892

 

코딩테스트 연습 - 길 찾기 게임 | 프로그래머스

[[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]]

programmers.co.kr

 

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]13458. 시험 감독  (0) 2020.03.05
[BOJ]6588. 골드바흐의 추측  (0) 2020.03.03
[BOJ]13305. 주유소  (0) 2020.02.25
[BOJ]2485. 가로수  (0) 2020.02.20
[BOJ]1182. 부분수열의 합  (0) 2020.02.18

문제:

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를 들어,
0ms 시점에 3ms가 소요되는 A작업 요청
1ms 시점에 9ms가 소요되는 B작업 요청
2ms 시점에 6ms가 소요되는 C작업 요청

과 같이 요청이 들어왔습니다. 한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms  시점에 작업 완료(요청에서 종료까지 : 11ms)
C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(=(3+11+16)/3)가 됩니다.

하지만 A->C->B 순서대로 처리하면

A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms  시점에 작업 완료(요청에서 종료까지 : 7ms)
B: 2ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

이렇게 A->C->B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(=(3+7+17)/3)가 됩니다.


각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마나 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소주점 이하의 수는 버립니다)


풀이 방법:

 위에서 처음 소개한 방법은 FCFS 방법으로 먼저 들어오는 작업을 먼저 수행하는 것으로 긴 작업이 먼저 들어올 경우 뒤에 들어온 작업들이 수행하기까지 많은 시간을 대기하기 때문에 평균시간이 길어지게 된다. 따라서 이를 해결하기 위해서 후자의 방법인 SJF를 사용하는 것이다. 즉 짧은 요청을 먼저 수행하는 것이다. 별도의 정렬이 없어도 작은 값을 반환해줄 수 있는 힙 구조를 사용해서 이 문제를 풀어야 한다.

 last와 now라는 두 변수를 사용해서 하나의 작업이 들어간 시점과 나오는 시점을 구분해준다. 또한 이 두 변수를 이용해 구간을 구성하고 이 구간 사이에 있는 jobs들을 heap에 담도록 한다. heap에 담기전에 now에서 그 작업이 들어온 시점부터까지의 시간을 계산해서 더해준다.
 
 'C와 B의 작업은 A가 수행되고 있는 도중에 들어오게 되었으며, A가 끝나는 시점인 3ms 까지 각각 1ms, 2ms를 대기한다.'

또한 len(wait)와 wait[0]을 곱한 값을 더하기도 한다. 이 말은 다음과 같다.

 'C가 수행되는 동안에 B가 이미 들어와 있어서 같이 대기를 해야 한다. 즉 C의 수행시간인 6ms 만큼 B가 대기하고 있다. 총 12ms 만큼 시간이 더해져야 한다.'

와 같은 말이다. 

count 변수를 만들어서 이 변수가 jobs의 길이와 같이 지는 순간까지 반복하면 각 작업들이 총 수행되는 시간을 알 수 있고 이를 jobs의 길이로 나누어 준 몫을 구하면 평균을 구할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import heapq
def solution(jobs):
    last=-1
    now=0
    answer=0
    wait=[]
    n=len(jobs)
    count=0
    while(count<n):
        for job in jobs:
            if last <job[0]<=now:
                answer+=(now-job[0])
                heapq.heappush(wait,job[1])
        if len(wait)>0:
            answer+=len(wait)*wait[0]
            last=now
            now+=heapq.heappop(wait)
            count+=1
        else:
            now+=1
    return answer//n
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]11050. 이항 계수 1  (0) 2019.05.08
[BOJ]11866. 조세퍼스 문제0  (0) 2019.05.07
[BOJ]8979. 올림픽  (0) 2019.05.05
[BOJ]1076. 저항  (0) 2019.05.04
[BOJ]1977. 완전제곱수  (0) 2019.05.03

+ Recent posts

티스토리툴바