이것저것 개발 블로그

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW8Wj7cqbY0DFAXN 

문제)

풀이)

이 문제는 조합으로 풀면 괜찮게 풀린다.

사실 조합코드를 짜기가 조금... 귀찮아서 어차피 2개만 뽑는 것이니 for문 2개를 이용해서 풀었다.

두 개의 간식을 더하고, 그것이 경계를 넘지 않으면서 최대값을 찾는 과정을 반복한다!

import java.util.Scanner;
//import java.io.FileInputStream;

class Solution_D3_9229_한빈이와SpotMart{
	public static void main(String args[]) throws Exception{
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			int N = sc.nextInt();
			int M = sc.nextInt();
			int[] snack = new int[N];
			for(int i=0; i<N; i++) {
				snack[i]=sc.nextInt();
			}
			
			int answer = 0;
			int temp = 0;
			
			
			for(int i=0; i<N-1; i++) {
				for(int j=i+1; j<N; j++) {
					temp = snack[i]+snack[j];
					if(temp<=M && answer<temp) {
						answer = temp;
					}
				}	 
			}
			
			if(answer == 0) {
				answer = -1;
			}
			
			
			System.out.println("#"+test_case + " " + answer);
			
		}
		sc.close();
	}
}

조합으로 짠 코드!!

시간은 더 오래 걸린다.

import java.util.Scanner;
//import java.io.FileInputStream;

class Solution_D3_9229_한빈이2{
	
	static int[] snack;
	static int N, M, answer;
	static boolean[] v;
	public static void comb(int start, int cnt) {
		if(cnt == 2) {
			cal();
			return;
		}
		
		for(int i=start; i<N; i++) {
			if(v[i])
				continue;
			
			v[i]=true;
			comb(i+1, cnt+1);
			v[i]=false;
			
		}
	}
	
	public static void cal() {
		int sum=0;
		for(int i=0; i<N; i++) {
			if(v[i])
				sum+=snack[i];
		}
		if(sum<=M)
			answer = Math.max(answer, sum);
	}
	
	public static void main(String args[]) throws Exception{
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			N = sc.nextInt();
			M = sc.nextInt();
			snack = new int[N];
			//과자 무게 기록 
			for(int i=0; i<N; i++) {
				snack[i]=sc.nextInt();
			}
			
			v=new boolean[N];
			answer = 0;
			comb(0, 0);
			
			if(answer == 0) {
				answer = -1;
			}
			
			System.out.println("#"+test_case + " " + answer);
			
		}
		sc.close();
	}
}

https://www.acmicpc.net/problem/1158

문제)

풀이)

Queue를 생성하여 모든 원소를 넣어두고,

pop한 후 순서에 맞춰 버릴지 queue에 다시 넣을지 결정한다!

이때, 순서에 맞춰 버리는 애는 순서대로 정답 배열에 저장해두고 후에 출력하면 끝!

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main_BJ_1158_요세푸스문제 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int k = sc.nextInt();
		Queue<Integer> p = new LinkedList<>();
		int[] answer = new int[N];
		for(int i=1; i<=N; i++)
			p.offer(i);
		
		int count=1;
		int index=0;
		while(!p.isEmpty()) {
			if(count % k == 0) {
				answer[index] = p.poll();
				index++;
				count++;
				continue;
			}
			p.offer(p.poll());
			count++;
		}
		System.out.print("<");
		for(int i=0; i<N; i++) {
			if(i!=N-1)
				System.out.print(answer[i] + ", ");
			else
				System.out.print(answer[i]);
		}
		
		System.out.println(">");
		sc.close();
	}

}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14w-rKAHACFAYD 

문제)

풀이)

LinkedList를 이용한다면 간단한 문제이다.

중간에 자주 추가가 이루어져서 linked list를 이용했다.

명령어를 만나고, start부터 end index 까지 삽입하는 방법을 사용했다.

그 후 완성되면 앞에서부터 10개 출력하면 끝!

//import java.io.FileInputStream;
import java.util.LinkedList;
import java.util.Scanner;


public class Solution_D3_1228_암호문1 {

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		for(int test_case = 1; test_case <= 10; test_case++){
			int N = sc.nextInt();
			LinkedList<Integer> key = new LinkedList<>();
			for(int i=0; i<N; i++) {
				key.add(sc.nextInt());
			}

			int cmdNum = sc.nextInt();
			for(int i=0; i<cmdNum; i++) {
				String str = sc.next();
				int start = sc.nextInt();
				int end = sc.nextInt();
				for(int j=start; j<=start+end-1; j++) {
					key.add(j, sc.nextInt());
				}	
			}
			System.out.print("#"+test_case+ " ");
			for(int k=0; k<10; k++) {
				System.out.print(key.get(k) + " ");
			}
			System.out.println();
		}
		sc.close();
	}
}

https://www.acmicpc.net/problem/2493

문제)

풀이)

솔직히 이 문제는 아주 헤맸다. 뭔가 쉬운듯 아닌듯...

뭔가 스택을 쓰면 될 것 같은데.. 하면서 이것저것 하다가 결국 포기하고 다시 보며 노력한 문제!

맨 처음에는 스택이 비어있으므로 stringbuilder인 sb에는 0 추가, stack에 push 한다.

그 이후부터는 탑의 높이를 입력 받으면서 stack의 맨 꼭대기에 존재하는 높이와 비교를 한다.

만약 입력받은 높이가 더 높다면, pop 시키고, 스택의 다음 원소와 비교한다.

이때, 스택 원소의 높이가 더 높을 경우, sb에 해당 원소의 인덱스를 삽입하고, 입력받은 원소는 stack에 push한다.

이를 반복하면 끝!

코드의 이해를 돕기 위해 입력에 따른 stack의 상태를 표현해봤다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main_BJ_2493_탑 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		Stack<int[]> stack = new Stack<>();
		StringBuilder sb = new StringBuilder();
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=n; i++) {
			//새로운 높이 입력받음 
			int Height = Integer.parseInt(st.nextToken());
			//스택에 비교대상이 있는지 
			while(!stack.empty()) {
				//스택의 꼭대기 높이와 새로운 높이 비교 
				if(stack.peek()[1] > Height) {
					//스택 꼭대기 높이가 더 높을 경우 꼭대기 인덱스 추가
					sb.append(stack.peek()[0] + " ");
					break;
				}
				// 새로운 높이가 더 높을 경우 pop 
				stack.pop();
			}//while
			
			//스택이 비어있을 때 
			if(stack.empty()) {
				sb.append("0 ");
			}
			
			// 스택에 인덱스와 높이 넣기 
			stack.push(new int[] {i, Height});
		}//for
		System.out.println(sb);
	}//main

}

처음에 Scanner를 썼는데, 메모리 초과가 나서 bufferedreader와 stringbuilder를 사용했다!

https://www.acmicpc.net/problem/12891

문제)

풀이)

이 문제는 슬라이딩 윈도우를 생각하면 좋다.

슬라이딩 윈도우?!

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘.

배열이나 리스트에서 요소의 일정 범위의 값을 비교할 때 사용할 수 있다!

예를 들어, 다음과 같이 윈도우 크기가 3인 윈도우를 보자.

이때, 이동할 때마다 첫 번째 원소는 윈도우에서 나가고, 나중 원소가 하나씩 들어옴을 확인할 수 있다.

즉, DNA 개수를 매번 다 계산하지 않고, 윈도우를 옮길 때마다 하나씩 추가, 삭제하는 작업을 거치면 된다!

나는 check 배열에 입력으로 주어진 비밀번호가 될 수 있는 AGCT 최소 개수를 저장하고,

sub 배열은 DNA 에서 윈도우만큼 자른 DNA 일부를 나타냈다.

이때, 각 배열의 index 0, 1, 2, 3은 A,G,C,T와 각각 대응한다!

Add 함수로 윈도우가 움직일때마다 추가되는 염기를 더해주고,

Remove 함수로 없어지는 염기를 제거해주었다.

나머지 Check 함수는 비밀번호 조건에 맞는지 확인하는 역할의 함수다.

import java.util.Scanner;

public class Main_BJ_12891_DNA비밀번호 {
	public static int[] check;
	public static int[] sub;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int s = sc.nextInt();
		int p = sc.nextInt();
		String str = sc.next();
		char[] dna = str.toCharArray();
		check = new int[4];
		sub = new int[4];
		for(int i=0; i<4; i++) {	// ACGT
			check[i]=sc.nextInt();
		}
		
		int count=0;
		for(int i=0; i<p; i++) {	//초기 설정
			Add(dna[i]);
		}
		
		if(Check())
			count++;
		
		
		for(int i=p; i<s; i++) {	//다음부터 더하고 빼기 반복
			int j = i-p;
			Add(dna[i]);
			Remove(dna[j]);
			if(Check())
				count++;
		}
		
		
		System.out.println(count);
		sc.close();
		
	}//main

	private static void Add(char c) {
		switch(c) {
		case 'A':
			sub[0]+=1;
			break;
		case 'C':
			sub[1]+=1;
			break;
		case 'G':
			sub[2]+=1;
			break;
		case 'T':
			sub[3]+=1;
			break;
		}
		
	}

	private static void Remove(char c) {
		switch(c) {
		case 'A':
			sub[0]-=1;
			break;
		case 'C':
			sub[1]-=1;
			break;
		case 'G':
			sub[2]-=1;
			break;
		case 'T':
			sub[3]-=1;
			break;
		}
		
	}
	
	private static boolean Check() {
		if(check[0] > sub[0])
			return false;
		else if(check[1]>sub[1])
			return false;
		else if(check[2]>sub[2])
			return false;
		else if(check[3]>sub[3])
			return false;
		return true;
	}
	
}

https://www.acmicpc.net/problem/2164

문제)

풀이)

금방금방 풀 수 있는 문제!

boolean 변수를 이용해 true면 버리고, false면 카드 맨 뒤로 가는 것을 반복했다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main_BJ_2164_카드2 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		Queue<Integer> queue = new LinkedList<>();
		for(int i=1; i<=num; i++) {
			queue.offer(i);
		}
		
		boolean check = true;
		int card = 0;
		while(!queue.isEmpty()) {
			if(check) { // true면 버리기
				card = queue.poll();
				check = false;
			}
			else {	//	false면 뒤로 가기
				card = queue.poll(); 
				queue.offer(card);
				check = true;
			}
		}
		System.out.println(card);
		sc.close();
	}

}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14uWl6AF0CFAYD 

문제)

풀이)

Queue를 알고 있다면 간단한 문제다.

숫자를 큐에서 차례로 뽑으면서 1부터 5까지 빼고 다시 큐에 삽입하는 작업을 한다.

이때, 뺀 수가 0보다 같거나 작을 경우 0을 큐에 삽입한 후 종료한다.

//import java.io.FileInputStream;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution_D3_1225_암호생성기 {

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input2.txt"));
		Scanner sc = new Scanner(System.in);
		for(int test_case = 1; test_case <= 10; test_case++){
			int t = sc.nextInt();
			Queue<Integer> queue = new LinkedList<>();
			for(int i=0; i<8; i++)
				queue.offer(sc.nextInt());
			
			int check = 0;
			int num = 1;
			while(true) {
				int pop_num = queue.poll();
				check = pop_num-num;
				
				if(check <= 0){
					check = 0;
					queue.offer(check);
					break;
				}
				
				queue.offer(check);
				num++;
				if(num == 6)
					num=1;
			}
			
			System.out.print("#"+test_case+" ");
			for(int j=0; j<8; j++) {
				System.out.print(queue.poll() + " ");
			}	
			System.out.println();
		}
		sc.close();
	}
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PzOCKAigDFAUq 

문제)

풀이)

아주 간단한 문제!

N크기도 작아서 for문으로 충분히 해결할 수 있다고 생각했다.

네모칸을 차례대로 움직이면서, 값을 모두 더한 후 비교하는 방식을 이용했는데,

범위만 주의하면 간단하다.

Python 코드

T = int(input())
for test_case in range(1, T + 1):
    n, m = map(int, input().split())
    matrix = []
    for _ in range(n):
        matrix.append(list(map(int, input().split())))

    answer = 0
    for i in range(n-m+1):
        for j in range(n-m+1):
            num = 0
            for row in range(m):
                for col in range(m):
                    num += matrix[row+i][col+j]
            if answer < num:
                answer = num
			           

    print('#{} {}'.format(test_case, answer))

JAVA 코드

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++)
		{
		int N = sc.nextInt();
			int M = sc.nextInt();
			int[][] matrix = new int[N][N];
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					matrix[i][j] = sc.nextInt();
				}
			}
			
			int answer = 0;
			for(int row=0; row<N-M+1; row++) {
				for(int col=0; col<N-M+1; col++) {
					int num=0;
					for(int i=0; i<M; i++) {
						for(int j=0; j<M; j++) {
							num += matrix[row+i][col+j];
						}
					}
					if(answer<num)
						answer=num;
				}
			}
			System.out.println("#"+test_case+" "+answer);

		}
	}
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14eWb6AAkCFAYD 

문제)

풀이)

효율적이지는 않지만 정말 간단하게 생각했다.

짝이 알맞게 다 있다면 [, {, (, < 의 각각의 짝들이 다 있을거니까,

boolean 배열을 이용하여 각 괄호의 짝을 찾아주는 작업을 했다.

내가 푼 코드에 따르면 괄호의 위치와는 상관이 없다.

예를 들어, 코드에서 짝을 찾는 과정은 다음과 같다.

즉, 바깥쪽 <와 바깥쪽 >이 짝이 이루어지지 않는다는 것이다.

문제와의 의도와는 다르지만, 짝이 알맞게 있는지 없는지의 문제이므로 이렇게 풀어도 가능했다.

//import java.io.FileInputStream;
import java.util.Scanner;

public class Solution_D4_1218_괄호짝짓기 {

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		for(int test_case = 1; test_case <= 10; test_case++)
		{
			int n = sc.nextInt();
			char[] arr = new char[n];	//input 배열
			boolean[] bool = new boolean[n];	//false
			String input = sc.next();
			arr = input.toCharArray();
			
			int answer = -1;
			for(int i=0; i<n; i++) {
				if(bool[i]==false) {	//탐색되지 않았으면
					switch(arr[i]) {
					case '{':{
						bool[i] = true;	//탐색
						for(int j=i+1; j<n; j++) {
							if(arr[j] == '}'&&bool[j]==false) {	//짝 찾고, 짝이 안 찾아진 애면
								bool[j]=true;
								break;
							}
						}
					}
						break;
					case '[':{
						bool[i] = true;
						for(int j=i+1; j<n; j++) {
							if(arr[j] == ']'&&bool[j]==false) {
								bool[j]=true;
								break;
							}
						}
					}
						break;
					
					case '<':{
						bool[i] = true;
						for(int j=i+1; j<n; j++) {
							if(arr[j] == '>'&&bool[j]==false) {
								bool[j]=true;
								break;
							}
						}
					}
						break;
					
					case '(':{
						bool[i] = true;
						for(int j=i+1; j<n; j++) {
							if(arr[j] == ')'&&bool[j]==false) {
								bool[j]=true;
								break;
							}
						}
					}
						break;
						
					}//switch
				}//if
			}//for
			for(int i=0; i<n; i++) {
				if(bool[i] == false) {	// 짝 없는애 있으면 0
					answer = 0;
					break;
				}
			}
			if(answer == -1)	//초기값 -1이니 0이 안 되었다는 것은 모두 짝이 있다는 것
				answer = 1;
			System.out.println("#"+test_case+" "+answer);
		}//test_case
		sc.close();
	}//main
}

이 문제의 정석은 stack을 활용하여 문제를 푸는 것이다.

입력값을 탐색하면서 여는 괄호를 만나면 stack에 저장하고, 닫는 괄호를 만나면 저장했던 괄호를 pop하여 잘 매칭되는지 확인한다.

이때, pop한 괄호와 닫는 괄호가 일치하지 않으면 틀렸으므로 0을 출력한다!

이 방식으로 문제를 푼다면 문제에서 원하는 방식으로 괄호 짝을 맞추면서 확인할 수 있다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Solution_D4_1218_괄호짝짓기 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		String opener = "<{([";//스택에 추가할 (시작)문자
		
		for (int tc = 1; tc <= 10; tc++) {
			
			int answer = 1;//기본값 1(유효)
			sb.append("#").append(tc).append(" ");
			
			int N = Integer.parseInt(br.readLine()); //괄호 개수
			String line = br.readLine(); 
			
			Stack<String> stack = new Stack<>(); //stack
			
			for (int i = 0; i < N; i++) {
				String item = line.substring(i, i + 1);  //괄호 하나
				
				if (opener.contains(item)) {//시작괄호 이면
					stack.push(item);
				} else {//끝괄호 이면
					boolean result = false;
					if (!stack.isEmpty()) {// 데이터가 있다면
						String prev = stack.pop();//스택의 끝에 저장된 시작괄호를 prev에 저장
						
						//끝괄호와 시작괄호 매칭 확인
						if (item.equals(">") && prev.equals("<")) {
							result = true;
						} else if (item.equals("]") && prev.equals("[")) {
							result = true;
						} else if (item.equals("}") && prev.equals("{")) {
							result = true;
						} else if (item.equals(")") && prev.equals("(")) {
							result = true;
						}
						
						if (!result) {// 안 맞음
							answer = 0; 
							break;
						}
					}
				}//끝괄호else
			}//for 입력N

			sb.append(answer).append("\n");
		}//tc
		System.out.println(sb);
	}//main
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GLXqKAWYDFAXB 

문제)

풀이)

백준에 나와있는 별찍기 문제와 비슷하게 풀이한다고 생각하면 좋다.

1. 합계를 구해야 하기 때문에 string으로 받은 것을 숫자로 변환하는 방법을 알아야 한다.

str.charAt(index) - '0';

위 코드를 수행한다면 string으로 받은 숫자들 중 index에 해당하는 숫자에 -'0'을 해주게 되어 int type의 숫자가 나온다!

2. 합계를 구하는 방법으로, 

N의 절반을 구한 후, 행 기준 위와 아래쪽을 나눠서 구한다.

이때, 정 가운데부터 차례로 행의 index만큼 늘려서 받으면

문제와 같이 가운데부터 점점 늘어나는 모양으로 더할 수 있다.

import java.util.Scanner;

public class Solution_D3_2805_농작물수확하기 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int N = sc.nextInt();
			int[][] farm = new int[N][N];
			
			
			for(int i=0; i<N; i++) {
				String str = sc.next();
				for(int j=0; j<str.length(); j++) {
                	//숫자 변환
					farm[i][j] = str.charAt(j)-'0';
				}
			}
			
			
			int answer = 0;
            //중간 위쪽
			for(int i=0; i<N/2; i++) {
				for(int j=N/2-i; j<=(N/2+i); j++) {
					answer += farm[i][j];
				}
			}
			
			//중간부터 아래쪽
			for(int i=N/2; i>=0; i--) {
				for(int j=N/2-i; j<=N/2+i; j++) {
					answer += farm[N-i-1][j];
				}
			}
			
			System.out.println("#"+test_case + " " + answer);
		}//test_case
		sc.close();
	}//main
}

이 문제는 절반으로 나누는건 잘했는데 열을 기준으로 절반에서 어떻게 계속 더할지를 헤맸다.

간단하게 규칙을 찾을 수 있었는데ㅠ 연습해야지!