Hello, Freakin world!

www.acmicpc.net/problem/1952 1952번: 달팽이2 M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다. 위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 www.acmicpc.net 달팽이 시리즈 문제입니다. 이전 달팽이 문제에서는 순회할 때 세야하는 칸의 개수를 유지했는데, 이번엔 이차원 boolean 배열을 이용해 방문한 곳을 체크하고 방문하지 않은 곳까지만 방문하는 방식으로 구현해봤습니다. 개인적으로 이 방법이 더 간단한 듯 하네요. import java.io.*; import java.util.ArrayList; import java.util.Arrays; import j..

www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 문제 풀이 2차원 배열을 달팽이 방향으로 순회하면서 숫자를 기입하는 문제입니다. 시계 방향으로 순회하기 때문에 방향은 상,우,하,좌 이렇게 1차원 배열에 넣고 순환시키면 될 것 같습니다. 그리고 이 문제의 경우 한 쪽 방향으로 숫자 개수가 점점 커지기 때문에 이 점도 고려해야 합니다. 찬찬히 살펴보면 어느 방향이든 (한쪽 행, 한쪽 열)이 사이클이 되며 이 때마다 필요한 숫자 개수가 하나씩 늘어납니다. 주의할 점..

www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net 위에서 a값(인턴에 참가하는 남학생 수)를 구할 때, 정수가 아닌 값이 나올 수가 있다. a값은 팀의 수가 최대일 때의 값이므로 이 값에 최대한 가까운 정수값을 써야 한다. 간단하게 이 값을 반올림해주면 된다. (값이 범위를 넘어가는 경우에는 0 또는 k값을 반환하도록 처리해줘야 한다.) 그 다음은 남자, 여자 총원에서 a, k-a를 각각 빼주고 팀을 카운트하면 끝~ import java.io.*; import java.util.ArrayList; import java.util...

www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 풀이를 둘러보니 상태를 저장하는 방법이 꽤 여러 가지였습니다. 각 요소의 값이 모두 1자리기 때문에 문자열이나 그냥 정수로 상태를 표현한 풀이도 가능합니다. 하지만 값이 한 자리를 넘어가는 순간 값들을 분리해야 되기 때문에 다른 방법이 필요할겁니다. 비트마스킹은 입력의 범위가 크지 않다면 일반적인 대안이 될 수 있습니다. 이 문제의 경우 0~9까지의 수를 표현하기 위해 4자리의 비트가 필요합니다. 수를 모두 9개이므로 36비트가 필요하겠네요. 자바 int 자료형은 32비트라서 안되고 lo..

www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 집합 요소를 삭제하는 연산의 구현이 조금 까다로운 면이 있다. 이를 구현하기 위해 모든 집합의 요소를 포함하는 111.. 11와 같이 1로 완전히 채워진 비트를 만들고, 지우려는 요소 위치의 원소를 XOR 연산을 통해 0으로 만들어 준다. 그리고 집합 S와 and 연산을 해주면 해당 요소가 지워진 집합을 얻을 수 있다. import java.io.*; import java.util.ArrayList; import java.util.List; im..

www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 전형적인 구간 트리 문제. 구간 트리를 초기화하는 과정에서 중복되는 과정들이 많아 BiFunction을 이용해 함수를 전달받게 만들어 봤는데, 역시 느리다. 가끔씩 문제들을 풀어오면서 느끼고 있었는데, 자바 Stream, 람다의 경우 연산량이 많이지는 경우 for문에 비해 엄청나게 느리다. 속도가 몇 초씩 차이가 날때가 있기 때문에, PS에서는 조심해서 사용할 것. impo..

import java.io.*; import java.util.*; /* 나이트의 이동 https://www.acmicpc.net/problem/7562 */ public class Main { static int t,n; public static void main(String[] args) throws IOException { //InputReader reader = new InputReader("testcase.txt"); InputReader reader = new InputReader(); t = reader.readInt(); StringBuilder sb = new StringBuilder(); for (int tc = 0; tc < t; tc++) { n = reader.readInt(); ..

www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 백트래킹의 개념을 알고 있다면 풀이 방법을 쉽게 떠올릴 수 있습니다. 위 그림을 보시면 재귀적인 구조를 쉽게 눈치챌 수 있습니다. 재귀 구조를 통해 sum을 구한 다음, 리턴하면서 대소를 비교하며 최대/ 최소를 각각 구해내면 됩니다. 그리고 각 연산자들의 숫자를 백트래킹을 이용해 계산해주면서 연산자 개수 > 0 일 때만 재귀호출 하도록 합니다. 말로 ..

www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이 www.acmicpc.net 핵심은 같은 쉬프트 연산을 어떻게 구현할 것인가에 달려 있습니다. 단순 리스트로 구현해서 인덱스를 추적해가면서 문자열을 조작해 구현할 수도 있겠으나 덱 구조를 이용하면 쉽게 구현이 가능합니다. 풀이 임의의 문자열 S가 있다고 합시다. 문자열을 추가할 때, 커서가 추가된 문자의 뒤에 생성된다고 가정합니다. 초기의 문자열 S는 다른 연산없이 문자를 추가만 한 상태입니다. 각 과정은 S에 대해 차례로 왼쪽, ..

www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모� www.acmicpc.net 문제 풀이 검사 대상 문자열 : S, 폭발 문자열 : C 1. S의 문자열을 차례대로 순회하면서 Stack에 추가한다. 2. 만약 추가한 문자가 C의 마지막 문자열과 같다면 C의 길이만큼 스택을 역탐색해 폭발 문자열인지 검사한다. - 폭발 문자열인 경우, 폭발 문자열의 길이만큼 pop한다. 다시 1번으로 - 아닌 경우 pass. 다시 1번으로 라이브러리에서 주어지는 Stack에는 배열처럼 순회하..