1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 내가 짠 코드 (메모리 초과) string = list(input()) input_stack = [] output_stack = [] for s in string: if s == ")": iter_num = -1 while 1: input_top = input_stack.pop() if input_top != "(": output_stack.append(input_top) else: iter_num = input_stack.pop() break input_..

2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 쏘 이지한 문제지만 풀이 방법이 마음에 들지 않아서 다른 분들 코드랑 비교해봤다. 내가 푼 코드 deque 을 사용했다. 문제에서 원하는 것은 추월한 차의 수를 구하는 것. 즉 first in first out 을 위배한 경우를 카운트 하는 것이다. q1 이란 deque() 에 터널에 들어간 순서대로 원소를 담는다. 그리고 차례대로 터널을 빠져나오는 원소(out) 가 q1 의 첫번째와 일치하지 않다면, 해당 원소는 추월한 것으로 간주할 수 있다...

14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 처음 푼 코드 from itertools import combinations N = int(input()) arr = list(map(int, input().split())) max_value = sum(arr) num_set = set() for n in range(1, N+1): for c in combinations(arr, n): num_set.add(sum(c)) i = 1 while T..

2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net ⭐️ 사고 과정 서로 다른 2개의 용액 -> 음 포인트는 2개 numbers 의 최대 길이는 10만 -> 즉 조합은 시간초과 두 수를 더했을 때 가장 0에 가깝게. 크건 작건 상관없이 두 수의 합이 0에 가까우면 된다. 브루트포스 안돼 📌 solved point 정렬할 때 절대값이 작은 순서대로 정렬해야한다. 그렇게 하면 서로 차이가 비슷한 것끼리 모임. 어떻게 절대값이 작은 순서대로 저장할 수 있는데? -> lambda bab..

전형적인 그리디 알고리즘이다 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net ⭐️ 풀이 다른 분들 풀이 보니까 heapq 를 사용했던데, 나는 리스트를 사용했다. 1. 가장 먼저 시작하는 강의 기준으로 정렬 친다. 2. 차례대로 리스트에 저장하되, 끝나는 시간만 저장한다. 3. 강의를 차례로 순회 -> 리스트에 저장된 수보다 강의 시작 시간이 더 크다면, 저장된 인덱스에 끝나는 시간을 저장한다. (이전 강의 끝나는 시간 < 다음 강의 시작시간 : 강의실 사용 가능) 강의실 교체가 필요할 때 de..

12845번: 모두의 마블 영관이는 게임을 좋아한다. 별의별 게임을 다 하지만 그 중에서 제일 좋아하는 게임은 모두의 마블이다. 어김없이 오늘도 영관이는 학교 가는 버스에서 캐릭터 합성 이벤트를 참여했다. 이번 이 www.acmicpc.net 포인트 여러 케이스를 만들어 시도하다보면 결국 가장 큰 카드를 중심으로 합성을 시작해야 함을 알 수 있다. 그리고 더 중요한 포인트는, 결국 가장 큰 (숫자) 카드가 다른 모든 카드와 합성 된다는 것. 문제에서는 인접한 카드끼리 합성한다고 돼 있어, 카드의 순서를 변경하면 안된다고 생각할 수 있다. 하지만 숫자가 가장 큰 카드를 중심으로 모든 카드가 합성되기에 단순히 정렬시켜도 무방하다. 정렬후엔 모든게 수월해진다. 코드 N = int(input()) cards =..

1455번: 뒤집기 II 세준이는 동전 뒤집기를 하려고 한다. 세준이는 동전을 N×M개 가지고 있다. 동전은 세로로 N개, 가로로 M개 크기의 직사각형에 차곡차곡 놓여져 있다. 동전의 앞면을 0이라고 하고 뒷면을 1이라고 www.acmicpc.net board = [list(map(int, list(input()))) for _ in range(N)] def flip(R, C): for r in range(R + 1): for c in range(C + 1): # 방법 1 board[r][c] = 0 if board[r][c] else 1 # 방법 2 board[r][c] ^= 1 # 방법 1, 2 중 하나를 주석 처리해서 사용 count = 0 for n in range(N - 1, -1, -1): f..

https://www.acmicpc.net/problem/1527 1527번: 금민수의 개수 첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 브루트 포스 냄새가 살살 나길래 permutation 으로 첨엔 접근했다. 어케 접근했냐면, 입력된 수의 길이 만큰 [4] 와 [7] 배열을 늘림. 늘린 [4] , [7] 배열을 합침. -> [4] * len(인풋값) + [7] * len(인풋값) 합쳐진 배열을 permutations 에 넣고 경우의 수를 구함. 당연히 시간 초과남... 불필요하게 4 와 7 배열을 늘려놓은게 시간초과의 원인이었..

2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net dfs 폼 미쳤다 result = set() dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] res = [list(map(str, input().split())) for _ in range(5)] def dfs(r_, c_, tmp): if len(tmp) == 6: result.add(tmp) return for i in range(4): nx = c_ + dx[i] ny = r_ + dy[i] i..