본문 바로가기

Algorithm

 (18)
백준 2567번 : 색종이-2 문제 2567번: 색종이 - 2 (acmicpc.net) 2567번: 색종이 - 2 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 색종이를 겹쳐서 붙였을 때, 전체 색종이의 둘레를 구하는 문제 아이디어 두가지 방법으로 풀이할 수 있는데 두 방법 모두 '우선 색종이를 붙인 다음' 시작한다. 색종이를 붙이는 방법은 이중 for 문 돌면서 0을 1로 바꿔주면 된다. 방법 1. 이중 for문으로 풀이 흰 도화지 전체를 돌면서 진행 색종이 부분(= 값이 1인)을 만나면, 4개의 방향에 있는 값을 조사 4변을 조사하는 방법은 {{0, 1}, {0,..
백준 10434번 : 행복한 소수 문제 10434번: 행복한 소수 (acmicpc.net) 10434번: 행복한 소수 각 테스트 케이스마다, 테스트 케이스의 번호, 입력받은 수, 만일 M이 행복한 소수라면 YES 아니라면 NO를 공백으로 각각 구분하여 출력한다. www.acmicpc.net 정수가 입력될 때 그 정수가 행복한 소수인지를 출력하는 문제. 행복한 소수란, 각 자리의 제곱의 합을 구하는 것을 반복했을 때 1이 나오는 소수 아이디어 ❗어떤 소수가 행복한 소수가 아닌 경우, 각 자리 제곱의 합은 어떤 패턴을 띄게 되어있다. 행복한 소수는 우선 소수여야 한다. -> 1과 소수가 아닌 수는 바로 NO 출력 입력된 수가 소수이면, 제곱의 합을 구한 다음 이미 나온 수인지를 반복문 안에서 확인한다. 이미 나온 수인지 확인하는 방법 : 합..
백준 2992번 : 크면서 작은 수 문제 2992번: 크면서 작은 수 (acmicpc.net) 2992번: 크면서 작은 수 정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 www.acmicpc.net 아이디어 1. case를 분류해서 조건식으로만 푸는 방법 각 자리수를 index 취급 숫자가 모두 내림차순으로 정렬되어있으면, 더 커질 수 없으므로 0출력 숫자 중에 오름차순으로 정렬된게 있는지 확인, 이는 숫자의 순서를 바꿈으로써 커질 수 있는 위치를 뜻함 오름차순이 발견된 idx 중에서 가장 뒤에 있는 idx를 찾기 = point로 저장 point 뒤에 있는 수 중에서 point 해..
백준 2304번 : 창고 다각형 문제 2304번: 창고 다각형 (acmicpc.net) 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 아이디어 첫번째 trial : 극댓값을 기준으로 설계 (엄청 공들여서 설계했는데, 틀렸었음 ㅠ) 기둥들을 배열로 보면, 위 그림은 {4,0,6,3,0,0,10,0,0,4,0,6,0,8}이라 생각할 수 있다. 이때 기준이 되는 기둥들의 특징은 '기울기가 바뀌는 부분(=극댓값)'이라 생각함 따라서 극댓값에 해당하는 배열로 표시하고, 그 배열을 돌면서 너비를 구함 틀린 이유 : 극댓값으로 접근을 ..
백준 5397번 : 키로거 문제 5397번: 키로거 (acmicpc.net) 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 아이디어 1406번과 동일한 로직으로 풀이했다. 1406번은 텍스트와 명령어가 따로 주어졌다면, 5397번은 인라인으로 주어졌다는 차이점 정도! 심지어 StringBuilder로 delete, insert하다가 시간 초과 떠서 데크 2개로 해결한 것조차 동일.. 커서가 나오는 문제는 커서 왼쪽 데크, 오른쪽 데크를 만들어서 풀어야 하나보다! 알게된 것 백준 문제는 무조건 시간 복잡도가 낮은 것으로 풀이해야..
백준 1406번 : 에디터 문제 1406번: 에디터 (acmicpc.net) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 커서를 이용해서 문자열을 편집하는 문제 아이디어 🔸 첫번째 시도 : 커서와 문자열을 분리해서 해결. 문자열 편집에는 char[ ]을 이용. 결과 : 시간 초과 1. 하나의 명령어가 주어질 때 '커서를 계산하는 함수'와 '문자열을 계산하는 함수'를 호출하므로 함수 호출이 빈번 2. char 배열을 이용했으므로 문자열을 편집할 때마다 새로운 길이의 배열을 만들고, → 매번 공간 복잡도 O(n) 이전 배열을 복사하기 위..
백준 2608번 : 로마 숫자 문제 2608번: 로마 숫자 (acmicpc.net) 2608번: 로마 숫자 첫째 줄과 둘째 줄에 하나씩 로마 숫자로 표현된 수가 주어진다. 입력된 각 수는 2000 보다 작거나 같고, 두 수의 합은 4000보다 작다. www.acmicpc.net 주어진 로마 숫자의 합을 정수와 로마 숫자로 출력하는 문제 아이디어 🔸로마문자 to 정수 : 해시맵 이용 순방향의 경우 바로 정수로 바꾸고, 역방향의 경우 다음 문자와 결합하여 정수로 바꿈 마지막 문자는 바로 정수로 바꿈 주어진 로마자가 하나인 경우 구현한 방향 로직을 실행할 수 없으므로 따로 빼주어서 바로 정수로 바꿈 🔸정수 to 로마문자 : 배열 2개 이용 키를 기준으로 정렬된 해시맵을 구현하기 위해서 정적배열 2개 이용 각 인덱스끼리 매핑되게 하면, '정..
[프로그래머스] 숫자 문자열과 영단어 문제 코딩테스트 연습 - 숫자 문자열과 영단어 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아이디어 [러프한 아이디어] step1) 영어 단어가 존재하는지 탐색 step2) 존재하는 위치에서 char 하나만 남기고 삭제 step3) 남은 하나의 char은 숫자로 변환 [아이디어 구현] step 1~3를 하며 문자열 수정이 자유롭도록 StringBuilder 사용 step1) 영어 단어가 존재하는지 탐색 : 단어가 담긴 자료구조를 돌면서 sb.indexOf(str)를 하고, -1이 아닐 경우 ste..

티스토리툴바