본문 바로가기

🔅코딩테스트 공부🔅213

[프로그래머스] Level2 할인 행사(python) https://school.programmers.co.kr/learn/courses/30/lessons/131127 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 해결 방법 dictionary + 슬라이딩 윈도우를 이용해서 문제를 풀었는데, Counter를 이용하면 불필요한 절차 없이 쉽게 구할 수 있다. - 슬라이딩 윈도우 def solution(want, number, discount): want_dic = {} #원하는 할인 제품 new_dic = {} #투 포인터 for i in range(len(want)): #원하는 제품 목록 딕셔너.. 2023. 3. 8.
[백준] 1377번 버블 소트(python) https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 1. 문제 해결 과정 n의 크기가 500,000이기 때문에 버블 정렬 알고리즘을 코드로 구현해 풀면 시간초과가 발생한다.(버블 정렬은 O(N^2)) 따라서 index를 이용한 아이디어를 이용해 문제를 풀어야한다. 오른쪽에 작은 수가 있는 경우, 한 번의 loof에서 1만큼의 인덱스가 왼쪽으로 이동한다. 이 경우에 (정렬 전 index) - (정렬 후 index)를 하면 양수.. 2023. 3. 8.
[프로그래머스] Level2 호텔 대실(python) https://school.programmers.co.kr/learn/challenges?order=recent&levels=2%2C3&languages=python3 코딩테스트 연습 | 프로그래머스 스쿨 개발자 취업의 필수 관문 코딩테스트를 철저하게 연습하고 대비할 수 있는 문제를 총망라! 프로그래머스에서 선발한 문제로 유형을 파악하고 실력을 업그레이드해 보세요! school.programmers.co.kr 1. 내가 작성한 코드 heap을 이용하면 될 것 같다는 생각을 하긴 했는데, 그냥 문자열로 풀었다. 이유는.. 나도 모른다.. 아마 내가 고집쟁이기 때문.. 결국 반례를 하나 못 찾아서 3시간 걸려서 풀었다. => 반례 : 방 청소가 끝났을 때 23:59분이 넘어가면 방을 빌려줄 수 없는데 00:.. 2023. 3. 7.
[프로그래머스] Level2 숫자 변환하기(python) https://school.programmers.co.kr/learn/courses/30/lessons/154538 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 해결 방법 BFS를 이용해 x+n, x*2, x*3 만큼 이동시키며 문제를 풀었다. 백준 숨바꼭질과 유사한 문제라서 한 번 풀어보시길 추천 from collections import deque def solution(x, y, n): visit = [0] * (y+1) visit[x] = 1 if bfs(x,y,n,visit) == False: return -1 else: return.. 2023. 3. 7.
[백준] 17298번 오큰수(python) https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 1. 난이도 골드 4 2. 문제 해결 방법 시간초과, 메모리초과 난사로 멸망당하고 구글링을 해서 풀었다. answer이라는 배열을 -1로 모두 저장해놓은 후, stack에 값이 있고, num[index] > stack[top] 인 경우 인덱스를 이용해 정답 배열에 오큰수를 저장한다. 위의 과정이 끝나면 현재 인덱스를 스택에 저장하고 다음 인덱스로 넘어간다. import sys input = sys.stdin.. 2023. 3. 7.
[프로그래머스] Level2 미로 탈출(python) https://school.programmers.co.kr/learn/courses/30/lessons/159993 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 해결 방법 BFS나 DFS를 이용하는 문제 레버와 탈출구를 찾을 수 있는 경우 (start에서 레버까지의 이동 거리) + (레버 위치에서 탈출구까지의 이동 거리)를 return 만약 레버나 탈출구 둘 중 하나를 찾을 수 없는 경우 -1을 return 2. 내가 작성한 코드 from collections import deque def solution(maps): n = len(maps).. 2023. 3. 6.
[프로그래머스] Level2 덧칠하기(python) https://school.programmers.co.kr/learn/courses/30/lessons/161989 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결 방법 투 포인터를 이용해서 문제를 해결했다. 벽을 칠해야 하는 section이 오름차순으로 정렬되어 있기 때문에 첫 start는 벽의 제일 좌측 값인 section[0], end는 start + (m-1) (start부터 시작해서 롤러 한 번에 칠할 수 있는 범위)을 넣어준다. section에 있는 값을 하나씩 for문에 넣어주며 1) end보다 작은 경우 => 이미 칠한 경우이기 때문에 .. 2023. 3. 6.
[백준] 11003 최솟값 찾기(python) https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 1. 난이도 플레티넘 5 이 문제의 데이터의 범위는 0 ~ 5,000,000이기 때문에 정렬(O(nlogn))을 이용해서 풀면 시간초과가 발생한다. 따라서 deque를 이용해 정렬을 진행해야한다. 문제를 해결하는 알고리즘은 1. deque의 마지막에 있는 값들부터 현재 들어올 값보다 크면 최솟값이 아니기 때문에 모두 pop을 시킨다. 2. dequq의 마지막에 현재.. 2023. 3. 6.
[백준] 12891번 DNA 비밀번호(python) https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 1. 난이도 실버2 (🥈) 2. 문제 해결 방법 부분문자열의 크기가 1,000,000으로 크기 때문에 시간복잡도 O(n) 으로 해결해야한다. 따라서 슬라이딩 윈도우 + 딕셔너리를 이용해서 문제를 해결했다. (다른 푼들이 푸는 코드를 보니 단순하게 if elif를 사용하는게 더 이득이었던 거 같음,,) 1. DNA라는 딕셔너리를 선언해주고, 첫 start 부터 end까지의 염.. 2023. 3. 5.

티스토리툴바