상경한 개발자 지망생들

문제 링크

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

접근 방법

일단 문제 풀이의 전체적인 프로세스는 아래와 같습니다.

 공용 공간의 카드 그리고 개인이 가지고 있는 카드는 HashMap을 사용하여 정보를 저장합니다.

또한 문제를 해결하기 위해 저는 2가지의 Class(구조체)를 정의하였습니다. 

1. Info(int id, String action, int num) -> 카드의 id, (next, acquire, release) 중 한 가지, 자원의 번호

2. UserPlace(HashMap myCards, boolean flag, Info info) -> 개인카드 덱, 수행할 acquire의 존재 유무, 존재한다면 수행해야 할 acquire의 정보

 이 두 가지의 자료구조와 위의 프로세스를 따라간다면 구현할 수 있는 문제였습니다.

자세한 내용은 아래 소스코드에 주석처리 하겠습니다.

소스 코드

import java.*;
import java.util.*;

public class boj21775 {
	
	static int[] turns;
	static ArrayList<Info> infos = new ArrayList<Info>();
	
	public static class Info {
		int id; String action; int num;
		
		public Info(int id, String action, int num) {
			this.id = id;
			this.action = action;
			this.num = num;
		}
	}
	
	public static class UserPlace {
		
		HashMap<Integer, Boolean> myCards;
		boolean flag;
		Info info;
		
		public UserPlace(HashMap myCards, boolean flag, Info info) {
			this.myCards = myCards;
			this.flag = flag;
			this.info = info;
		}
	}
	
	public static void solve(int n, int t) throws Exception {
		
		HashMap<Integer, Boolean> common = new HashMap<Integer, Boolean>(); //공용공간
		ArrayList<UserPlace> Users = new ArrayList<UserPlace>(); //각각의 유저들(idx로 참조)
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		for(int i=0;i<n;i++) 
			Users.add(new UserPlace(new HashMap<Integer, Boolean>(), false, null));
		
		int pointer = 0; //더미 포인터
		
		for(int i=0;i<t;i++) {
			
            // 현재 유저
			UserPlace now = Users.get(turns[i]);
			
            //수행해야 할 acquire가 존재한다면
            if(now.flag) {
				boolean isContain = common.get(now.info.num);
				if(isContain) { //공용 공간에 acquire 자원이 있다면
					common.put(now.info.num, false); //공용공간의 자원 false
					now.myCards.put(now.info.num, true); //개인공간의 자원 true
					now.flag = false; //acquire 해제
				}
				sb.append(now.info.id + "\n");
			} //수행해야 할 acquire가 없다면
			else {
				
                //더미 포인터를 통해 수행해야할 연산을 가져옴
				Info info = infos.get(pointer);
				
				if(info.action.charAt(0) == 'n') //next인 경우
					sb.append(info.id + "\n");
				else if(info.action.charAt(0) == 'r') { //release인 경우
					now.myCards.put(info.num, false); //개인공간의 자원 false
					common.put(info.num, true); //공용공간의 자원 true
					sb.append(info.id + "\n");
				}
				else { //acquire인 경우
                	// 공용공간에 key가 없다는 것은 한 번도 해당 자원을 참조하지 않았다는 뜻
					if(!common.containsKey(info.num)) {
						common.put(info.num, false); //공용공간에 자원을 추가하며 사용불가 false
						now.myCards.put(info.num, true); //개인 공간의 자원 true
					}
					else { // 공용 공간에 자원이 참조된 적이 있을 때
						if(common.get(info.num)) { //공용공간에서 사용가능하다면
							common.put(info.num, false); //공용공간의 자원 false
							now.myCards.put(info.num, true); //개인 공간의 자원 true
							now.flag = false; //acquire flag 해제
						}
						else { //공용공간에서 사용불가능 하다면
							now.flag = true; // 수행해야 할 acquire true
							now.info = info; // 현재의 acquire 정보를 user에 update
						}
					}
					sb.append(info.id + "\n");
				}
                //더미 포인터 증가
				pointer++;
			}
		}
		
		bw.write(sb.toString());
		bw.close();
	}

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str," ");
		
		int n = Integer.parseInt(st.nextToken());
		int t = Integer.parseInt(st.nextToken());
		
		str = br.readLine();
		st = new StringTokenizer(str," ");
		turns = new int[t];
		for(int i=0;i<t;i++) {
			turns[i] = Integer.parseInt(st.nextToken()) - 1; //추 후 index로 참조하기위해 -1
		}
		
		for(int i=0;i<t;i++) {
			str = br.readLine();
			st = new StringTokenizer(str," ");
			int id = Integer.parseInt(st.nextToken());
			String action = st.nextToken();
			int num = 0; //0번 자원은 존재하지 않기 때문에 next인 경우 임시로 0번 자원 저장
			if(action.charAt(0) != 'n')
				num = Integer.parseInt(st.nextToken());
			infos.add(new Info(id, action, num)); 
		}
		br.close();
		
		solve(n, t);	
	}
}

문제 설명

0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다.

• x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다.

예를 들어, x = "11100" 일 때, 여기서 중앙에 있는 "110"을 뽑으면 x = "10" 이 됩니다. 뽑았던 "110"을 x의 맨 앞에 다시 삽입하면 x = "11010" 이 됩니다.

변형시킬 문자열 x가 여러 개 들어있는 문자열 배열 s가 주어졌을 때, 각 문자열에 대해서 위의 행동으로 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ s의 길이 ≤ 1,000,000
• 1 ≤ s의 각 원소 길이 ≤ 1,000,000
• 1 ≤ s의 모든 원소의 길이의 합 ≤ 1,000,000

입출력 예

sresult

입출력 예 설명

입출력 예 #1

• 다음 그림은 "1110"을 "1101"로 만드는 과정을 나타낸 것입니다.

• "1101"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "1101"을 담아야 합니다.
• 다음 그림은 "100111100"을 "100110110"으로 만드는 과정을 나타낸 것입니다.

• "100110110"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "100110110"을 담아야 합니다.
• 그림에 나온 방식 말고도 다른 방법으로 "100110110"을 만들 수 있습니다.
• 다음 그림은 "0111111010"을 "0110110111"로 만드는 과정을 나타낸 것입니다.

• "0110110111"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "0110110111"을 담아야 합니다.
• 그림에 나온 방식 말고도 다른 방법으로 "0110110111"을 만들 수 있습니다.

접근 방법

문제의 풀이를 알아도 신경써야될 부분이 많았던 문제였습니다.

1. 문자열의 앞부터 110이 있는지 탐색

2. 110을 발견한다면 110을 문자열에서 제거하고 그 자리부터 다시 110을 찾아나가며 제거

3. 문자열의 가장 뒤부터 0이 발견되는 곳까지 탐색

4. 0이 발견되었다면 0뒤에 삭제된 110의 갯수만큼 110을 붙힘

1번, 2번 과정은 Stack의 자료구조를 사용해야합니다. 

* 1번 과정에서 IndexOf를 사용할 시 선형의 시간복잡도가 110의 갯수만큼 생기므로 시간초과 발생

* 2번 과정에서 substring 또는 delete를 사용할 시 선형의 시간복잡도가 110의 갯수만큼 생기므로 시간초과 발생

4번 과정에 있어서 string끼리 문자열 연산을 하면 시간초과가 발생합니다.

stringBuilder를 사용하여 string연산의 시간을 줄여줘야 합니다.

소스 코드

import java.util.*;

class Solution {
    
    
    public String solve(String s){
        
        int cnt110 = 0;
        
        Stack<Character> st = new Stack<Character>();
        
        for(int i=0;i<s.length();i++){
            
            st.push(s.charAt(i));
            
            if(st.size() >= 3){
                //시간복잡도를 조금이라도 줄이고자 3개를 순차적으로 꺼내며 검사
                char first = st.pop();
                if(first != '0'){
                    st.push(first);
                    continue;
                }
                char second = st.pop();
                if(second != '1'){
                    st.push(second);
                    st.push(first);
                    continue;
                }
                char third = st.pop();
                if(third != '1'){
                    st.push(third);
                    st.push(second);
                    st.push(first);
                    continue;
                }
                cnt110++;
            }
        }
        
        //string으로 +연산시 시간초과 발생
        StringBuilder sb = new StringBuilder();
        int pos = st.size();
        boolean flag = false;
        
        //0을 발견할때까지 idx조정
        while(!st.isEmpty()){
            char pop = st.pop();
            if(!flag && pop == '1') pos--;
            if(pop == '0') flag = true;
            sb.insert(0, pop);
        }
        
        //110의 갯수만큼 110을 idx자리에 붙힘
        String fix = "";
        for(int i=0;i<cnt110;i++)
            sb.insert(pos, "110");
    
        return sb.toString();
    }
    
    public String[] solution(String[] s) {
        
        String[] answer = {};
        answer = new String[s.length];
        
        //1케이스씩 해결
        for(int i=0;i<s.length;i++)
            answer[i] = solve(s[i]);
        
        return answer;
    }
}

문제 설명

과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 1번부터 N번까지 차례로 번호가 붙은 바구니 N개가 일렬로 나열해 놨습니다.

철수는 두 아들에게 줄 과자를 사려합니다. 첫째 아들에게는 l번 바구니부터 m번 바구니까지, 둘째 아들에게는 m+1번 바구니부터 r번 바구니까지를 주려합니다. 단, 두 아들이 받을 과자 수는 같아야 합니다(1 <= l <= m, m+1 <= r <= N). 즉, A[i] 를 i번 바구니에 들어있는 과자 수라고 했을 때, A[l]+..+A[m] = A[m+1]+..+A[r] 를 만족해야 합니다.

각 바구니 안에 들은 과자 수가 차례로 들은 배열 cookie가 주어질 때, 조건에 맞게 과자를 살 경우 한 명의 아들에게 줄 수 있는 가장 많은 과자 수를 return 하는 solution 함수를 완성해주세요. (단, 조건에 맞게 과자를 구매할 수 없다면 0을 return 합니다)

제한사항

• cookie의 길이는 1 이상 2,000 이하입니다.
• cookie의 각각의 원소는 1 이상 500 이하인 자연수입니다.

입출력 예

cookieresult

입출력 예 설명

입출력 예 #1

첫째 아들에게 2, 3번 바구니를, 둘째 아들에게 4번 바구니를 사주면 두 아들은 각각 과자 3개를 받습니다.

입출력 예 #2

주어진 조건에 맞게 과자를 살 방법이 없습니다.

접근 방법

 문제를 읽고 부분합과 동적계획법을 사용한 풀이가 떠올랐으나 효율성을 통과하지 못했습니다. 하지만 투포인터를 사용하여 간단하게 해결할 수 있었습니다. 

1. mid가 고정된 상태에서 left와 right를 mid로 부터 1칸씩 멀어지게 적절히 조정합니다. 

(left와 right를 한 칸씩 조정하면서 합을 구할 수 있기 때문에 prefix sum은 필요없습니다.)

2. leftSum과 rightSum이 같아질 경우 answer를 최대값으로 갱신합니다.

(leftSum은 left ~ mid의 합, rightSum은 mid + 1 ~ right의 합)

3. leftSum이 더욱 클 경우 right를 mid로 부터 1칸 멀어지게 하고, rightSum이 더욱 클 경우 left를 mid로 부터 1칸 멀어지게 합니다. 

4. mid를 0~cookie.length까지 움직이며 1,2,3을 반복합니다.

그림으로 설명하면 아래와 같습니다.

소스 코드

class Solution {
    public int solution(int[] cookie) {
        
        int answer = 0;
        
        //4번 과정
        for(int mid = 0;mid<cookie.length - 1;mid++){
            
            int left = mid;
            int right = mid + 1;
            int lSum = cookie[mid];
            int rSum = cookie[mid+1];
            
            while(true){
                
                //2번 과정
                if(lSum == rSum){
                    answer = Math.max(answer, rSum);
                    if(++right < cookie.length) rSum += cookie[right];
                    else break;
                }
                else if(lSum > rSum){ //3번 과정
                    if(++right < cookie.length) rSum += cookie[right];
                    else break;
                }
                else{ //3번 과정
                    if(--left >= 0) lSum += cookie[left];
                    else break;
                }
            }
        }
        return answer;
    }
}

문제 설명

단어 퍼즐은 주어진 단어 조각들을 이용해서 주어진 문장을 완성하는 퍼즐입니다. 이때, 주어진 각 단어 조각들은 각각 무한개씩 있다고 가정합니다. 예를 들어 주어진 단어 조각이 [“ba”, “na”, “n”, “a”]인 경우 "ba", "na", "n", "a" 단어 조각이 각각 무한개씩 있습니다. 이때, 만들어야 하는 문장이 “banana”라면 “ba”, “na”, “n”, “a”의 4개를 사용하여 문장을 완성할 수 있지만, “ba”, “na”, “na”의 3개만을 사용해도 “banana”를 완성할 수 있습니다. 사용 가능한 단어 조각들을 담고 있는 배열 strs와 완성해야 하는 문자열 t가 매개변수로 주어질 때, 주어진 문장을 완성하기 위해 사용해야 하는 단어조각 개수의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 만약 주어진 문장을 완성하는 것이 불가능하면 -1을 return 하세요.

제한사항

• strs는 사용 가능한 단어 조각들이 들어있는 배열로, 길이는 1 이상 100 이하입니다.
• strs의 각 원소는 사용 가능한 단어조각들이 중복 없이 들어있습니다.
• 사용 가능한 단어 조각들은 문자열 형태이며, 모든 단어 조각의 길이는 1 이상 5 이하입니다.
• t는 완성해야 하는 문자열이며 길이는 1 이상 20,000 이하입니다.
• 모든 문자열은 알파벳 소문자로만 이루어져 있습니다.

입출력 예

strstresult

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
"ap" 1개, "ple" 1개의 총 2개로 "apple"을 만들 수 있으므로 필요한 단어 개수의 최솟값은 2를 return 합니다.

입출력 예 #3
주어진 단어로는 "banana"를 만들 수 없으므로 -1을 return 합니다.

접근 방법

단어의 0번째 문자부터 끝까지 최소한의 갯수로 만들어 나가는 dp테이블을 채워가며 해결 할 수 있는 문제입니다.

예를들어

[b][a][n][a][n][a]가 있다면

[b]를 최소한으로 만들 수 있는 횟수

[ba]를 최소한으로 만들 수 있는 횟수

[ban]를 최소한으로 만들 수 있는 횟수

.........

[banana]를 최소한으로 만들 수 있는 횟수를 채워가면 됩니다.

저와 같은 경우는 Top Down방식을 사용하였고

dp[i] = (i번째부터 단어의 마지막까지 문자열을 만드는 최소 횟수)를 의미합니다.

단어를 만들어감에 있어서 길이가 긴 단어를 우선적으로 채워 만드는 것이 유리합니다.

strs[]를 긴 단어부터 정렬을 한 뒤, for문으로 탐색을 하였습니다.

자세한 내용은 소스 코드에 주석 처리하겠습니다.

소스 코드

class Solution {
    
    String t;
    String[] strs;
    int dp[];
    
    //문자열의 길이 순 정렬
    Comparator<String> c = new Comparator<String>() { 
        public int compare(String s1, String s2) { 
            return Integer.compare(s2.length(), s1.length()); 
        } 
    };
    
    public int solve(int idx){
        
        //dp[i]는 i~마지막 문자열을 채울 수 있는 최소 횟수를 의미
        
        //더 이상 진행 불가능
        if(idx == t.length())
            return 0;
        if(dp[idx] != -1)
            return dp[idx];
        
        // 최소값을 찾아야 하므로 충분히 큰 값으로 초기화
        dp[idx] = 20001;
        for(int i=0;i<strs.length;i++){
            
            // (현재까지 만들어진 문자열의 길이 + 새로운 퍼즐의 크기)가
            // 단어의 길이보다 짧아야 함
            if(idx + strs[i].length() <= t.length()){
                boolean flag = true;
                // substring으로 잘라서 문자열을 비교할경우 시간초과가 납니다. ㅠㅠ
                // 채워나갈 수 있는 단어인지 검사
                for(int j = 0; j < strs[i].length(); j++) {
                    if(t.charAt(idx + j) != strs[i].charAt(j)) {
                        flag = false;
                        break;
                    }
                }
                if(flag) 
                    dp[idx] = Math.min(dp[idx], solve(idx + strs[i].length()) + 1);
            }
        }
        return dp[idx];
    }
    
    public int solution(String[] strs, String t) {
        
        dp = new int[t.length()];
        Arrays.fill(dp, -1);
        Arrays.sort(strs, c);
        this.strs = strs; this.t = t;
        
        int answer = solve(0);
        return answer = (answer <= 20000) ? answer : -1;
    }
}

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

오지 탐험가인 프로도는 탐험 도중 n개의 방으로 이루어진 지하 동굴을 탐험하게 되었습니다. 모든 방에는 0부터 n - 1 까지 번호가 붙어있고, 이 동굴에 들어갈 수 있는 유일한 입구는 0번 방과 연결되어 있습니다. 각 방들은 양방향으로 통행이 가능한 통로로 서로 연결되어 있는데, 서로 다른 두 방을 직접 연결하는 통로는 오직 하나입니다. 임의의 서로 다른 두 방 사이의 최단경로는 딱 한 가지만 있으며, 또한 임의의 두 방 사이에 이동이 불가능한 경우는 없습니다.

탐험에 앞서 이 지하 동굴의 지도를 손에 넣은 프로도는 다음과 같이 탐험 계획을 세웠습니다.

1. 모든 방을 적어도 한 번은 방문해야 합니다.
2. 특정 방은 방문하기 전에 반드시 먼저 방문할 방이 정해져 있습니다.
   2-1. 이는 A번 방은 방문하기 전에 반드시 B번 방을 먼저 방문해야 한다는 의미입니다.
   2-2. 어떤 방을 방문하기 위해 반드시 먼저 방문해야 하는 방은 없거나 또는 1개 입니다.
   2-3. 서로 다른 두 개 이상의 방에 대해 먼저 방문해야 하는 방이 같은 경우는 없습니다.
   2-4. 어떤 방이 먼저 방문해야 하는 방이면서 동시에 나중에 방문해야 되는 방인 경우는 없습니다.

위 계획 중 2-2, 2-3, 2-4는 순서를 지켜 방문해야 하는 두 방의 쌍이 A → B(A를 먼저 방문하고 B를 방문함) 형태로 유일함을 의미합니다. 즉, 프로도는 아래와 같은 형태로 방문순서가 잡히지 않도록 방문 계획을 세웠습니다.

• A → B, A → C (방문순서 배열 order = [...,[A,B],...,[A,C],...]) 형태로 A를 방문 후에 방문해야 할 방이 B와 C로 두 개 또는 그 이상인 경우
• X → A, Z → A (방문순서 배열 order = [...,[X,A],...,[Z,A],...]) 형태로 A를 방문하기 전에 방문해야 할 방이 X와 Z로 두 개 또는 그 이상인 경우
• A → B → C (방문순서 배열 order = [...,[A,B],...,[B,C],...) 형태로 B처럼 A 방문 후이면서 동시에 C 방문 전인 경우

그리고 먼저 방문해야 할 방과 나중에 방문할 방을 반드시 연속해서 방문해야 할 필요는 없어 A방을 방문한 후 다른 방을 방문한 후 B방을 방문해도 좋습니다.

방 개수 n, 동굴의 각 통로들이 연결하는 두 방의 번호가 담긴 2차원 배열 path, 프로도가 정한 방문 순서가 담긴 2차원 배열 order가 매개변수로 주어질 때, 프로도가 규칙에 맞게 모든 방을 탐험할 수 있을 지 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• n은 2 이상 200,000 이하입니다.
• path 배열의 세로(행) 길이는 n - 1 입니다.
  • path 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다.
  • 두 방 A, B사이를 연결하는 통로를 나타냅니다.
  • 통로가 연결하는 두 방 번호가 순서없이 들어있음에 주의하세요.
• order 배열의 세로(행) 길이는 1 이상 (n / 2) 이하입니다.
  • order 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다.
  • A번 방을 먼저 방문한 후 B번 방을 방문해야 함을 나타냅니다.

입출력 예

npathorderresult

입출력 예에 대한 설명

접근 방법

 결론부터 이야기하자면 DFS를 사용하여 구현하였습니다. 효율성 10번 테스트케이스에서 런타임에러가 발생하는데 Java 환경에서는 BFS를 사용해야만 통과할 수 있을 거 같습니다. C++의 경우 DFS를 사용해도 무난히 통과할 수 있습니다.

이런 유형의 문제는 처음이여서 다른 사람들의 풀이를 참조하였습니다.

*order에서 [A -> B]가 존재한다고 할 때 A를 B의 사전노드, B를 A의 사후노드라고 표현하겠습니다.

1. 현재 방문하고자 하는 노드가 사전 노드를 가지고 있는지 확인합니다.

2. 사전 노드가 방문이 된 상태라면 DFS를 계속 진행합니다.

3. 사전 노드가 방문이 되지 않은 상태라면 현재 노드와 사전 노드를 reserve에 기록하고 DFS진행을 멈춥니다.

4. 이후 현재노드가 reserve에 기록되어 있다면, 즉시 사후노드부터 DFS를 진행시킵니다.

자세한 내용은 소스코드에 주석처리 하겠습니다.

소스 코드

import java.util.*;

class Solution {
    
    ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>>(); //인접 리스트
    HashMap<Integer, Integer> before = new HashMap<Integer, Integer>(); //(사후노드, 사전노드)
    HashMap<Integer, Integer> reserve = new HashMap<Integer, Integer>(); //(사전노드, 사후노드)
    boolean visited[] = new boolean[200000];
    int cnt = 0; //노드의 방문 횟수
    
    public void init(int n, int[][] path, int[][] order){
        
        for(int i=0;i<n;i++)
            tree.add(new ArrayList<Integer>());
        for(int i=0;i<order.length;i++)
            before.put(order[i][1], order[i][0]);
        
        for(int i=0;i<path.length;i++){
            tree.get(path[i][0]).add(path[i][1]);
            tree.get(path[i][1]).add(path[i][0]);
        }    
    }
    
    public void DFS(int now){
        
        //사전노드를 가지고 있는지 검사
        if(before.get(now) != null){
        	//사전 노드가 방문된 상태가 아니라면 기록 후 진행을 멈춤
            if(!visited[before.get(now)]){
                reserve.put(before.get(now), now);
                return;
            }
        }
        
        visited[now] = true;
        ++cnt; //노드의 방문 횟수
        
        //만약 사후노드가 방문되었다면 사전 노드부터 탐색
        if(reserve.get(now) != null)
            DFS(reserve.get(now));
        
        //인접한 노드들로 DFS진행
        for(int i=0;i<tree.get(now).size();i++){
            int next = tree.get(now).get(i);
            if(!visited[next])
                DFS(next);
        }
        return;
    }
    
    public boolean solution(int n, int[][] path, int[][] order) {
        boolean answer = true;
        init(n, path, order); DFS(0);
        //모든 노드를 방문했다면 true, 아니면 false
        return answer = (cnt == n) ? true : false;
    }
}

문제 설명

사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다.

• ((1 - 5) - 3) = -7
• (1 - (5 - 3)) = -1

위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다.
또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다.

• (((1 - 3) + 5) - 8) = -5
• ((1 - (3 + 5)) - 8) = -15
• (1 - ((3 + 5) - 8)) = 1
• (1 - (3 + (5 - 8))) = 1
• ((1 - 3) + (5 - 8)) = -5

위와 같이 서로 다른 연산 순서의 계산 결과는 [-15, -5, -5, 1, 1]이 되며, 이중 최댓값은 1입니다.
문자열 형태의 숫자와, 더하기 기호("+"), 뺄셈 기호("-")가 들어있는 배열 arr가 매개변수로 주어질 때, 서로 다른 연산순서의 계산 결과 중 최댓값을 return 하도록 solution 함수를 완성해 주세요.

제한 사항

• arr는 두 연산자 "+", "-" 와 숫자가 들어있는 배열이며, 길이는 3 이상 201 이하 입니다.
  • arr의 길이는 항상 홀수입니다.
  • arr에 들어있는 숫자의 개수는 2개 이상 101개 이하이며, 연산자의 개수는 (숫자의 개수) -1 입니다.
  • 숫자는 1 이상 1,000 이하의 자연수가 문자열 형태로 들어있습니다.. (ex : "456")
• 배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있습니다.

입출력 예

arrresult

입출력 예시

입출력 예 #1
위의 예시와 같이 (1-(3+(5-8))) = 1 입니다.

입출력 예 #2
(5-(3+((1+2)-4))) = 3 입니다.

접근 방법

개인적으로 굉장히 재미있게 풀었던 문제입니다. 

문제를 해결하기 위해서는 부분문제를 해결하며 전체의 최적해를 찾아가는 동적 계획법을 사용할 수 있습니다.

1. [A1 ~ An] + [B1 ~ Bn] 의 최대값을 구하기 위해서는 [A1 ~ An]이 최대가 되어야하고 [B1 ~ Bn]이 최대가 되어야 할 것입니다. 

2. [A1 ~ An] - [B1 ~ Bn] 의 최대값을 구하기 위해서는 [A1 ~ An]이 최대가 되어야하고 [B1 ~ Bn]이 최소가 되어야 할 것입니다. 

3. [A1 ~ An] = [A1 ~ Ax] + [Ax+1 ~ An]또는 [A1 ~ Ax] - [Ax+1 ~ An] 표현할 수 있습니다. 즉 부분 문제부터 해결하며 최적해를 구합니다. 이 때 중복되는 연산을 없애기 위해 dp테이블을 구성합니다.

4. dp테이블은 3차원으로 구성할 수 있습니다.

dp[최대 or 최소][범위의 시작][범위의 끝] = 범위의 최대 혹은 최소 값

dp테이블의 1차원은 0또는 1로써 최대값을 저장하는 테이블인지 최소값을 저장하는 테이블인지 지정하며 그에 따른 값을 dp테이블에 기록합니다.

ex1) dp[0][3][7] -> 3번째 숫자부터 7번째 숫자까지의 최대값

ex2) dp[1][2][7] -> 2번째 숫자부터 7번째 숫자까지의 최소값

자세한 내용은 아래 소스코드에 주석처리 하였습니다.

소스 코드

class Solution {
    
    //dp의 1차원의 0은 최대 테이블, 1은 최소테이블
    int dp[][][] = new int[2][200][200]; 
    char oper[]; int nums[]; //oper는 연산자를 기록, nums는 숫자를 기록
    String arr[];
    int tmp = 987654321;
    
    //dp테이블 초기화
    public void init(){
        
        int n = arr.length/2;
        
        for(int i=0;i<n+1;i++)
            for(int j=0;j<n+1;j++){
                dp[0][i][j] = -1 * tmp;
                dp[1][i][j] = tmp;            
            }
            
        nums = new int[n + 1];
        oper = new char[n];
        
        //arr의 짝수 idx는 숫자가 기록, 홀수 idx에는 연산자가 기록되어 있음
        for(int i=0;i<arr.length;i++){
            if(i%2 == 0) nums[i/2] = Integer.parseInt(arr[i]);
            else oper[i/2] = arr[i].charAt(0);
        }
    }
    
    //flag == 0이면 최대, 1이면 최소
    public int solve(int flag, int start, int end){
        
        // 범위가 숫자 하나로 일치하는 경우
        if(start == end)
            return dp[flag][start][end] = nums[start];
        
        //이미 해결했던 문제라면
        if(flag == 0 && dp[flag][start][end] != -1*tmp)
            return dp[flag][start][end];
        if(flag == 1 && dp[flag][start][end] != tmp)
            return dp[flag][start][end];
        
        // flag에 따라 초기값을 다르게 줌
        int ret = (flag == 0) ? -1 * tmp : tmp;
        // 방문 체크
        dp[flag][start][end] = 0;
        
        if(flag == 0){
        //최대를 구해야 하는 경우
            for(int mid = start; mid < end; mid++){
                if(oper[mid] == '-') //두 구간 사이의 연산자가 "-"일때, 최대 - 최소
                    ret = Math.max(ret, solve(0, start, mid) - solve(1, mid+1, end));        
                else //두 구간 사이의 연산자가 "+"일때, 최대 + 최대
                    ret = Math.max(ret, solve(0, start, mid) + solve(0, mid+1, end));
            }    
        }
        else{
        //최소를 구해야 하는 경우
            for(int mid = start; mid < end; mid++){
                if(oper[mid] == '-') //두 구간 사이의 연산자가 "-"일때, 최소 - 최대
                    ret = Math.min(ret, solve(1, start, mid) - solve(0, mid+1, end));        
                else //두 구간 사이의 연산자가 "+"일때, 최소 + 최소
                    ret = Math.min(ret, solve(1, start, mid) + solve(1, mid+1, end));
            }
        }
        return dp[flag][start][end] = ret;
    }
    
    public int solution(String arr[]) {
        int answer = -1;
        this.arr = arr;
        init();
        // solve(처음부터 마지막의 최대값), flag = 0, start = 0, end = 마지막 idx
        return answer = solve(0, 0, arr.length/2);
    }
}

문제 설명

각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다.

• 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한쪽은 1 감소시킵니다.

하지만, 모든 트리가 위의 행동을 통하여 모든 점들의 가중치를 0으로 만들 수 있는 것은 아닙니다. 당신은 주어진 트리에 대해서 해당 사항이 가능한지 판별하고, 만약 가능하다면 최소한의 행동을 통하여 모든 점들의 가중치를 0으로 만들고자 합니다.

트리의 각 점의 가중치를 의미하는 1차원 정수 배열 a와 트리의 간선 정보를 의미하는 edges가 매개변수로 주어집니다. 주어진 행동을 통해 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가능한지를 찾아 return 하도록 solution 함수를 완성해주세요. (만약 처음부터 트리의 모든 정점의 가중치가 0이라면, 0을 return 해야 합니다.)

제한사항

• a의 길이는 2 이상 300,000 이하입니다.
  • a의 모든 수는 각각 -1,000,000 이상 1,000,000 이하입니다.
  • a[i]는 i번 정점의 가중치를 의미합니다.
• edges의 행의 개수는 (a의 길이 - 1)입니다.
  • edges의 각 행은 [u, v] 2개의 정수로 이루어져 있으며, 이는 u번 정점과 v번 정점이 간선으로 연결되어 있음을 의미합니다.
  • edges가 나타내는 그래프는 항상 트리로 주어집니다.

입출력 예

aedgesresult

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 트리의 모든 정점의 가중치를 0으로 만드는 과정을 나타낸 것입니다.

1. 2번 정점과 3번 정점을 선택하여 2번 정점은 1 감소시키고, 3번 정점은 1 증가시킵니다. (2번 반복)
2. 3번 정점과 4번 정점을 선택하여 4번 정점은 1 감소시키고, 3번 정점은 1 증가시킵니다. (2번 반복)
3. 0번 정점과 3번 정점을 선택하여 3번 정점은 1 감소시키고, 0번 정점은 1 증가시킵니다. (5번 반복)

• 모든 정점의 가중치를 0으로 만드는 데 필요한 최소 행동 횟수는 9번이므로, 9를 return 해야 합니다.

입출력 예 #2

• 주어진 트리는 모든 정점의 가중치를 0으로 만드는 것이 불가능하므로, -1을 return 해야 합니다.

접근 방법

1. 가장 먼저 확인해야할 부분은 모두 0으로 만들 수 있는지 아닌지 입니다.

 모든 노드의 가중치의 합이 0이라면 모두 0으로 만드는 것이 가능하고, 반대의 경우는 모든 가중치를 0으로 만드는 것이 불가능합니다.

2. 어떻게 해야 최소의 횟수로 모든 가중치를 0으로 만들 수 있을까? 

 가장 최소의 횟수로 모든 가중치를 0으로 만드려면 반복되는 연산(가중치 교환)과정이 있어서는 안됩니다. 즉 일방향으로 연산을 적용한다면 노드의 어떤 부분부터 시작하더라도 모두 같은 최솟값을 구할 수 있습니다. 

 노드의 연결 정보는 무조건 트리의 형태로 주어진다는 것을 알 수 있습니다. 즉 어떤 임의의 노드를 루트로 잡고 DFS를 사용하여 자식의 방향으로 향하게 설계 후, 리프(말단)노드로부터 부모 노드의 방향으로 연산을 적용하여 해결할 수 있습니다.

소스 코드

import java.util.*;

class Solution {
    
    ArrayList<ArrayList<Integer>> info;
    boolean[] visited;
    long[] a;
    long cnt = 0;
    
    void solve(int now){
        
        //부모노드로 올라가지 못하게 방문노드 check
        visited[now] = true;
        
        for(int i=0;i<info.get(now).size();i++){
            int next = info.get(now).get(i);
            if(visited[next] == false){
                solve(next);
                a[now] += a[next];
            }
        }
        //cnt는 연산이 일어나는 횟수
        cnt += Math.abs(a[now]);
    }
    
    
    void makeInfo(int[][] edges){
        
        info = new ArrayList<ArrayList<Integer>>();
        
        for(int i=0;i<this.a.length;i++)
            info.add(new ArrayList<Integer>());
        
        for(int i=0;i<edges.length;i++){
            info.get(edges[i][0]).add(edges[i][1]);
            info.get(edges[i][1]).add(edges[i][0]);
        }
    }
    
    public long solution(int[] a, int[][] edges) {
        
        long sum = 0;
        
        this.a = new long[a.length];
        this.visited = new boolean[a.length];
        
        for(int i=0;i<a.length;i++){
            this.a[i] = a[i];
            sum += this.a[i];
        }
        //합이 0이 아니라면 가중치를 0으로 만들 수 없음
        if(sum != 0)
            return -1;
        
        //인접리스트로 표현
        makeInfo(edges);
        
        solve(0);
        return cnt;
    }
}

문제 설명

N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다.

예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g 기지국이 전파 도달 거리가 1인 5g 기지국으로 바뀔 경우 모든 아파트에 전파를 전달할 수 없습니다. (전파의 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.)

• 초기에, 1, 2, 6, 7, 8, 9번째 아파트에는 전파가 전달되지 않습니다.

• 1, 7, 9번째 아파트 옥상에 기지국을 설치할 경우, 모든 아파트에 전파를 전달할 수 있습니다.

• 3개의 아파트보다 더 많은 아파트 옥상에 기지국을 설치할 경우에도 모든 아파트에 전파를 전달할 수 있습니다.

이때, 우리는 기지국을 최소로 설치하면서 모든 아파트에 전파를 전달하려고 합니다. 위의 예시에선 최소 3개의 아파트 옥상에 기지국을 설치해야 모든 아파트에 전파를 전달할 수 있습니다.

아파트의 개수 N, 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열 stations, 전파의 도달 거리 W가 매개변수로 주어질 때, 모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값을 리턴하는 solution 함수를 완성해주세요

제한사항

• N: 200,000,000 이하의 자연수
• stations의 크기: 10,000 이하의 자연수
• stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다.
• W: 10,000 이하의 자연수

입출력 예

NstationsWanswer

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다

입출력 예 #2

• 초기에, 1~6, 12~16번째 아파트에는 전파가 전달되지 않습니다.

• 3, 6, 14번째 아파트 옥상에 기지국을 설치할 경우 모든 아파트에 전파를 전달할 수 있습니다.

접근 방법

전파가 닿지 않는 부분을 빈 공간이라고 칭하겠습니다.

1. 일단 가장 먼저 생각해야 할 것이 크기가 n인 빈 공간을 채우는데 최소 몇 개의 기지국이 필요한지 알아야 합니다.

 만약 전파의 크기가 1이라면 1개의 기지국으로 (1~3)크기의 빈 공간을 채울 수 있습니다. 또한 2개의 기지국으로는 (4~6) 크기의 빈 공간을 채울 수 있습니다. 

 만약 전파의 크기가 2이라면 1개의 기지국으로 (1~5)크기의 빈 공간을 채울 수 있습니다. 또한 2개의 기지국으로는 (6~10) 크기의 빈 공간을 채울 수 있습니다. 

 즉, 전파의 크기가 w일 때 하나의 기지국으로 최대 k = (2*w + 1)의 빈 공간을 채울 수 있습니다.

이때 빈 공간의 크기가 n일 때 필요한 기지국의 수 X는 x = (n % k == 0) ? (n / k) : ((n / k ) + 1)입니다.

나머지가 0이면 몫, 0이 아니라면 몫+1입니다.

2. 빈 공간의 크기를 구해야 합니다.  

문제에서 stations[]배열이 오름차순이 되어있습니다. stations 사이의 빈 공간은 아래와 같습니다.

공간 = (stations[i + 1] - w) - (stations[i + 1] + w) - 1

만약 이러한 공간의 크기가 0보다 작거나 같다면 전파가 겹쳐 빈 공간의 없다는 의미이므로 생각하지 않습니다.

3. 추가적으로 첫 번째 건물로 부터 stations[0]의 빈 공간, stations[마지막]으로부터 마지막 건물의 빈 공간에 필요한 기지국의 갯수를 더합니다.

소스 코드

import java.util.*;
import java.lang.*;

class Solution {
  
    int N, W;
    
    //1번::크기가 n인 빈 공간에 필요한 기지국의 수
    public int howMany(int n){
        
        if(n <= 0) //기지국 설치가 필요없음
            return 0;
        
        int ret = n/(W * 2 + 1);
        return ret = (n % (W * 2 + 1) == 0) ? ret : ret + 1;
    }
    
    public int solve(int[] stations){
        
        int total = 0;
        int cnt = 0;
        
        // 1번 건물로 부터 stations[0] 사이에 필요한 기지국의 수
        total = howMany(stations[0] - W - 1);
        // stations[i]와 stations[i + 1] 사이에 필요한 기지국의 수
        for(int i=1;i<stations.length;i++)
            total += howMany((stations[i] - W) - (stations[i - 1] + W) - 1);
            
        // stations[마지막]과 마지막 건물사이에 필요한 기지국의 수
        total += howMany(N - (stations[stations.length - 1] + W));
        
        return total;
    }
    
    public int solution(int n, int[] stations, int w) {
    
        int answer = 0;
        this.N = n; this.W = w;

        return answer = solve(stations);
    }
}