whiporithm

2295 - 세 수의 합 (Java)

문제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에서 값을 꺼내서 회전을 시키는 방식으로 구성했다...

문제https://www.acmicpc.net/problem/1043 풀이[* 먼저 말하자면 이 문제는 union - find 로 푸는게 정설인 거 같다.] 이 문제의 요점은, 진실을 알고 있는 사람을 통해 건너건너 거짓말쟁이에게 진실이 전해질 수 있다는 점이다. 만약 진실을 알고 있는 사람이 1이라고 가정했을 때, 파티 1 : 1 2파티 2 : 2 3파티 3 : 3 4 이런식으로 이루어져 있을 때 2번이 1번을 통해 진실을 듣게 된다. 다음에 3번은 2번을 통해 들을 수 있고, 4번은 3번을 통해서 들을 수 있다.  (파티의 순서는 상관없다) 따라서 건너건너까지 진실을 알고 있는 사람과의 파티에 엮여있는지 확인할 필요가 있다. 나는 스텝을 나눠서 코드를 구현했다. 1. 우선 진실을 아는 사람들을 저장한..

문제https://www.acmicpc.net/problem/1374  풀이아이디어를 말하자면 pq를 이용하면 된다. 진행중인 강의를 pq에 넣고, 끝나는 순이 빠른 강의를 확인한다. 가장 끝나는 시간이 빠른 강의의 "종료 시간이" 현재 내가 선택한 강의의 "시작시간" 보다 같거나 빠르다면, 해당 강의실을 그대로 사용할 수 있으므로 강의실을 추가할 필요 없다. (이 때 pq에서는 빼줘야 한다.) 그러나 그렇지 않은경우에는 강의실을 추가해야한다. (이 때는 pq에서 빼줄 필요가 없다.) 이 아이디어를 기반으로, 시작시간이 빠른 강의부터 하나씩 확인하고, pq에 넣어주는 방식으로 진행하면 된다.시작시간이 같을 경우에는 종료시간이 빠른 강의순으로 정렬한다. 코드import java.util.*;import j..

문제https://www.acmicpc.net/problem/5567 풀이문제는 단순하다. 나는 맵을 활용해서 풀었다. key 값으로 대상 동창을 넣고, value 로는 Set으로 친구 목록을 추가했다.친구는 양방향 관계니까 반대로도 넣어준다. 그런 다음 상근이(1번)의 친구들을 세어주고,그 친구들의 친구들을 세어주면 끝이다. 값을 넣어줄때 동창별로 친구 목록을 Set에 저장해뒀으니 이를 활용하면 된다. 정답도 Set을 이용해서 중복을 없애면 된다.단, 이럴 경우 상근이가 친구가 0명일때를 제외하고 답에 상근이 카운트도 들어가니,그 부분만 예외처리 해주면 된다. 코드import java.util.*;import java.io.*;public class Main { public void solutio..