2주차 모범 답안

[dhdbstjr98]

개요

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

모범 답안

1. 해밍코드

문제 보기

정답 : 10명

전현준

B = list(map(int, input().split()))
C = [str(sum([B[i] for i in [-1-p-d for p in range(0, 15, 2**(x+1)) for d in range(2**x)][0:7]] + [B[2**x-1]])%2) for x in range(4)]
error = int('0b'+''.join(C[::-1]), base=0)
if error:
    B[error-1] = 1 - B[error-1]
print(int('0b'+''.join([str(B[i-1]) for i in range(1, 16) if i not in [2**x for x in range(4)]][::-1]), base=0))

2. 괄호 회전하기

문제 보기

정답 : 13명

전현준

stack을 이용한 풀이

def isRight(s):
    stack = list()
    for ch in s:
        for open, close in zip('[({', '])}'):
            if ch == open:
                stack.append(open)
                break
            elif ch == close:
                if stack and stack[-1] == open:
                    stack.pop()
                    break
                else:
                    return False
    return False if stack else True

s = input()
print(sum([isRight(s[i:]+s[:i]) for i in range(len(s))]))

3. 방돌이

문제 보기

정답 : 5명

심규진

stack을 이용한 풀이

import sys
from collections import deque
input = sys.stdin.readline
def solution():
    n = int(input())
    can_go = {}
    for i in range(n):
        start, end = input().split()
        try:
            can_go[start].append(end)
        except:
            can_go[start] = [end]
            
    def custom_rank(key):
        '''길이와 사전순을 기준으로 정렬'''
        return (len(key), key)
    
    for idx in can_go:
        can_go[idx] = deque(sorted(can_go[idx],key = custom_rank))

    result = []
    
    # 손선생님의 손길이 탄 코드입니다.
    funcStack = deque(["DCOM"])
    while funcStack:
        
        cur = funcStack[-1]
        try:
            funcStack.append(can_go[cur].popleft())
            if not can_go[cur]:
                del can_go[cur]  
        except:
            result.append(funcStack.pop())
            continue
        
    print(*result[::-1])
solution()

4. 앱등이

문제 보기

정답 : 11명

구희연

two pointer 알고리즘을 이용한 풀이

gems=[]
for i in range(int(input())):
    gems.append(str(input()))
def solution(gems):
    TYPE_NUM=len(set(gems))
    GEM_NUM=len(gems)
    cur_shop={gems[0]:1}
    cand=[]
    l_idx,r_idx=0,0
    DIST,RESULT=0,1
    
    while l_idx<GEM_NUM and r_idx<GEM_NUM:
        if len(cur_shop)<TYPE_NUM:
            r_idx+=1
            if r_idx==GEM_NUM:
                break
            cur_shop[gems[r_idx]]=cur_shop.get(gems[r_idx],0)+1
            
        else:
            cand.append((r_idx-l_idx,[l_idx+1,r_idx+1]))
            cur_shop[gems[l_idx]]-=1
            if cur_shop[gems[l_idx]]==0:
                del cur_shop[gems[l_idx]]
            l_idx+=1
    cand=sorted(cand,key=lambda x:(x[DIST],x[RESULT]))
    def print_it():
        for i in cand[0][RESULT]:
            print(i)
    return print_it()
solution(gems)
#print(solution(["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]))
#투포인터 알고리즘 사용
#두 포인터를 설정하여 4가지 보석이 존재하지 않으면 end를 증가시키고 4가지 보석이 존재하면 start를 증가시킴

송용우

슬라이딩 윈도우 알고리즘을 이용한 풀이

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;

int n;
int item_cnt = 0;
int category_cnt;
vector<string> v;
int s_idx = 0;
int e_idx = 0;
map<string, int> m;
set<string> s;

/*
void get_start_window(){
	int isFind = false;
	int idx = s_idx;
	while(!isFind){
		m[v[idx]] -= 1;
		if(m[v[idx]] == 0){
			item_cnt -= 1;
		}
		if(item_cnt != category_cnt){
			m[v[idx]] += 1;
			item_cnt += 1;
			s_idx = idx;
			isFind = true;
		}
		idx++;
	}
}
*/

void get_end_window(){
	while(e_idx < n){
		//cout << idx << endl;
		m[v[e_idx]] += 1;
		if(m[v[e_idx]] == 1){
			item_cnt += 1;
		}
		if(item_cnt == category_cnt){
			break;
		}
		e_idx++;
	}
	
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int s_ans, e_ans, w_size;

	bool isBuy = false;
	cin >> n;
	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		v.push_back(s);
		if(m.find(s) == m.end()){
			m.insert({s,0});
		}
		
		
	}
	
	category_cnt = m.size();
	//슬라이딩 윈도우의 끝 지점을 찾는다.
	get_end_window();
	s_ans = s_idx;
	e_ans = e_idx;
	w_size = e_ans - s_ans;
	while(e_idx < n){
		//cout << s_idx << " " << e_idx << endl;
		string item = v[s_idx];
		m[item]--;
		s_idx++;
		if(m[item] == 0){
			item_cnt--;
			e_idx++;
			get_end_window();
		}
		
		
		if(item_cnt == category_cnt && w_size > e_idx - s_idx){
					s_ans = s_idx;
					e_ans = e_idx;
					w_size =  e_ans - s_ans;
			}	

		
	}
	
	cout << s_ans + 1 << endl << e_ans + 1;
	
	
	
	
	return 0;
}

5. 방의 개수

문제 보기

정답 : 6명

윤창목

n = int(input(""))
directions = list(map(int, input("").split()))

mov = [(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1)]

new = True
now = (0, 0)
bef = (3, 3)
visited = {now:[-1]}
shapes = 0
additional = False

for d in directions:
    nex = (now[0]+mov[d][0], now[1]+mov[d][1])
    if d%2 == 1:
        try:
            if (d+2)%8 in visited[(now[0]+mov[(d+1)%8][0]) ,(now[1]+mov[(d+1)%8][1]) ]:
                additional = True
        except:
            additional = False
    
    if nex in visited:
        if d not in visited[nex]:
            shapes += 1
            if additional:
                shapes += 1
                additional = False
            visited[nex].append(d)
            visited[now].append((d+4) % 8)
        else:
            additional = False
        new = False
    else:
        visited[nex] = [d]
        visited[now].append((d+4) % 8)
        new = True
        if additional:
            shapes += 1
            additional = False
    bef = now
    now = nex

    # if d == 0:
    #     nex = (now[0], now[1]+1)
    # elif d == 1:
    #     nex = (now[0]+1, now[1]+1)
    #     try:
    #         if 7 in visited[(now[0]), now[1]+1] or 3 in visited[(now[0]+1, now[1])]:
    #             additional = True
    #         else:
    #             additional = False
    #     except:
    #         additional = False
    # elif d == 2:
    #     nex = (now[0]+1, now[1])
    # elif d == 3:
    #     nex = (now[0]+1, now[1]-1)
    #     try:
    #         if 5 in visited[(now[0], now[1]-1)] or 1 in visited[(now[0]+1, now[1])]:
    #             additional = True
    #         else:
    #             additional = False
    #     except:
    #         additional = False
    # elif d == 4:
    #     nex = (now[0], now[1]-1)
    # elif d == 5:
    #     nex = (now[0]-1, now[1]-1)
    #     try:
    #         if 7 in visited[(now[0]-1, now[1])] or 3 in visited[(now[0], now[1]-1)]:
    #             additional = True
    #         else:
    #             additional = False
    #     except:
    #         additional = False
    # elif d == 6:
    #     nex = (now[0]-1, now[1])
    # elif d == 7:
    #     nex = (now[0]-1, now[1]+1)
    #     try:
    #         if 5 in visited[(now[0]-1, now[1])] or 1 in visited[(now[0], now[1]+1)]:
    #             additional = True
    #         else:
    #             additional = False
    #     except:
    #         additional = False
    # if nex in visited:
    #     if nex != bef and d not in visited[nex]:
    #         shapes += 1
    #         if additional:
    #             shapes += 1
    #             additional = False
    #         visited[nex].append(d)
    #     else:
    #         additional = False
    #     new = False
    # else:
    #     visited[nex] = [d]
    #     visited[now].append((d+4) % 8)
    #     new = True
    #     if additional:
    #         shapes += 1
    #         additional = False
    # bef = now
    # now = nex

print(shapes)

정산

• 전현준x2
• 심규진
• 구희연
• 송용우
• 윤창목

1주차 후반부터 실행 시간을 기록하도록 시스템이 개선되어 2주차부터는 모범 답안 선정시에도 실행 시간을 고려하고 있습니다. 모범 답안은 실행 시간, 최적화 정도, 가독성 등을 종합적으로 검토하여 선정하며,
비슷한 경우 모범 답안 선정 횟수가 적은 분을 우선으로 선정합니다.

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

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

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

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

[all-eviate]

#아래 주석부는 애초에 틀린 부분이라 생략합니다.

#입력
n = int(input(""))
directions = list(map(int, input("").split()))

#각 이동 방향의 좌표 이동량을 리스트로 미리 저장해둡니다.
mov = [(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1)]

new = True #새로운 방이 생길 수 있다는 플래그입니다. 새로운 좌표로 이동할 때에 True로 올라갑니다.
now = (0, 0) #현재 좌표를 (0, 0)으로 초기화합니다.
bef = (3, 3) #이전 좌표를 저장하기 위한 변수를 초기화 하는데, 날린 주석부에서만 쓰는 변수라 없어도 됩니다.

visited = {now:[-1]}
'''
위 visited는 방문한 좌표를 진입한 방향과 함께 저장하는 좌표 기록입니다.
만약 (0, 0)좌표로부터 (1, 1)좌표로 1방향으로 도달했다면 visited에 {(1, 1) : [1]}이 저장되는 방식입니다.
다만 시작하는 좌표는 진입각이 없었으니 쓰지 않는 방향인 -1로 저장해 visited를 초기화합니다.
'''

shapes = 0 #생성된 방의 갯수입니다.
additional = False #점이 아닌 곳에서 대각선으로 교차되어 방이 추가로 생성되는지 알려주는 플래그입니다.

for d in directions:

    nex = (now[0]+mov[d][0], now[1]+mov[d][1]) #이동 방향대로 다음 좌표를 저장합니다.

    if d%2 == 1: #만약 이동 방향이 대각선인 경우,

        try:
            #이번 이동으로 이전에 그은 대각선과 교차하는 경우
            if (d+2)%8 in visited[(now[0]+mov[(d+1)%8][0]) ,(now[1]+mov[(d+1)%8][1]) ]: 
                additional = True #플래그를 세워줍니다.

        except: #이번 이동과 겹치는 대각선이 아예 없다면
            additional = False
    
    if nex in visited: #이번 이동으로 도달한 좌표에 왔던 적이 있는 경우,

        if d not in visited[nex]: #그리고 그 사이에 한 번이라도 새 좌표에 들른 적이 있는 경우,

            shapes += 1 #새로운 방이 만들어졌습니다.

            if additional: #또한 대각선이 교차했다면,

                shapes += 1 #하나가 더 만들어졌습니다. (2 7 2 5가 기가 막힌 예시입니다.)
                additional = False #서있던 플래그를 내려줍니다.

            visited[nex].append(d) #처음 도달한 좌표니 좌표 기록에 추가합니다.
            visited[now].append((d+4) % 8) #한 쪽 방향만 저장되지 않도록 반대 방향 좌표 기록도 추가합니다.

        else: #이번 이동으로 도달한 좌표에 왔던 적이 있고, 그 사이에 새 좌표로 들른 적이 없는 경우,

            additional = False #이미 있던 선만 따라간 것이니, 대각선이 교차했대도 새로 생성되는 방은 없습니다.

        new = False #새로운 좌표가 아니니 new플래그도 내려줍니다.

    else: #처음 와보는 좌표인 경우,

        visited[nex] = [d] #좌표 기록에 추가해줍니다.
        visited[now].append((d+4) % 8) #반대 방향도 추가합니다.
        new = True #새로운 좌표에 도달했으니, 이제 기존 좌표에 도달하면 도형이 이어져 방이 생성됩니다. 플래그를 올립니다.

        if additional: #1 6 3처럼 대각선 교차로 방이 생성된 경우,

            shapes += 1 #방 갯수를 추가하고,
            additional = False #올라간 플래그를 초기화합니다.

    bef = now #없어도 됩니다.
    now = nex #아까 계산한 다음 좌표로 넘어갑니다.

#끝!
print(shapes)