개발하는 사막여우

https://www.acmicpc.net/problem/2161 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 소스코드 풀이 ★ 알고리즘 분류 중 '구현'에서 이 문제를 봤고, 선입선출 구조를 가지고 있는 큐를 사용하여 문제를 풀었습니다 ★ 1부터 n까지의 수가 들어있는 큐와 버리는 수들을 저장하는 배열 k를 만들어줍니다. n-1만큼 반복을 하면서 큐에서 2개의 수를 leftpop 합니다. 그 수 중 처음오는 수는 버리는 수이기 때문에 k에 저장하고 두번째 수는 큐의 맨 뒤로 append 해줍니다. ★ 반..

https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 소스코드 풀이 ★ 문제를 봤을 때 승률(z)이 변하는 최소 게임 수를 구하라고 했는데, 승률이 오르는 경우 뿐만 아니라 내리는 경우도 있지 않나 싶어서 조금 헤맸던 거 같습니다. ★ 승률 k를 구하는 과정에서 소수점 이하를 내림 처리 해주는 math 모듈의 trunc 함수를 사용하였습니다. 처음엔 k = m.trunc((y/x)*100)으로 승률을 구했는데 정답 처리가 계속 오답으로 떠서 ..

https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 소스코드 풀이 ★ 딕셔너리를 사용하여 입력받은 배열 안의 수가 몇번 나오는지 확인해줍니다. ex) a = [1,1,2,3,4,2,1] => {1: 3, 2: 2, 3: 1, 4: 1} ★ 정답을 저장하는 배열 ans는 -1로 초기화 하는데, 만약 해당 수의 오등큰수가 없다면 -1이 출력되어야 하기 때문입니다. ★ 입력받은 배열을 읽으면서 stack의 최상단의 값이 딕셔너리 안에 가지고 있는 수가 해당 값의 수..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 소스코드 풀이 ★ 정렬된 리스트 a의 시작부분과 끝부분을 투포인터로 잡고, 그 값들을 더한 값이 0에 가까운 수들을 찾아줍니다. lt가 rt보다 작을 때만 반복문을 도는 이유는 문제에서 n개의 용액들 전부 특성이 다르기에 중복되는 수가 없기 때문입니다. ★ 투포인터를 더한 절대값(mid값)이 ans보다 작으면 그 값이 0에 가장 가까운 값이 됩니다. 만약 mid ..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 소스코드 풀이 ★ 입력으로 주어진 m개의 수를 가지고 있는지 없는지 판단하기 위해 이분 탐색을 합니다. 먼저 a를 오름차순으로 정렬한 뒤 시작점(lt), 끝점(rt)를 0과 n-1로 설정합니다. ★ b의 원소들에 대해 반복문을 돌면서 x와 mid값을 인덱스로 가지고 있는 a의 값이 같다면 숫자를 가지고 있는 것이기에 1을 출력하고, while문이 break없이 정상적..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 소스코드 - 자료형 - 이분탐색 풀이 ★ 이번 문제는 자료형을 사용하거나 이분탐색을 사용하는 방식으로 해결할 수 있는 문제입니다. 먼저 자료형 set을 사용하면 입력받은 a리스트에서 중복된 수가 제거되고 값들을 정렬한 형태로 반환합니다. b 리스트를 돌면서 in을 활용하여, 해당 수가 a에 들어있다면 1을, 없다면 0을 출력합니다. ★ 이분탐색을 위..

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 소스코드 풀이 ★ k개를 제거하여 가장 큰 수를 만들어야 하기 때문에 수들을 stack에 넣어가며 대소비교를 해줘야 합니다. stack 안에 들어있는 값보다 비교하려는 값이 더 작다면 그 수는 stack에 들어올 수 없습니다. ★ for문을 돌면서 stack이 비어있지 않고, 제거해야 하는 갯수인 k가 0보다 크다면 stack의 최상단 값과 반복문을 도는 값의 크기 비교를 해줍니다. 만약 stack안에 있는 값이 작다면 pop으로 제거해주고, k또한 -1 해줍니다. 크다면 ..

https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 소스코드 풀이 ★ 입력받은 문자열의 문자들을 stack에 추가하면서 stack의 뒤에서 두번째 글자부터 끝까지의 글자가 ['A','A'] or ['B','B']일 경우 그 문자열은 좋은 단어이기 때문에 삭제해주는 과정을 진행합니다. ex) ABBA stack = ['A'] stack = ['A','B'] stack = ['A','B','B'] => 'B','B' pop 되고, cnt += 1 stack =[..

https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 소스코드 풀이 ★ n만큼 반복문을 돌면서 stack이 비어있지 않고, 스택의 최상단에 있는 값이 반복문 해당 값보다 작거나 같으면, 스택에서 pop해준 뒤, 해당 값을 append 해줍니다. ex) k = [6,9,7,6,4,6] i = 0, stack = [0] i = 1, stack = [1] i = 2, stack = [1,2] i = 3, stack = [1,2,3] i = 4, stack = ..

https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 소스코드 풀이 ★ 문제에서 커서에 대한 위치가 나올 때 2개의 스택을 활용하여 푸는 문제라고 생각했습니다. 이와 비슷한 문제들이 종종 있는 거 같아용 ★ 입력받은 문자열을 돌면서 x가 괄호를 만나는지, 백스페이스를 만나는지 아니면 문자인지에 따라 수행이 달라지게 됩니다. X == ''을 만날 때는 커서가 오른쪽으로 이동해야 하기 때문에 s2에 있는 마지막 원소를 s1에 추가해줍니다. 만약 ..