5주차 모범 답안

[dhdbstjr98]

개요

• 평균 점수 : 5.83점 (미참여자 제외)
• 만점자 : 2명

모범 답안

1. 화살표

문제 보기

정답 : 11명

박진수

chars = input()
chars += chars[0] # dummy
answer = 0
for i in range(1, len(chars) - 1):
    if chars[i] != chars[0] and chars[i] != chars[i + 1]:
        answer += 1
print(answer)

2. 상자 쌓기

문제 보기

정답 : 8명

최성원

dp를 이용한 풀이

#dp[i] : i번째 위치에서 넣을 수 있는 상자의 최대 갯수 
n = int(input())
boxes = list(map(int, input().split()))

dp = [1 for _ in range(n)]
for i in range(1, n):
    for j in range(i):
        if boxes[j] < boxes[i]:
            dp[i] = max(dp[i], dp[j]+1) # +1 : i번째 상자 포함

print(max(dp))

3. 싸지방

문제 보기

정답 : 6명

심규진

Priority Queue를 이용한 풀이

import heapq
import sys
input = sys.stdin.readline
def solve():
    N = int(input())
    values = [0] * N
    for i in range(N):
        values[i] = tuple(map(int,input().split()))
    values.sort()
    
    # heapq로 현재 사용 중인 자리의 끝나는 시간을 담고 있음.
    end_que = []
    # heapq로 현재 사용 가능한 자리의 idx를 담고 있음.
    idx_que = []
    # 각 자리별 사용 인원 수
    cache = [0] * N
    nxt_idx = 0
    
    for start,end in values:
        # 현재 사용 중인 인원이 있다면
        if len(end_que):
            # 그 중 가장 빨리 끝나는 사람을 찾는다.
            fastest_end, fastest_idx = end_que[0]
            # 만약 fastest_end가 start 보다 작다면 (즉 그 자리를 쓸 수 있다면)
            if fastest_end <= start:
                try:
                    # fastest_end가 start보다 커지거나 end_que가 빌때까지
                    # 계속 빼내서 idx_que에 넣음
                    while fastest_end <= start:
                        f_end, f_idx = heapq.heappop(end_que)
                        heapq.heappush(idx_que, f_idx)
                        fastest_end, fastest_idx = end_que[0]
                except:
                    pass  
            try:
                # idx_que에 value가 있다면 가장 빠른 자리를 찾는다.
                idx = heapq.heappop(idx_que)
                cache[idx] += 1
                heapq.heappush(end_que, (end, idx))
                continue
            except:
                pass
        # 사용중인 인원이 없거나, 빈자리가 없고 가장 빨리 끝나는 사람이 내 시작시간보다 느리면
        # 새로운 자리를 추가한다.
        cache[nxt_idx] += 1
        heapq.heappush(end_que, (end, nxt_idx))
        nxt_idx += 1
            
    print(nxt_idx)
    print(*cache[:nxt_idx])
solve()

손현수

세그먼트 트리를 이용한 풀이

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

#define pii pair<int,int>

int n, st, ed, segTree[1<<21], ptr=1<<20;
vector<pii> timetable;
vector<int> computers, endTimes;
map<int,priority_queue<int>> timeComputer;

void update(int num, int val){
    segTree[num+=ptr] = val;
    while(num>>=1)
        segTree[num] = min(segTree[num*2], segTree[num*2+1]);
}

int getMin(int st, int ed){
    st+=ptr, ed+=ptr;
    int res = 1000001;
    while(st<=ed){
        if(st%2==1) res = min(res, segTree[st]), ++st;
        if(ed%2==0) res = min(res, segTree[ed]), --ed;
        st>>=1, ed>>=1;
    }
    return res;
}

int main()
{
    scanf("%d",&n);
    for(int cnt=0; cnt<n; ++cnt){
        scanf("%d%d",&st,&ed);
        timetable.push_back(make_pair(st,ed));
    }
    
    sort(timetable.begin(), timetable.end());
    fill(segTree, segTree+ptr*2, 1000001);
    
    for(auto iter = timetable.begin(); iter != timetable.end(); ++iter){
        int minPos = getMin(0, iter->first);
        if(!timeComputer.count(iter->second))
            timeComputer.insert(make_pair(iter->second, priority_queue<int>()));
        
        
        if(minPos == 1000001){
            timeComputer[iter->second].push(-computers.size());
            if(timeComputer[iter->second].top() == -computers.size())
                update(iter->second, computers.size());
            
            computers.push_back(1);
            endTimes.push_back(iter->second);
        }
        else{
            ++computers[minPos];
            timeComputer[endTimes[minPos]].pop();
            
            if(!timeComputer[endTimes[minPos]].empty())
                update(endTimes[minPos], -timeComputer[endTimes[minPos]].top());
            else
                update(endTimes[minPos], 1000001);
            
            timeComputer[endTimes[minPos]=iter->second].push(-minPos);
            if(timeComputer[iter->second].top() == -minPos)
                update(iter->second, minPos);
        }
    }
    
    printf("%d\n", computers.size());
    for(auto iter = computers.begin(); iter != computers.end(); ++iter)
        printf("%d ", *iter);
        
    return 0;
}

4. 명단 관리

문제 보기

정답 : 3명

심규진

Linked List를 이용한 풀이

import sys
input = sys.stdin.readline
class Node:
    def __init__(self,idx):
        self.idx = idx
        self.bef = None
        self.nxt = None
        
def solution():
    n,f,k = map(int, input().split())
    
    # linked list 초기화
    values = [Node(i) for i in range(n)] 
    for i in range(n):
        try:
            values[i].nxt = values[i + 1]
        except:
            pass
        try:
            values[i+1].bef = values[i]
        except:
            pass
        
    deleted = [] # stk
    cur = values[f]
    
    for i in range(k):
        comm = list(input().split())
        
        if comm[0] == "U":
            for _ in range(int(comm[1])):
                cur = cur.bef
        elif comm[0] == "D":
            for _ in range(int(comm[1])):
                cur = cur.nxt
        elif comm[0] == "C":
            deleted.append(cur.idx)
            cur.idx = -1
            try:
                cur.bef.nxt = cur.nxt
            except:
                pass
            try:
                cur.nxt.bef = cur.bef
                cur = cur.nxt
            except:
                # 마지막이라서 nxt가 없다면
                cur = cur.bef
            
        else:
            restore = deleted.pop()
            target = values[restore]
            target.idx = restore
            nxt = target.nxt
            try:
                while nxt.idx == -1:
                    nxt = target.nxt
                
                if nxt.bef != None:
                    nxt.bef.nxt = target
                target.bef = nxt.bef
                nxt.bef = target
                target.nxt = nxt
                
                
            except:
                bef = target.bef
                while bef.idx == -1:
                    bef = target.bef
                
                if bef.nxt != None:
                    bef.nxt.bef = target
                target.nxt = bef.nxt
                bef.nxt = target
                target.bef = bef
                pass
    deleted.sort()
    result = ""
    for i in deleted:
        result += str(i) + "\n"
    print(result)
            
solution()

손현수

펜윅트리를 이용한 풀이

#include <cstdio>
#include <algorithm>
using namespace std;

#define pii pair<int,int>

int n, f, k, num, delName[1000001], delPtr, fwTree[1000010];
char command;

void update(int num, int val){
    while(num<=n)
        fwTree[num] += val, num += (num & -num);
}

int getSum(int ed){
    int res = 0;
    while(ed)
        res += fwTree[ed], ed -= (ed & -ed);
    return res;
}

int bs(int val){
    int l=1, r=n, m;
    while(l<=r){
        m=(l+r)/2;
        if(getSum(m)<=val) l=m+1;
        else r=m-1;
    }
    return l;
}

int main()
{
    scanf("%d%d%d",&n,&f,&k); ++f; getchar();
    for(int cnt=1; cnt<=n; ++cnt)
        update(cnt, 1);
    
    for(int cnt=0; cnt<k; ++cnt){
        scanf("%c",&command);
        switch(command){
        case 'U':
            scanf("%d",&num); getchar();
            f = bs(getSum(f)-num-1);
        break;
        
        case 'D':
            scanf("%d",&num); getchar();
            f = bs(getSum(f)+num-1);
        break;
        
        case 'C':
            getchar();
            delName[delPtr] = f;
            
            if(f==bs(n-delPtr-1)) f = bs(getSum(f)-2);
            else f = bs(getSum(f));
            
            update(delName[delPtr++], -1);
        break;
        
        case 'Z':
            getchar();
            update(delName[--delPtr],1);
        break;
        }
    }
    
    sort(delName, delName+delPtr);
    for(int cnt=0; cnt<delPtr; ++cnt)
        printf("%d\n",delName[cnt]-1);
        
    return 0;
}

5. 자동 완성

문제 보기

정답 : 4명

심규진

Trie를 이용한 풀이

import sys
input = sys.stdin.readline
def solution():
    # 알파벳 하나 하나를 가지는 dictonary 중첩으로 푼다.
    # 만약 dict[char]의 len이 1이라면 자동완성이 되는걸로 쳐서 count를 하지 않는다.
    
    n = int(input())
    words = [0] * n
    
    # root에 tmp를 추가해 시작 알파벳이 다 같은 경우여도 count가 1은 나오게 해줘서
    # 첫글자는 자동완성이 안되는 것처럼 했다.
    root = {}
    root[""] = 0
    
    
    for i in range(n):
        # 단어를 입력받고
        words[i] = input().rstrip()
        cur = root
        # 각 단어의 글자마다 dict 안을 들어간다.
        for char in words[i]:
            try:
                cur =  cur[char]
            except:
                cur[char] = {}
                cur = cur[char]
        # 해당 단어에서 끝나는 경우와 그 이상으로 이어지는 경우 거르기 위해 tmp 추가
        cur[""] = 0
    
    result = ""
    # 각 단어로 쭉 파고 들어가면서 count 한다.
    for i in range(n):
        count = 0
        cur = root
        for char in words[i]:
            if len(cur) != 1:
                count += 1
            cur =  cur[char]
        
        result += str(count) + "\n"
    
    print(result)

solution()

정산

• 심규진 x3
• 손현수 x2
• 박진수
• 최성원

모범 답안 작성 후 해설 작성시 모범 답안 채택 갯수 시상에 우대합니다(동점자 발생시). 모범 답안 선정되신 분들은 다른 학우분들이 코드를 보고 공부하실 수 있도록 해설 남겨주시면 감사드리겠습니다.

코드에 주석으로 달아주신 분들은 해설을 작성해주신것으로 간주하겠습니다. 물론 추가 해설을 작성해주시면 너무 감사드립니다.

해설은 본 이슈에 계속 달아주세요!

모범 답안 및 해설에 대한 질문이 있으신 분들도 여기에 같이 남겨주시면 좋을 것 같습니다. 슬랙 #dcomding 채널을 이용해주셔도 좋습니다.