코테

문제https://www.acmicpc.net/problem/22251 풀이설명이 괜히 어렵게 되어있는거 같은데 대충 정리하면 n자리수의 층을 가진 엘레베이터가 있고 최대층과 현재층이 주어질 때, 현재층에서 다른 층으로 갈 수 있는 방법을 구하는 것이다. 이 때 반전이라는 개념을 사용하고, 그 횟수의 제한을 둔다. 우선 각 수를 배열로 나타내었다. 꺼져있는 부분은 0, 켜져있는 부분은 1로 나타냈고그 이후에는 숫자 변형시 필요 반전 개수를 map 에 저장해뒀다.Map> 형태로 구현하였으며cnt = map.get(1).get(3) 라고 했을때 이는 1에서 3으로 바꿀때 필요 반전 개수가 cnt 개라는 뜻이다. 이렇게 구현한 다음 현재층에서 다른 층으로 이동할 수 있는지를 알아봐야 하는데,최대층이 정해져있기..

문제https://www.acmicpc.net/problem/5397 풀이커서를 이동하고, 중간에 값을 삽입하고, 삭제하고 하는 등의 요건을 살펴보면 이 문제가 연결리스트 문제라는걸 알 수 있다. 구현은 단순하다, LinkedList와 ListIterator 를 선언하고 입력받은 값을 순회하면서 로직을 처리한다. "" 또한 마찬가지이다. "-" 가 나올경우에, 가장 앞을 가리키고 있는지 확인하고 (커서가 가장 앞) , 그게 아니라면 연결리스트에서 값을 삭제하고, iterator 를 한 칸 앞으로 이동시켜준다. 그 외에 일반 문자열은 현재 iterator 가 가리키고 있는 위치에 넣어주면 된다. 코드import java.util.*;import java.io.*;public class Main { p..

문제https://www.acmicpc.net/problem/3055 풀이두 스텝으로 진행하면 된다. 1. 물을 먼저 퍼트린다. 2. 고슴도치가 이동할 수 있는 칸을 보고 이동처리를 한다. ※ 물 퍼트리기 우선 물 퍼트리는건, "*" 기준으로 상하좌우로 범위안에 들면서, 빈칸이어야 한다. (".")이 경우에, 임시 배열을 만들어서 새롭게 퍼지는 칸을 체크하고,마지막에 한번에 원본 배열에 물 값을 세팅해주면 된다. ※ 고슴도치 이동 처리 이거는 bfs 로 하면 되는데, 중요한게 있다.한 단계마다 고슴도치가 이동 할 수 있는 걸 모두 체크해야하기에,bfs 수행시 queue 에 들어가 있는, 같은 스텝의 데이터들을 모두 꺼내서 bfs 를 수행해야한다. 일반적으로는 bfs 는 queue에 있는값을 하나씩 꺼내면..

문제https://www.acmicpc.net/problem/2295 풀이알고보면 참 단순한 문제다. 우리는 x + y + z = k 라는 공식을 활용해서 답을 찾아야 하는데, 이 표현은 x + y = k - z 로도 나타낼 수 있다는 점을 알아야 한다. x + y + z 의 경우의 수를 모두 구할려면 O(N^3) 이 걸릴 테지만  이를 조금 비틀어  x + y = k - z  를 활용하면 양쪽의 식들 값을 구하기 위해서 O(N^2) 의 시간에 풀이할 수 있다. x + y 의 값들을 set 에 저장한다음, k - z 값이 set에 있는지 확인하면 된다. 이 때 k 값이 가장 큰 값을 찾고 있기 때문에 배열을 오름차순으로 정렬해준다음,가장 뒤에서부터 k 값을 세팅해서 탐색을 시작하면 된다. k 값을 큰 값..

문제https://www.acmicpc.net/problem/2493 풀이스택을 활용한 문제이다. 스택을 활용해서 내 기준 왼쪽편에 나보다 큰 건물을 빠르게 찾을 수 있다. 스택에는 [건물번호, 건물높이] 형태로 저장하며, case 1. 스택이 빈 경우에는 -> 앞에 나보다 큰 건물이 없다는 뜻, 0번으로 세팅하고 스택에 현재 건물을 넣어준다. case 2. 스택 값이 건물높이가 나보다 작다면           -> 스택 값이 나보다 클 때까지 빼준다. (스택에 있는 높이가 크다면 내가 찾던 가장 가까운 건물을 의미한다.)           -> 큰 값이 나오면 해당 건물 번호로 세팅해주고, 스택에 현재 건물을 넣어준다. 정리하면 스택에서 현재 건물보다 큰 값이 나올때까지 빼주다가, 큰 값이 나오면 해당..

문제https://www.acmicpc.net/problem/1253 풀이투 포인터를 활용해서 풀어야하는 문제이다. 값을 오름차순 정렬한다음, 가장 앞과 가장 뒤에 포인터를 위치시킨다. 포인터에 위치한 두 값을 더한 값이, 내가 선택한 값보다 크다면 -> 뒤의 포인터를 줄인다.내가 선택한 값보다 작다면 -> 앞의 포인터를 늘린다. 포인터를 이동할 때 선택한 숫자는 선택이 안되야하므로 이 부분은 예외처리 해주면 된다. 코드import java.util.*;import java.io.*;import java.util.stream.Collectors;public class Main { public Integer solution() throws Exception { BufferedReader ..

문제https://www.acmicpc.net/problem/20955 풀이유니온 파인드를 활용해서 쉽게 풀 수 있는 문제이다. 뉴런은 노드, 시냅스는 엣지로 표현한다. 우선 입력으로 들어오는 값들을 연결하되, 사이클이 발생하면 연결을 끊는 과정을 거쳐야하기 때문에 연산횟수에 1을 더해준다. 그렇게 입력값이 다 끝났다면, 그룹을 확인해서 몇번의 연결 연산을 더 해야하는지 계산해주면 된다. 예로 그룹이 3개로 나뉘어져있다면 2번의 연결 연산이 더 필요한것이다. 단 주의해야할점이 union find 를 사용하다보면 내가 속한 부모의 그룹을 가리키고 있기 때문에 그룹의 개수를 구할려면 find 연산으로 계산을 하던가, 아니면 최적화 작업을 거쳐서 그룹번호를 가질 수 있도록 설정해두어야 한다.     코드imp..

문제https://www.acmicpc.net/problem/10799 풀이괄호만 보면 스택먼저 생각나는 만큼, 스택을 활용해서 풀면 된다. 여는 괄호는 현재 막대기의 개수를 의미한다. 그러다가 이제 닫는 괄호가 나오면, 레이저를 의미한다. 이때 스택에서 여는괄호 하나를 꺼내서 닫는 괄호와 쌍을 맞추어 레이저가 구성된다. 그러면 막대들이 절단될것이고, 3개의 막대들이 있다고 가정 하면 3개가 잘려나갈것이다. 단, 앞서 레이저였는데 (닫는 괄호가 나왔는데) 또 닫는 괄호가 나온다면 이는 막대의 끝을 의미한다.막대의 끝을 만나면 1개를 추가해줌으로 레이저로 인해 잘린 오른쪽 값을 체크할 수 있다.   코드import java.util.*;import java.io.*;public class Main { ..

문제https://www.acmicpc.net/problem/2116 풀이  첫번째 주사위는 6면 모두 아랫면으로 향할 수 있기 때문에, 초기 값 기준으로 6번의 반복문을 돌아 경우의 수를 판단한다. 그 외의 주사위는 한칸씩 쌓으면서 아랫면이, 아래 주사위의 윗면과 맞닿으면 된다. 이 때, 새롭게 쌓는 주사위의 아랫면과 윗면을 제외한 4면 중 가장 큰 값을 취하고, 이 과정을 반복하면 된다.  주사위 쌓는 과정을 상세하게 설명하면, 1. 주사위를 쌓을때 아래 주사위의 윗면 값을 현재 주사위의 인덱스 어디에 있는지 찾는다.   (만약 아랫면 주사위의 윗면이 5라고 했을때, 현재 주사위에 5가 어느 위치에 있는지 찾으면 된다.)※ 주사위는 정수형 배열로 인덱스로 위치를 파악할 수 있다.  2. 해당 인덱스와..

문제https://www.acmicpc.net/problem/15662 풀이우선 바퀴는 LinkedList 에 저장함으로 회전이 쉽도록 구성했다. (가장 앞쪽에 있는걸 뒤로하거나, 그 반대로 함에 따라 시계방향, 반시계방향 회전 구현이 가능하다.) 이후 나는 현재 바퀴를 기준으로,  앞쪽에 돌아가야하는 바퀴들을 검사하고 뒤쪽에 돌아가야하는 바퀴들을 검사하는 방식으로 수행했다. 이 때 포인터를 두개둬서, 기준점하고 그 기준점 앞의 바퀴를 가리키도록 했다.그 다음에 극이 같은지 다른지 검사하고, 이 과정을 앞쪽으로 쭉 반복, 뒤쪽으로 쭉 반복하는 식으로 구성했다. 검사 결과에 따라 돌아가야하는 바퀴들은 Map에 방식으로 저장해서 한 번 회전이 끝났을때Map에서 값을 꺼내서 회전을 시키는 방식으로 구성했다...