개발하는 개구리

🐸 문제 정보 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net 🤖 알고리즘 그리디, 구현 ⏱️ 풀이 시간 12.59m 📝 풀이 예제를 직접 손으로 그려보면 그리디라는 것을 쉽게 파악할 수 있었다. 각각 최대값과 최소값을 찾는 순서는 아래와 같다. 둘다 기본적으로 주어진 입력에 대해 앞에서부터 순회한다. 최대값 M이 나오면 stack에 담는다. K가 나오면 K를 포함한 stack의 길이(n) 만큼 5 * (10 ^ (n - 1))를 문자열로 바꿔 정답 문자열에 더해준다. 마지막에 stack에 담겨진 M을 모두 1로 치환하여 정답 문자열에 더해준다. 최소값 M이 나오면 stack에 담는다. K..

🐸 문제 정보 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 15.14m 📝 풀이 처음에 숫자 야구 규칙을 직접 코드로 구현해야하나..? 하고 헉 했는데, 알고보니 그냥 순열에서 조건 맞지 않는 요소를 제거하는 문제였다. 파이썬이니까 permutation 쓰고, set으로 시간복잡도를 조금이라도 줄이고자 했다. 🧑‍💻 나의 답 # pypy3 import sys from itertools import permutations input = sys.stdin.readline n ..

🐸 문제 정보 16960번: 스위치와 램프 첫째 줄에 스위치의 수 N, 램프의 수 M이 주어진다. 둘째 줄부터 N개의 줄에는 스위치에 대한 정보가 주어진다. 스위치 정보의 첫 번째 정수는 그 스위치와 연결된 램프의 수이고, 이후 연결된 램 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 18.47m 📝 풀이 스위치에 연결된 램프의 번호를 딕셔너리 형태로 변경한다. 램프번호 : 개수 스위치를 하나씩 순회하면서, 해당 스위치가 꺼져도 모두 켜져있는지 확인한다. 이 문제에 핵심은 2차원 리스트를 {램프번호 : 개수} 형태의 딕셔너리로 변경하는 것이었다. 파이썬의 내장 모듈이 워낙 강력해서... Counter와 리스트 컴프리헨션으로 쉽게 풀 수 있었다. 🧑‍💻 나의 답 # pypy3 import ..

🐸 문제 정보 5883번: 아이폰 9S 사람 9명이 줄을 서있고 각 사람이 원하는 용량의 크기는 2, 7, 3, 7, 7, 3, 7, 5, 7 이다. 용량 3을 원하는 사람을 줄에서 빼버리면, 줄은 2, 7, 7, 7, 7, 5, 7가 되고, 7을 원하는 사람이 4명이 연속된 구간이 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 12.32m 📝 풀이 처음에 2차원 DP로 풀어야하나 했으나(LCS..?) LCS 개념과는 약간 다른 것 같아 구현으로 풀어봤더니 풀렸다. 구현으로 풀면 간단하게 풀 수 있는 문제였다. set을 이용해서 용량 종류 파악하기 용량 종류를 하나씩 빼서 새로운 배열을 할당하고, 해당 배열에서 연속된 용량의 길이 구하기 마지막에 정답을 한 번 더 갱신해주는 것이 중요하다..

🐸 문제 정보 3005번: 크로스워드 퍼즐 쳐다보기 첫째 줄에 R과 C (2 ≤ R, C ≤ 20)가 주어진다. R는 행의 개수, C는 열의 개수이다. 그 다음 R개의 줄엔 C개의 문자가 포함되어 있다. 각 문자는 영어 알파벳 소문자 또는 '#'이며, '#'인 경우에는 막혀 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 21.34 📝 풀이 처음에 문제 이해도 안되고, BFS로 풀어야하나 하고 조금 고민하느라 시간이 오래 걸렸다. 그냥 십자말풀이라고 적어놓지... 왜 크로스워드 퍼즐이라고 적어놨을까.... 여튼 풀이 방법 자체는 간단했다. 행과 열을 문자열로 각각 분리 각 행과 열에 대해서 #으로 split 길이가 1 이상이라면 substring 조건에 충족하므로, res 배열에 담기 re..

🐸 문제 정보 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 31.25m 📝 풀이 그리디처럼 풀면서 최적의 방법을 찾다가... 계속 틀리길래 '이게 맞나'란 생각이 들었다. 알고보니 그냥 생구현으로 풀 수 있는 아주 쉬운 문제였다ㅠㅠ 처음에는, 단어를 정렬해서 사전 순 앞에 나오는 문자의 인덱스를 뒤에서 부터 찾아내고 잘라서 넣는.. 과정을 거쳤다. 틀린 풀이 더보기 import sys input = sys.stdin.readline word = input().rstrip()..

🐸 문제 정보 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 47.05m 📝 풀이 완전 대기업 코테에서 나올 것 같은 문자열 + 빡구현 문제였다...! 좋은 문제인둣...! 조건을 나눠서 그에 맞게 구현하면 되는 문제이다. 각 판에서 x는 5개, o는 4개가 최대이며, 이보다 더 많이 있다면 무조건 invalid x가 먼저 시작하기 때문에, x가 o보다 1개 많거나 같아야한다. x가 o와 같은 개수라면, o가 이기는 경우로 끝나야 유효하다. x가 o보다 1개 더 많다면, ..

🐸 문제 정보 4659번: 비밀번호 발음하기 좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtp www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 22.01m 📝 풀이 실버 5임에도 구현이라 체감상 실버 2~3으로 느껴졌다. 문제에서 제시한 조건대로 빡구현하는 되는 문제였다. 모음의 경우 딕셔너리로 설저해놔서 시간복잡도를 줄였다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline gather = {'a': True, 'e': True, 'i': True, 'o': True, 'u': True} while ..

🐸 문제 정보 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 18.31m 📝 풀이 쉬운 구현 문제였다. 뒤에서부터 순회하면서 아래 조건대로 정답 리스트에 (인덱스 + 1)을 추가해주면 되는 문제였다. 왼쪽에 나보다 큰 사람이 없다면, 정답 리스트 가장 왼쪽에 (인덱스 + 1) 추가 왼쪽에 나보다 큰 사람이 있지만, 내 순서가 정답 리스트의 길이보다 작다면, 내 순서가 될 자리에 (인덱스 + 1) 추가 왼쪽에 나보다 큰 사람밖에 없다면, 정답 리스트 가장 오른쪽에 (인..

🐸 문제 정보 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 🤖 알고리즘 스택 (이라고 적혀있지만 구현에 가깝다) ⏱️ 풀이 시간 30.25m 📝 풀이 보자마자 스택 문제인 것은 알았지만, 스택보다는 구현에 가까운 문제였다. 가장 높은 지점을 기준으로, 왼쪽 오른쪽에서 최대값은 의미가 없다는 것을 알아야했다. 때문에 입력 값에서 가장 높은 지점의 인덱스를 찾은 후, 그 지점을 기준으로 왼쪽 오른쪽 각 1회씩 탐색하면서 스택 형태로 값을 더해주면 되는 문제였다. 문제에서 모든 인덱스에 h가 있..