찰떡개발자 코딩

문제 : https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 : 와... 사실 나는 cursor를 따로 만들어 위치를 변경시키면서 진행되는 코드를 짰었다... 다른 사람이 짠 코드에 놀라서 그 코드로 정리해놓으려고 한다. 대단하다 이런생각을...ㅠㅠ Stack을 왼쪽 오른쪽 두가지로 나누어 커서의 위치를 만들어내었다... 이 아이디어로만으로도 코드 구현은 가능하니까..! 여기까지만 설명...! public static void main(Stri..

문제 : https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 풀이 : 처음에는 문제 이해가 되지 않았다... 무슨 말인지 ㅎㅎ; 쉽게 말해 Stack에 들어가는 입력정수들은 1씩 증가하고, push와 pop을 통해 1씩 증가하는 값이 담겨있는 Stack을 활용하여 입력받은 값을 만들수 있느냐는 문제였다. 문제 이해만 한다면 쉽게 풀수 있을것 같다. public sta..

문제 : https://www.acmicpc.net/problem/9093 9093번: 단어 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 www.acmicpc.net 풀이 : StringTokenizer와 StringBuffer를 사용하여 간단하게 풀었다. 매 출력 후 sb 를 신규 instance를 생성해줘 값을 초기화 시켜서 사용했다. 뒤집는건 단어 역순으로 붙여 출력하는 방식을 사용했다. public static void main(String[] args) throws IOException { BufferedReader br = new B..

문제 : https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 풀이 : Arrays.sort를 이용하여 풀어보았다... Comparator를 사용하면 비교가 쉬워지는데, 처음에 2차원 배열을 compare 안해봐서... 조금 당황했지만 그냥 되부렀네...~ public class Main{ public static void main(String[] args) throws NumberFormatEx..

문제 : https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 풀이 : 소인수분해는 어떤건지 다들 아실거라 생각한다. 간단하게 while문만으로 나눠주는 값을 하나씩 증가시키면서 나눠보려고 했는데 시간초과가 떴다... 뭐지...? 해당코드.. public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int i = 2; while(N >= i) { if(N % i == 0) { System.out.println(i); N /= i; } else { i..

오늘은 Quick Sort에 대해 공부해 보려고한다. 이름에서도 보이는 바와 같이 빠른 정렬이다. 퀵 정렬의 메커니즘은 크게 다음과 같다. Sorting할 List를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬 후 , 각 부분리스트에 대해 다시 위의 로직을 재귀적으로 수행하여 정렬하는 방법이다. 쉽게 말해 부분을 나눠서 각각 자기가 맡은 부분을 정렬시킨다고 보면 된다. 로직 순서 1. 피벗을 선택 2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값, 혹은 작은 값을 찾는다. 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다. 3. 양 방향에서 찾은 두 원소를 교환 4. 왼쪽에..

문제 : https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 풀이 : 1+199 = 200 ..1+2+197 = 200 ... 1+2+3+194 = 200 이런식으로 해서 가장 많은 숫자의 합으로 이루어질때를 구하면 된다. 그래서 값을 더할 때마다 count를 증가시켰고, 최종 마지막때는 값이 더 커질수 있으니 그때는 count -1 을 해준다. public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System..

문제 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 : 좌표 문제는 처음 접해봤다... 2차원 배열을 써야되겠는건 알겠는데 쉽지 않았다... 먼저 어떻게 풀어야될지 감이 안잡혔다. 너비 우선탐색 BFS를 생각해보니 Queue를 써야겠구나 싶었다. 방법 1). 우선 익은 토마토의 기준으로 안익은토마토를 익히는걸 중점적으로 생각했다. 그래서 익은 토마토의 위치를 Queue에 담아놓고 익은토마토를 한바퀴돌면서 주변의 안익은..

문제 : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 : DFS 그래프로 풀었다... 전역으로 Cnt 놓고, 순서대로 시작 정점부터 재귀를 통해 Cnt하는 방법으로 풀었다. static int cnt = 0; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

문제 : https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 풀이 : 이 문제는 시간제한이 있는것을 생각안하고, 쉬운문제다 생각하고 2중for문을 사용해서 처음에 풀었다... 안일했다.. 결국 아래 코드로 로직 수정. 처음에는 문제가 이상해보였지만, 결국 결론은 간단하였다. K의 하중을 N개의 로프가 각각 K/N 씩 받는다고한다. ==> 예를 들어보자. 최종 문제에서 제시하는 정보는 선택한 로프 10, 20 , 30, 40 , 50 이 있..