본문 바로가기

PS831

백준 14405 자바, 파이썬 - 피카츄 (boj 14405 java, python) 문제 : boj14405 1. 직접 찾아보자! 우선 정규식을 사용하지 않고 직접 찾는걸 확인해보자. 간단히 생각해서, 문자열에서 "pi", "ka", "chu"를 모두 나올 수 없는 문자로 변경해보자! 예를들어 "piakapichu"를 확인해보자. 이제 변경되지 못하고 남는 'a'가 보인다. 따라서 'NO'를 출력하면 된다. '&'만 있었다면 'YES'를 출력하면 된다. 그냥 삭제하지 않고 저렇게 자리를 남겨두는 이유는 'cpihu' 와 같은 경우 때문이다. 이 때 위 처럼 문자를 남긴다면 'c&hu'가 되어 chu를 변경할 수 없지만, 그냥 삭제하면 'chu'가 되므로 변경될 수 있다. 즉 올바른 답을 찾을 수 없다. 위와 같은 방식으로 짠 코드는 '코드1'에서 볼 수 있다. 2. 정규식을 사용해 찾아.. 2022. 3. 29.
백준 5698 자바 - Tautogram (boj 5698 java) 문제 : boj5698 원랜 브론즈는 해설을 작성하지 않으려 했으나, 블로그 유입인원 늘릴려면 아무래도 골플 문제보단 브론즈 문제가 더 이득인 것 같다. 문자열을 잘라내는 방법만 안다면 풀 수 있다. 자바의 경우 String에 대한 split함수 또는 StringTokenizer를 사용해서 자를 수 있는데, 결론적으로 후자가 더 빠르다. 이제 자를수만 있다면, 모든 잘라진 토큰에 대해 첫 character만 확인하면 된다. String에 대해 charAt(0)을 하면 첫 번째 character가 나온다. 이 때 소문자 혹은 대문자로 맞춰서 확인하는 것이 좋을 것이다. 그럼 해당 String에 대해 toLowerCase 후에 charAt(0) 으로 보면 바로 소문자가 나온다. 하지만 당연히 더 느리다. 따.. 2022. 3. 28.
백준 9342 자바 - 염색체 (boj 9342 java) 문제 : boj9342 파싱해서 하려다가, 너무 대놓고 정규 표현식으로 풀어! 라고 하는 문제라서 정규 표현식으로 풀어봤다. ^ : 정규표현식 시작 $ : 정규표현식 끝 [A-F] : A,B,C,D,E,F ? : 0번 또는 1번 + : 그 전 문자가 1개 이상 이다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private static final String REGEX = "^[A-F]?A+F+C+[A-F]?$"; private void solution() throws Exception { BufferedReader br = new BufferedReader(new Input.. 2022. 3. 28.
백준 14381 자바 - 숫자세는 양 (Small) (boj 14381 java) 문제 : boj14381 0부터 9까지의 모든 숫자를 체크하는건 HashSet을 사용하거나(size()가 10이 된다면 모두 찾은 것), 10칸짜리 배열을 사용하면 할 수 있다. 이제 시뮬레이션을 만들면 된다. 어떤 시뮬레이션이냐면, N을 입력받은 후 1N, 2N, 3N, ... 하고 적당히 100N 까지 각 숫자를 만들면서 각 자리수를 HashSet이나 배열에 담는다. 중간에 10개의 숫자가 모두 나왔다면 중지하고, 그렇지 않다면 적당히 큰 수 까지 직접 가보면 된다. 예를들어 다음과 같다. N이 11이었다면 다음과 같은 숫자가 체크될 것이다. 1N = 11 -> 1 2N = 22 -> 2 ... 9N = 99 -> 9 10N = 110 -> 0 최종적으로 10N일 때 10개의 수를 모두 찾았고, 11.. 2022. 3. 27.
백준 16955 자바 - 오목, 이길 수 있을까? (boj 16955 java) 문제 : boj16955 '.'인 곳 중 한 곳을 'X'로 바꾸었을 때, 'X'가 가로, 세로 혹은 대각선으로 연속으로 5개 이상인지 체크해보면 된다. 10x10의 입력값에서 '.'인 곳 모두를 한번씩 'X'로 바꿔보면서 위의 사항을 체크해보면 된다! 대략 O(10x10x5x4) 정도 될 것으로, 매우 널널하다(10x10은 오목판의 크기, 4는 가로 확인, 세로 확인, '↗'형태의 대각선, '↘' 형태의 대각선이다. 5는 대강 5 이상 됬으면 답일테니 5 미만으로만 갈테니 5이다 ㅋㅋ) 이 때 매번 전체 오목판을 모두 확인하면서 5개가 연속인지 확인하면 비효율적이다. 그러니 현재 '.'을 'X'로 변경한 위치부터 다음과 같이 가로, 세로, 대각선을 각각 확인하면 된다. 위의 경우 가로로는 4개, 세로로는.. 2022. 3. 26.
백준 20420 자바 - 화살표 미로 (Normal) (BOJ 20420 JAVA) 문제 : boj20420 매운맛의 BFS 문제였다. BFS에 대해서는 여기에 작성해놨다. 해당 글의 내용만 있으면 풀 수 있는 문제이다. 이 문제를 풀 수 있는 BFS 적용 아이디어를 작성해보겠다. A. BFS 진행 시 인접한 곳은 원래 주어진 방향, 좌측으로 회전해서 갈 수 있는 만큼의 방향(예를들어 남은 L이 2라면 좌측으로 2번까지 돌 수 있다.), 우측으로 회전해서 갈 수 있는 만큼의 방향 이다. B. 좌측으로 4번 혹은 우측으로 4번을 돌면 원래 방향이 되므로 무조건 손해이다. 따라서 좌측으로 3번, 우측으로 3번까지만 확인해야 한다. 이 때, 예를들어 좌측으로 3번이 우측으로 1번과 동일하다고 해서 2번까지만 확인하면 안된다. 남은 횟수가 한쪽이 더 많을 수도 있다. C. 방문체크는 모든 경우.. 2022. 3. 25.
백준 13537 자바 - 수열과 쿼리 1 (BOJ 13537 JAVA) 문제 : boj13537 기본적으로 알고 있어야 하는 알고리즘 기법들이 좀 있어야 이해할 수 있는 풀이 입니다. 모르는 알고리즘이 있다면 별도로 공부하셔야 이해하실 수 있습니다. 결국 통과된 풀이에 쓰인 오프라인 쿼리는 사실 어차피 값이 변경되지 않으므로, 순서를 바꿔서 쿼리를 진행하더라도 원래 위치만 안다면 순서를 바꿔서 답을 구한 후, 원래 위치에 맞게 답만 출력해주면 된다고만 이해하시면 됩니다. 제곱근 분할법은 여기를 참고하시면 될 것 같습니다. 몰라도 사실 유-명한 세그먼트 트리를 사용하면 더 효율적으로 풀 수 있습니다. (제곱근 분할법인 sqrt(N), 세그먼트 트리는 logN) 1. 시간초과 난 풀이방법 '1'은 오답노트 느낌으로 시간초과 난 풀이방법을 적은 것이니, 통과한 풀이를 보고 싶으시.. 2022. 3. 25.
백준 1417 자바 - 국회의원 선거 (BOJ 1417 JAVA) 문제 : boj1417 1. 시뮬레이션을 돌리자! 이 문제를 만족시키기 위해서 어떻게 해야할지부터 생각해보자. 다솜이가 처음 얻은 듣표수를 a라고 하겠다. 그럼 그 나머지 득표수들을 -시키면서, a를 +시켜나갈 때 나머지 득표수 중 가장 큰 득표수보다 a가 커지면 된다. 그렇다면 중요한 요소는 나머지 득표수 중 가장 큰 득표수이다. 이걸 max라 하겠다. 결국 매번 max값을 -1 시키고, a를 +1 시켜나가면 원하는 답을 구할 수 있다. 예를들어 다음의 경우를 보자. 4 1 3 3 4 답을 찾는 과정은 다음과 같다. 매번 max값을 찾고(빨간색으로 나타냈다), 해당 값을 -1 시키고 a를 +1 시킨다. 그러다가 max1) pq.add(Integer.parseInt(br.readLine())); int .. 2022. 3. 24.
백준 17756 자바 - Kieszonkowe (BOJ 17756 JAVA) 문제 : boj17756 우선 NIESTETY 를 출력해야 하는 경우부터 살펴보자. 결국 n개에 대해 가장 큰 짝수를 구해야 하는데, 짝수로 만들 수 없다는 얘기는 n이 1개였고, 그 한개가 홀수인 경우 밖에 없다. 이제 전체 로직을 살펴보자. 짝수를 만들 수 있는 경우를 살펴보면 된다. 우선 짝수+짝수는 당연히 짝수이다. 홀수+홀수도 역시 짝수이다. 따라서 짝수는 그냥 넘어가면 되고, 홀수는 홀수인 것이 짝수개 있다면 짝수로 만드는데 문제가 없다. 이제 문제는 홀수가 홀수개 있는 경우인데, 이 때는 한 개의 수를 제외해야 한다. 당연히 가장 작은 홀수를 제거하는 것이 이득일 것이다. 최종적으로 전체 로직을 살펴보면 다음과 같다. 코드 : github import java.io.BufferedReader.. 2022. 3. 24.
[자바] 프로그래머스 - 체육복 [코딩테스트 연습 Lv1] 문제 : programmers-체육복 1. '여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.' 부분부터 처리해야 한다. lost와 reserve에 동시에 포함되는 항목이 있다면 양쪽에서 제거해서, '2' 이후의 로직에 영향을 끼치면 안된다. 2. +-1인 학생한테 체육복을 빌릴 수 있으므로 무지성으로 lost 기준으로 +-1 학생한테 빌릴 수 있으면 바로 빌리고, reserve에서 제거하면 된다. 뭐 오름차순으로 -1인 학생부터 빌리고 이런 과정이 필요 없다. 만약 +-2 이상으로 빌릴 수 있었다면 누가 누구한테 빌리는지에 따라 빌릴 수 있는 학생의 수가 변경될 것.. 2022. 3. 23.

티스토리툴바