문제 - 스택은 자료를 넣는(push) 입구와 자료를 뽑는(pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 LIFO(Last int First out) 특성을 가짐 - 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있음 - 스택에 push하는 순서는 반드시 오름차순을 지킴 - 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지 판단 - 만들 수 있다면 어떤 순서로 push와 pop 연산을 수행하는지 계산(push : + / pop : -) 해결방법 java의 stack 클래스를 사용하여 문제를 해결하였다. 스택에 push할 때, 이전에 push 되었던 수를 또 넣을 순 없기 때문에 이전에 넣었던 최대값을 저장해두고 그 값 이상의..
문제 - 길이가 제각각인 K개의 랜선으로 같은 길이의 N개의 랜선을 만들어야 함 - 이미 자른 랜선은 붙일 수 없고 버려야 함 - 랜선을 자르거나 만들 때 손실되는 길이는 없음 - 기존 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없음 - 항상 정수 길이만큼 자름 - N개보다 많이 만드는 것도 N개를 만드는 것에 포함 - K는 1 이상 10,000 이하의 정수 - N은 1 이상 1,000,000 이하의 정수 - 항상 K
문제 - 종말의 숫자란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수 (666, 1666, 2666, ...) - 영화감독 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지으려고 함 - N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자)와 같음 - 숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램 작성 해결방법 첫 번째 종말의 숫자인 666부터 1씩 증가하는 숫자를 문자열로 바꾸어주고 해당 문자열 내에 "666"이 포함되어 있는지를 검사하는 방식으로 코드를 작성하였다. "666"이 포함되어 있으면 시리즈가 하나씩 늘어나는 것이므로 count 변수를 두어 하나씩 증가할 수 있도록 하였고, 해당 count가 입..
문제 - 뒤에서부터 읽어도 똑같은 단어를 팰린드롬이라고 함 - 수의 숫자들을 뒤에서부터 읽어도 같다면 그 수는 팰린드롬수 - 앞에 무의미한 0이 올 수 있다면 010이 되어 팰린드롬수로 취급할 수도 있지만, 이 문제에서는 무의미한 0이 앞에 올 수 없음 - 121, 12421 등이 팰린드롬수 해결방법 입력받은 숫자를 문자열로 취급하여, 맨 뒤부터 접근하여 거꾸로 뒤집은 숫자를 입력받은 숫자와 비교할 수 있도록 하였다. 이 과정에서 두 숫자가 같으면 팰린드롬수로 판단하여 yes를, 다르다면 팰린드롬수가 아니기 때문에 no를 출력할 수 있도록 하였다. 코드 import java.io.*; import java.util.*; class Main{ public static void main(String[] ar..
문제 - 첫째 줄에 단어 개수 N을 입력받음 - N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어들을 N개 입력받음 - 아래의 조건에 따라 정렬 1. 길이가 짧은 것부터 2. 길이가 같으면 사전 순으로 고찰 Comparator를 이용하여 정렬하고 싶었지만, 오랜만에 코드를 짜는 것이였기 때문에 잘 기억이 안나 Comparable과 Comparator에 대해 다시 공부를 하고 코드를 작성하였다.. 2022.07.05 - [JAVA] - [JAVA] Comparable / Comparator [JAVA] Comparable / Comparator 객체들을 정렬하기 위해서는 정렬 기준이 필요하다. 단순한 숫자, 문자와 같은 기본형(primitive) 데이터는 Arrays.sort() 메서드를 이용하여 알아서 정..
문제 - 현재 한수의 위치 (x, y)에서 가장 가까운 변을 찾아 직사각형에서 탈출하는 문제 - 직사각형의 크기는 w x h 해결방법 현재 한수의 위치와 직사각형 사이의 거리(상, 하, 좌, 우)를 각각 계산하여 그 중에서 최소값을 찾아 출력하는 방식으로 코드를 작성하였다. 코드 import java.io.*; import java.util.*; class Main{ static int x, y, w, h; static int result = Integer.MAX_VALUE; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)..
문제 - 입력받은 MxN 보드판에서 8x8 크기만큼 떼어내어 체스판처럼 칠하는 문제 - 각 칸이 검은색, 흰색으로 번갈아가면서 칠해져 있어야 함 - 8x8 크기는 아무데서나 골라서 사용 - 다시 칠해야 하는 정사각형(1x1)의 최소 개수 구하기 해결방법 처음에는 8x8 체스판을 가져왔을 때, (0, 0) 위치의 색을 가져와서 번갈아가면서 색을 비교하는 코드를 작성하였다. 하지만, testcase 4번에서 마지막에 W로 색칠되어 있었기 때문에 한 번 덜 색칠하고도 체스판을 다시 칠할 수 있었다. 따라서, (0, 0) 위치의 색을 가져와서 색을 비교하는 방식으로 진행한 것이 아니라 B으로 시작하는 체스판, W로 시작하는 체스판을 이용하여 비교할 수 있도록 하였다. 코드 - Testcase 4번 error 코..
부분집합(Subset) 개념 - 집합에 포함된 원소들을 선택하는 것 - 아무 것도 안 뽑는 것부터 전체 다 뽑는 것까지 조합의 경우를 다 더한 것과 같음 - 부분집합을 이용하여 조합으로 사용하고 싶으면 지금까지 선택한 원소의 개수가 r개가 되면 조합을 구할 수 있음 - 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개 - 순서가 의미가 있으면 순열 / 순서가 의미가 없으면 조합 구현 - 하나의 원소에 대해서 선택, 비선택 하는 과정을 재귀로 진행 - isSelected[cnt] = true : 선택 - Subset(cnt+1) : 다음 원소 (선택에 대한 처리하면서 뒤에 따라오는 모든 경우를 따짐) - isSelected[cnt] = false : 비선택 - Subset(cnt+1) :..