Dev_Diary

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문자열의 길이가 길다보니 일반적으로 탐색하면 시간초과가 걸립니다. 입력된 문자가 폭발하는 문자열의 마지막 문자인지 파악하고 마지막 문자열이 폭발하는 문자열인지 판단했습니다. import sys def solution(str_data, target_str): # 스택 stack = [] # 스택에 한 글자씩 입력 for string in str_data: stack.append(str..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 재귀적으로 접근하면 문제를 쉽게 풀 수 있습니다. def solution(N, data_list): # 카운트 global white global blue white = 0 blue = 0 # 재귀함수 호출 split_paper(data_list, [0, N], [0, N]) print(white) print(blue) # 구간을 쪼개는 함수 def split_paper..

https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 입력의 크기가 커서 100점 맞기가 어려운 문제였습니다. 단순히 순회하면 시간초과가 생기므로 누적합 리스트를 만들어 풀어야합니다. 문자별로 누적합 리스트를 만들어 풀었습니다. import sys from collections import defaultdict def solution(S, data_list): # 문자별 누적합 subsum = [[0..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 전형적인 백트래킹 문제입니다. 다만 조건 시간이 빡빡해 운이 안좋으면 실패, 운이 좋으면 통과라는 어이없는 결과가 나오기도 하는 문제입니다. 저의 경우에는 is_empty 함수의 if queen[row] == queen[i] 조건문이 원래 if queen[i] == queen[row] 였는데 순서를 바꾸어주자 넉넉하게 통과하기도 했습니다. 정확한 이유는 모르겠지만 코드가 맞고 다른 이들과의 코드와 차이를 잘 모르..

https://www.acmicpc.net/problem/25192 25192번: 인사성 밝은 곰곰이 첫번째 새로운 사람이 들어온 뒤 pjshwa, chansol, chogahui05은 모두 곰곰티콘으로 인사했다. 두번째 새로운 사람이 들어온 뒤 pjshwa와 chansol은 다시 곰곰티콘으로 인사했다. www.acmicpc.net 자료구조들의 특성을 잘 이용하면 쉽게 풀 수 있는 문제입니다. from collections import defaultdict def solution(N, data_list): # enter 횟수 enter = 0 # 채팅 기록 dict chat_log_dict = defaultdict(int) # 임시 기록 temp_count_set = set() # 채팅 기록을 순회하며 ..

https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 입력이 긴 문제의 경우 Input() 보다 sys.stdin.readline() 을 사용하는 것이 좋습니다. 그리고 readline 뒤에 \n 같은 공백 문자도 같이 입력되니 strip() 을 사용하면 깔끔하게 받아올 수 있습니다. 문제는 Dict 타입을 사용하면 쉽게 풀 수 있습니다. import sys from collections import defau..

https://www.acmicpc.net/problem/13414 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net 길이가 긴 입력의 경우, input() 보다는 sys.stdin.readline() 을 사용하는게 더 빠릅니다. 나머지는 Dict 자료구조를 사용하면 쉽게 해결할 수 있습니다. import sys from collections import defaultdict def solution(K, L, data_list): # 수강 대기 목록 사전 wait_dict = defaultdict(i..

https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 구현문제입니다. 문제를 이해하기만 하면 나름 간단하게 풀 수 있습니다. 1. 모래를 날릴 때 소수점은 버린다. -> 버린 소수점 아래의 모래는 그 자리에 남아있다. 2. 맵 밖으로 날아간 모래 역시 소수점은 버린다. 이 점만 고려하면 구현만 충실히 하면 풀 수 있습니다. def solution(N, data_list): # 초반 모래의 양 init_sum_sand ..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 데이터의 사이즈가 작은 편이기 때문에 모든 경우를 돌아가면서 거리를 구해보고 비교하면 쉽게 풀 수 있습니다. from itertools import combinations def solution(N, M, data_list): # 치킨집 리스트, 집 리스트 정리 all_chick_list = [] house_list = [] for i in range(N): for j in ..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 단순한 구현문제입니다. 다만 맵 구성시에 데이터로 주어지는 인덱스는 [0, 0] 을 1행 1열로 표현하고 있으니 이 점만 주의하면 쉽게 풀 수 있습니다. from collections import deque def solution(N, K, L, apple_list, dir_list): # 맵 # 0 빈공간 1 사과 2 뱀 data_map = [[0 for _ in range(N)] for __ in r..