프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이 1def test(arr): new_arr = [] for i in range(2): time = arr[i] hour, minute = time.split(":") new_time = int(hour) * 60 + int(minute) # 대실 종료시각의 경우 청소시간을 포함해서 10분을 추가 if i == 1: new_time += 10 # 대실 종료시각이 23:5..
파이썬
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 유형에는 완전탐색이라고 되어 있기하던데 난 다른 방식으로 풀었다.n개의 송전탑이 하나의 트리 형태로 연결되어 있고, 그 중 하나의 전선을 끊어 두 개의 트리로 만든다.그리고 각 트리에서의 원소 개수 차이가 최소가 되는 그 최소값을 구하면 된다. union-find를 통해서 풀었다.반복문을 통해 각 전선을 하나씩 제거하면서 union-find연산을 통해 각 송전탑들이 속하고 있는 트리를 저장한다.그리고 각 경우에 대해, 트리에 속한 송전탑의 개수 차이가 최솟값인 경우를 갱신해서 리턴한다. 풀이 코드from coll..
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 처음에 DP를 활용해서 풀었다.2차원 DP 테이블을 만들어서 dp[i][j]에 sequence[i] ~ seqence[j]의 합을 저장하는 형식으로 코드를 작성해봤다.그리고 각 i를 돌면서 만약 k와 값이 같다면 해당 시작인덱스, 끝인덱스를 candidate라는 리스트에 저장한다.그리고 k보다 큰 경우에는 해당 row를 더 이상 탐색할 이유가 없으므로(합이 k보다 커질수 밖에 없으므로), 다음 행으로 넘어간다. 처음 풀이def solution(sequence, k): n = len(sequence) c..
https://www.acmicpc.net/problem/9935 스택을 활용하면 되는 문제다.폭발 문자열에 해당하는 문자열이 스택의 탑에 오는 경우에 pop해버리면 된다. 첫 풀이import sysinput = sys.stdin.readlineword = input().rstrip()bomb = input().rstrip()len_word = len(word)while True: word = word.replace(bomb, '') if len_word == len(word): break else: len_word = len(word)if word == '': print('FRULA')else: print(word) 처음에는 replace를 사용해서..
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 처음에는 n의 124 나라에서의 숫자의 자리수를 구한 후, 해당 자리수만큼 중복순열(product)를 사용해 리스트를 만든 후, 해당 리스트의 인덱스에 해당하는 수를 리턴하도록 했다.이러면 내가 구하려는 수 말고도, 자리수에 해당하는 124 나라에서의 모든 수를 구해야 하므로 쓸 데 없는 계산을 많이 해, 시간 초과가 뜬다. 시간 초과 풀이from itertools import productdef solution(n): answer = '' i = 3 cnt = 1 # 자리수 whil..
https://www.acmicpc.net/problem/1406 스택 혹은 큐를 활용해서 풀면 되는 문제.커서를 기준으로 left, right 두 스택 혹은 큐로 나눠서 로직을 구현하면 된다. 처음에는 스택을 활용해서 풀었다.import sysinput = sys.stdin.readlineleft = list(input().rstrip())right = []n = int(input()) # 명령 개수for _ in range(n): command = input().rstrip() if command == 'L': if left: char = left.pop() right.append(char) elif command == 'D': ..
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 그리디 문제다.그리디는 정말... 풀이가 딱 떠오르지 않으면 푸는데 한참 걸리거나 못 푸는 것 같다.그래서 많이 풀어보는 게 중요하다는 생각이 든다. 풀이를 계속 생각해봤지만, 계속 아니더라..결국 구글링을 참고해서 풀었다. def solution(number, k): answer = '' stack = [] for num in number: while k > 0 and stack and stack[-1] 0: stack = stack[:-k] ..
https://www.acmicpc.net/problem/10799 스택을 활용하는 문제다. # 10799번: 쇠막대기import sysinput = sys.stdin.readlinearr = list(input())stack = [arr[0]]cnt = 0 # 잘려진 쇠막대기 조각의 총 개수for i in range(1, len(arr)): check = arr[i] # 만약 현재 넣으려는 괄호가 '('인 경우에는 stack에 집어 넣는다. if check == '(': stack.append(check) # 만약 현재 넣으려는 괄호가 ')'인 경우에는 더 구체적으로 확인한다. elif check == ')': stack.pop() # stack에는 ..
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 큐 자료형을 활용한 문제다. 길이가 같은 두 큐에 들어있는 원소의 합을 같게 만들면 된다.큐는 pop을 통해 먼저 들어간 원소가 나오고, append를 통해 뒤에 원소를 추가한다.이런 큐의 성질을 활용해 로직을 구현했다. from collections import dequedef solution(queue1, queue2): n = len(queue1) # 각 큐의 길이 total = sum(queue1) + sum(queue2) # 모든 큐의 합 # 모든 큐의 합이 홀수인 경우에는 각 큐..
https://www.acmicpc.net/problem/1689 그리디 문제다.여러 선분의 시작점과 끝점이 주어졌을 때, 겹치는 선분의 최대 개수를 출력하는 문제다. 처음에는 각 선분의 좌표가 .5를 지나가는 경우 1을 더해주는 방식으로 구해보려고 했다.예를 들어 선분의 시작점, 끝점 좌표가 (3, 6)인 경우에는 3.5, 4.5, 5.5를 지나가는 것이다.그러므로 리스트를 선언해 전체 좌표에 대해 지나가는 선분의 개수를 저장하려고 해봤는데,생각해보니 선분의 개수가 100만개이고, 선분의 좌표의 절댓값이 10억 이하이므로 무조건 시간초과가 나기 때문에 구현하지 않았다. 그 다음 아이디어로, 입력받은 좌표들을 정렬한 후에, 조건을 넣어줘서 선분 개수의 최댓값을 갱신해주면 되지 않을까?라는 생각이 들어서 ..
