BangBang's Devlogs

programmers.co.kr/learn/courses/30/lessons/12973?language=java

Stack 자료구조를 활용하여 구현하였습니다.

해결 방안

문자열의 문자들을 Stack에 넣어주면서 stack.peek()이 넣으려는 문자와 같으면 pop()해주고 아니면 push()해준다.

다 끝난 후 stack이 비어있으면 성공적으로 수행하였으므로 1, 비어있지 않으면 0을 반환해준다.

코드

import java.util.*;
class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        
        char[] sChar = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        
        for(int i=0; i<s.length(); i++){
            if(!stack.isEmpty() && stack.peek()==sChar[i]){
                stack.pop();
            }
            else{
                stack.push(sChar[i]);    
            }
        }
        
        if(stack.isEmpty())
            answer = 1;
        else
            answer = 0;

        return answer;
    }
}

www.acmicpc.net/problem/15970

문제

각 점에서 색깔이 같은 가장 가까운 점과 연결한 화살표들의 길이 합을 구하는 문제이다.

해결 방안

색깔마다 점의 배열을 만들어서 정렬을 한 뒤 각 점에서 가장 가까운 선(왼쪽 혹은 오른쪽)을 구해서 더해주면 되겠다고 생각하였다.

HashMap을 사용하여 점들의 색깔마다 ArrayList(점의 위치 배열)를 만들어주었다.

그 후 색깔마다 점의 위치 배열을 정렬해주고 각 점에서 가장 가까운 점까지의 화살표 길이를 더해주었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N; // 점들의 갯수
		int x; // 점의 좌표
		int y; // 점의 색깔
		String str = br.readLine();
		N = Integer.parseInt(str);
		
		Map<Integer, ArrayList<Integer>> map = new HashMap<>();
		for(int i=0; i<N; i++) {
			str = br.readLine();
			x = Integer.parseInt(str.split(" ")[0]);
			y = Integer.parseInt(str.split(" ")[1]);
			
			// 색깔별 점의 좌표
			if(map.containsKey(y)) {
				map.get(y).add(x);
			}
			else {
				map.put(y, new ArrayList<Integer>());
				map.get(y).add(x);
			}
		}
		
		int sum = 0;
		Set<Integer> keys = map.keySet();
		// 1~N
		for(int key: keys) {
			ArrayList<Integer> arr = map.get(key);
			Collections.sort(arr);
			
			int distance = 0;
			int l=0;
			int r=0;
			for(int i=0; i<arr.size(); i++) {
				if(i==0) {
					distance = arr.get(i+1)-arr.get(i);
				}
				else if(i==arr.size()-1) {
					distance = arr.get(i)-arr.get(i-1);
				}
				else {
					l = arr.get(i)-arr.get(i-1);
					r = arr.get(i+1)-arr.get(i);
					distance = Math.min(l, r);
				}
				sum += distance;
			}
		}
		System.out.println(sum);
	}

}

www.acmicpc.net/problem/17609

문제

회문인지, 유사 회문(한글자만 삭제하면 회문이 되는 경우)인지, 일반 문자열인지 확인하는 문제이다.

해결 방안

주어진 단어의 첫 부분은 증가시키고 끝 부분은 감소시키면서 비교해온다.
이 때 단어의 변화되는 첫 부분 문자와 끝 부분의 문자가 가운데에 올 때가지 같으면 회문(0)이다.

그렇지 않은 경우 첫 부분을 하나 증가시키거나 끝 부분을 하나 감소시켜서 한 글자를 삭제 시켜서 확인을 해보고 둘 중  하나의 경우라도 회문이면 유사회문(1)이고 둘다 안되면 일반 문자열(2)인 경우이다.

이를 코드로 나타내면 아래와 같다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;

// 회문
// 회문:0 유사회문:1 그외:2
public class Main {

	static int T;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		
		String word = "";
		int result = 0;
		
		for(int i=0; i<T; i++) {
			
			word = br.readLine();
			result = palindrome(word);
			
			System.out.println(result);
		}

	}
	
	public static int palindrome(String word) {
		int result = 0;
		int left = 0, right = word.length()-1;
		
		while(left<=right) {
			
			if(word.charAt(left) == word.charAt(right)) {
				left++;
				right--;
			}
			else {
				int l = left;
				int r = right;
				
				l++;
				while(l<=r) {
					if(word.charAt(l) == word.charAt(r)) {
						l++;
						r--;
					}
					else {
						result++;
						break;
					}
				}
				
				l = left;
				r = right;
				
				r--;
				while(l<=r){
					if(word.charAt(l) == word.charAt(r)) {
						l++;
						r--;
					}
					else {
						result++;
						break;
					}
				}
				
				return result;
			}
		}
		
		return result;
	}

}

www.acmicpc.net/problem/17608

문제

해결 방안

뒤에서부터 확인을 하므로 Stack을 이용하여 구현하였다.

기준 막대기높이(standard)보다 비교하는 막대기높이(current)가 크면 갯수를 하나씩 늘려주고 standard를 current로 바꿔준다.

코드

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

// 막대기
public class Main {

	public static void main(String[] args) throws IOException {

		Stack<Integer> stack = new Stack<>();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		int n = Integer.parseInt(str);
		
		int h=0;
		for(int i=0; i<n; i++) {
			str = br.readLine();
			h = Integer.parseInt(str);
			stack.push(h);
		}
		// ==== 입력 끝
		
		int standard = stack.pop();
		int cnt = 1;
		int current = 0;
		while(!stack.isEmpty()) {
			current = stack.pop();
			if(current > standard) {
				standard = current;
				cnt++;
			}
		}
		
		System.out.println(cnt);
	}

}

www.acmicpc.net/problem/17616

문제

그래프를 만들어야 되는 문제라고 생각은 했으나 어떻게 문제를 접근해야할지 몰라서 다른사람 풀이 참고함

참고 블로그: home-body.tistory.com/646

해결 방안

가능한 가장 높은 등수 U와 가능한 가장 낮은 등수 V를 구하는 문제이다.

크게 보자면 단방향 그래프로 lower_graph와 higher_graph 두개를 이용해서 U와 V를 구해주었다.

lower_graph는 x에서 시작하는 x보다 뒤의 순서들이 나열될 것이다. 따라서 인접 노드의 갯수를 구한뒤 +1을 해주면 가능한 가장 높은 등수 U가 된다.

higher_graph는 x에서 시작하는 x보다 앞의 순서들이 나열될 것이다. 따라서 n에서 인접노드의 갯수를 빼면 가능한 가장 낮은 등수 V가 될것이다. 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

//한국정보올림피아드
//KOI 2019 2차대회 초등부
//등수 찾기
public class Main {

	static int n, m, x;
	static int u, v; // u가 가능한 가장 높은 등수, v가 가능한 가장 낮은 등수
	
	static ArrayList<ArrayList<Integer>> higer_graph;
	static ArrayList<ArrayList<Integer>> lower_graph;
	static boolean[] visited;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine();
		n = Integer.parseInt(str.split(" ")[0]);
		m = Integer.parseInt(str.split(" ")[1]);
		x = Integer.parseInt(str.split(" ")[2]);
		
		higer_graph = new ArrayList<>();
		lower_graph = new ArrayList<>();
		
		
		for(int i=0; i<n+1; i++) {
			higer_graph.add(new ArrayList<Integer>());
			lower_graph.add(new ArrayList<Integer>());
		}
		
		// 단방향 그래프
		int a,b;
		for(int i=0; i<m; i++) {
			str = br.readLine();
			a = Integer.parseInt(str.split(" ")[0]);
			b = Integer.parseInt(str.split(" ")[1]);
			
			higer_graph.get(a).add(b);
			lower_graph.get(b).add(a);
		}
		
		System.out.println((1+bfs(x, lower_graph)) + " " + (n-bfs(x, higer_graph)));
		
	}
	
	public static int bfs(int start, ArrayList<ArrayList<Integer>> graph) {
		visited = new boolean[n+1];
		
		Queue<Integer> q = new LinkedList<>();
		q.offer(start);
		visited[start] = true;
		int result = 0;
		
		int current;
		int y; // 인접노드
		while(!q.isEmpty()) {
			current = q.poll();
			//System.out.print(current + " ");
			
			for(int i=0; i<graph.get(current).size(); i++) {
				y = graph.get(current).get(i);
				
				if(!visited[y]) {
					q.offer(y);
					visited[y] = true;
					result++;
				}
			}
		}
		//System.out.println();
		return result;
	}

}

문제

그리디 문제이다.

해결 방안

처음에 R과 B의 갯수를 각각 세어서 rCnt, bCnt에 저장해준다.

그리디 문제로 볼을 이동하는 4가지 방법 중 최소 이동횟수를 구하면 된다.

1. R공을 모두 왼쪽으로 이동
문제의 그림1을 볼때 RRRRBBBB로 나열하기 위해서는 첫번째 R을 제외하고는 다 옮겨줘야 한다.
따라서 왼쪽에 R이 계속 있을경우 cnt를 세어준다음 Rcnt-cnt는 이동해야하는 R공의 갯수가 된다.
ex) RBBBRBRRR인 경우 첫번째 R이 있으므로 cnt = 1이된다. 따라서 Rcnt(5)-cnt(1)=4가 되고 실제로 왼쪽으로 이동해야하는 R공의 갯수가 된다.

2. R공을 모두 오른쪽으로 이동

3. B공을 모두 왼쪽으로 이동

4. B공을 모두 오른쪽으로 이동

2,3,4번도 뒤에서부터 세야되나 B공을 세야되나에 따라 각각 코드가 조금씩 달라지는거 외에는 같은 원리이다.
자세한 것은 코드를 보면 충분히 이해 가능하다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

// 한국정보올림피아드
// KOI 2019 2차대회 초등부
// 볼 모으기
public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String colors = br.readLine();
		int result = N;
		int rCnt = 0;
		int bCnt = 0;
		
		for(int i=0; i<N; i++) {
			if(colors.charAt(i)=='R') 
				rCnt ++;
			else
				bCnt ++;
		}
		
		int cnt = 0;
		// 4가지 경우
		// 1. R만 움직여서 RRRBBB(R을 다 왼쪽으로)
		for(int i=0; i<N; i++) {
			if(colors.charAt(i)=='R')
				cnt++;
			else
				break;
		}
		result = Math.min(result, rCnt-cnt);
		
		// 2. R만 움직여서 BBBRRR
		cnt = 0;
		for(int i=N-1; i>=0; i--) {
			if(colors.charAt(i)=='R')
				cnt++;
			else
				break;
		}
		
		result = Math.min(result, rCnt-cnt);
		
		// 3. B만 움직여서 BBBRRR
		cnt = 0;
		for(int i=0; i<N; i++) {
			if(colors.charAt(i)=='B')
				cnt++;
			else
				break;
		}
		result = Math.min(result, bCnt-cnt);
		
		// 4. B만 움직여서RRRBBB
		cnt = 0;
		for(int i=N-1; i>=0; i--) {
			if(colors.charAt(i)=='B')
				cnt++;
			else
				break;
		}
		
		result = Math.min(result, bCnt-cnt);
		
		System.out.println(result);
		
	}

}

www.acmicpc.net/problem/17614

문제

 369 규칙에 맞게 1~N까지 나왔을때 N까지 박수의 총 횟수를 출력하는 것이다.

해결 방안

1~N까지 완전 탐색을 해주며 각 수의 자릿수들이 3,6,9인경우 result 변수를 하나씩 증가해주었다.

ex) 13 이면 박수 한번 33이면 박수 두번 가 되야 하므로

코드

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

// 한국정보올림피아드
// KOI 2019 2차대회 초등부
// 369
public class Main {

	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String sN = "";
		int result = 0;
		
		char n;
		for(int i=1; i<=N; i++) {
			sN = Integer.toString(i);
			
			for(int j=0; j<sN.length(); j++) {
				n = sN.charAt(j);
				if(n=='3' || n=='6' || n=='9') {
					result++;
				}
			}
		}
		System.out.println(result);
	}
	
}

programmers.co.kr/learn/courses/30/lessons/67256?language=java

그냥 구현 문제 입니다. 문제에 주어진 조건에 맞춰 풀면 되는 문제이다.

해결 방안

키패드의 위치를 x, y로 생각해주었다.
00~02
..
30~32

1. 일단 문제의 조건4에서 2,5,8,0 숫자 키패드가 나온경우 두 엄지손가락의 현재 키패드 위치에서 더 가까운 엄지 손가락을 사용한다고 하였으므로 왼손, 오른손 엄지의 위치를 저장할 변수를 선언해주었다.(lLoc, rLoc)
(이때, lLoc(왼손 엄지 위치)의 초깃값은 * 키패드의 위치인 {3,0}으로 rLoc(왼손 엄지 위치)의 초깃값은 # 키패드의 위치인 {3,2}로 설정해주었다.)

2. 각 숫자 패드의 위치를 ArrayList<int[]> locList에 저장해주었다. (locList.get(i) 하면 i 키패드의 위치가 나올 수 있게)

3. 조건2, 조건3과 같이 147, 369가 나온경우 각각 왼손 위치, 오른손 위치를 저장해주고 answer에는 L, R을 추가해준다.

4. 조건 4같이 2580이 나온경우 왼, 오른손과의 거리를 구해주고 더 가까운 손을 answer에 추가해준다.
이때 같으면 hand에 영향을 받도록 구현하였다.

(자세한 것은 코드의 주석 참고!)

코드

import java.util.*;
// 키패드 누르기
class Solution {
    
    // 00~02
    // ..
    // 30~32
    static int[] lLoc = {3, 0}; // 왼 엄 위치(*)
    static int[] rLoc = {3, 2}; // 오 엄 위치(#)
    static List<int[]> locList = new ArrayList<>();
    
    public String solution(int[] numbers, String hand) {
        String answer = "";
        
        int x = 0;
        int y = 0;
        // 0~9 키패드 위치 저장
        for(int i=0; i<=9; i++){
            if(i==0) 
                locList.add(new int[]{3,1});
            else{
                locList.add(new int[]{x, y});
                y++;
                if(y % 3 == 0){
                    y = 0;
                    x++;
                }
            }
        }
        
        // 가운데 패드와 왼, 오른 엄지손가락 거리
        int lDistance = 0;
        int rDistance = 0;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<numbers.length; i++){
            // 147
            if(numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7){
                sb.append("L");
                lLoc = locList.get(numbers[i]);
            }
            // 369
            else if(numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9){
                sb.append("R");
                rLoc = locList.get(numbers[i]);
            }
            // 2580
            else{
                // 거리 계산
                lDistance = Math.abs(lLoc[0]-locList.get(numbers[i])[0]) + Math.abs(lLoc[1]-locList.get(numbers[i])[1]);
                rDistance = Math.abs(rLoc[0]-locList.get(numbers[i])[0]) + Math.abs(rLoc[1]-locList.get(numbers[i])[1]);
                
                // 거리가 같으면 손잡이 따라감
                if(lDistance == rDistance){
                    if(hand.equals("right")){
                        sb.append("R");
                        rLoc = locList.get(numbers[i]);
                    }
                    else if(hand.equals("left")){
                        sb.append("L");
                        lLoc = locList.get(numbers[i]);
                    }
                }
                // 왼쪽
                else if(lDistance < rDistance){
                    sb.append("L");
                    lLoc = locList.get(numbers[i]);
                }
                // 오른쪽
                else if(rDistance < lDistance){
                    sb.append("R");
                    rLoc = locList.get(numbers[i]);
                }
            }
            
        }
        answer = new String(sb);
            
        return answer;
    }
}