🤔 PS(Problem Solving)

[백준/c++] 10610번 - 30

문제 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는 www.acmicpc.net 풀이 분류 : 그리디 30의 배수이면서, 최대인 값을 찾아야 합니다. 1.30의 배수는 끝자리가 무조건 0으로, 입력값에 0이 있는지 확인합니다.(없으면 -1 출력) 2.자리수를 내림차순으로 정렬합니..

[백준/c++] 10971번 - 외판원 순회2

문제 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 풀이 분류 : 완전탐색+dfs 코드(O(n)?) *O(n)이 아니라면 알려주세요. 감사합니다(--)(__)*

[백준/c++] 1525번 - 퍼즐

문제 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 풀이 분류 : 완전탐색 0만 3x3 위치로 옮기는게 아니라, 퍼즐판까지 1 2 3 4 5 6 7 8 0 순으로 맞춰야 하는 것이 이 문제의 핵심이었습니다. + bfs 결국 입력값을 123456780의 순서로 만들수 있는지를 체크하면 되었습니다. 1. 입력값을 string 문자열로 초기화하되, 0은 9로 치환해줍니다. 2. 처음 입력받은 문자열을 큐에 넣어줍니다. 3. 큐에서 pop한 문자열에서 9의 위치를 찾고, 9와 상하좌우를 스왑합니다. 4. 스왑으로 새로 만들어진 string문자열이, 캐시의 key로 이미 등록되어있는지 체크합니..

[백준/c++] 17298번 - 오큰수

문제 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 분류 : 큐, 스택 벡터(arr)와 스택(s)을 이용합니다. 입력 수열은 벡터에, 스택엔 벡터의 index를 저장합니다. 벡터의 길이만큼 for문을 돌면서, arr[i](현재 값) > arr[s.top()](이전 값) 이라면 오큰수를 찾은 것이므로 현재 값을 정답벡터에 넣어주고 스택은 pop해줍니다. 이후 수열의 길이만큼 반복. 코드(O(nm)) *O(nm)이 아니라면 알려주세요. 감사합니다(--)(__)*

[백준/c++] 1021번 - 회전하는 큐

문제 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 분류 : 큐, 스택, 시뮬레이션 현재 pivot 값을 기준으로 left, right의 거리를 계산, 더 짧은 거리로 이동해주며 이동거리를 증감해줍니다. 코드(O(nm)) *O(nm)이 아니라면 알려주세요. 감사합니다(--)(__)*

[백준/c++] 10866번 - 덱

문제 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘쨰 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net 풀이 분류 : 큐, 스택, 덱 문제에서 요구하는대로 덱을 만듭니다. 코드(O(n)) *O(n)이 아니라면 알려주세요. 감사합니다(--)(__)*

[백준/c++] 2164번 - 카드 2

문제 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리 www.acmicpc.net 풀이 분류 : 큐, 스택 입력값을 큐에 넣어주고, 문제에서 말하는 대로 큐의 size가 1이 아닐때 까지 pop(), push(), pop() 해줍니다. 코드(O(n)) *O(n)이 아니라면 알려주세..

[백준/c++] 4949번 - 균형잡힌 세상

문제 4949번: 균형잡힌 세상 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이룰 수 있다. 모든 왼쪽 대괄호("[")는 오른쪽 대 www.acmicpc.net 풀이 분류 : 큐, 스택 / 문자열 처리. 현재 문자가 [ or ( 이라면 스택에 넣고, ] or ) 이라면 먼저 스택의 top값 확인합니다. 스택의 top + 현재 문자 가 [] 또는 () ..

[백준/c++] 1874번 - 스택 수열

문제 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 풀이 분류 : 큐, 스택. 1. 먼저 입력으로 주어지는 수열을 스택에 담습니다. 2. 0부터 시작하는 pivot을 설정합니다. 3. pivot보다 n번째 수열값이 크다면, pivot++해주면서 +-가 담기는 정답스택에도 +를 담아줍니다. 4. pivot++해주다가 pivot과 n번째 수열값이 같은 경우가 온다면 정답스택에 -를 담아주고, 수열 스택도 pop해주고 pivot--..

[Level2/c++] 소수 찾기

문제 코딩테스트 연습 - 소수 찾기 | 프로그래머스 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. 013은 0, 1, 3 숫자가 적힌 종이 programmers.co.kr 풀이 에라토스테네스의 체를 응용한다. 0. 0이 맨 앞에 오지 않도록 문자열을 sort해준다. 1. 2~stoi(numbers.size())의 수 중에서 numbers의..