SWEA [D4] 3378번: 스타일리쉬 들여쓰기

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWD3nB5q3T0DFAUZ

SW Expert Academy

오늘 보충에서 푼 문제

 

재택학습 시작 전에 풀었던 문제인디 왤케 낯선지... 오늘 강사님께서 삼성역량테스트 A 맞으려면 SWEA의 80%이상, 백준은 150문제 이상 풀어봐야 된다고 하셨다. 그에 비해서 난... 후하후하 1일 5알고리즘 해야할듯!! 

 

이번 문제는 시뮬레이션이다. 보충에서 푼 문제는 최적화를 안해줘서 수행 시간이 조금 걸린다. 친절한 문제여서 이해와 풀이는 그닥 어렵지 않았다.

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
public class Solution {
	static int p, q;
	
	static char[][] prr; //마스터 
	static char[][] qrr; //사용자
	
	
	static int[] res;	 //출력할 공간
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		
		StringTokenizer st = null;
		for (int t = 1; t <= TC; t++) {
			st = new StringTokenizer(br.readLine(), " ");
			p = Integer.parseInt(st.nextToken());
			q = Integer.parseInt(st.nextToken());
			
			prr = new char[p][];
			qrr = new char[q][];
			
			res = new int[q];
			//사용된 흔적을 판단할 수 있게 나올 수 없는 값으로 초기화
			Arrays.fill(res, -2);
			
			for (int i = 0; i < p; i++) {
				prr[i] = br.readLine().toCharArray();
			}
			for (int i = 0; i < q; i++) {
				qrr[i] = br.readLine().toCharArray();
			}
			
			//솔루션 구현
			//완전 탐색
			for (int r = 1; r <= 20; r++) {
				for (int c = 1; c <= 20; c++) {
					for (int s = 1; s <= 20; s++) {
						if(isFind(r, c, s)) {
							solve(r,c,s);
						}
					}
				}
			}
			
			
			//시간초과 나면 StringBuilder 사용하기
			System.out.print("#"+t);
			for (int i = 0; i < q; i++) {
				System.out.print(" "+res[i]);
			} System.out.println();
		}//end of for testCase
	}//end of main


	public static boolean isFind(int r, int c, int s) {
		// TODO Auto-generated method stub
		int rCnt=0, cCnt=0, sCnt=0, cnt=0; //r, c, s의 개수, 점의 개수
		int intent = 0; //들여쓰기 해야하는 값
		for (int i = 0; i < p; i++) { 
			cnt = 0;
			for (char ch : prr[i]) { //점의 개수세기
				if(ch == '.') cnt++;
				else break; //문자열에 있는 점은 들여쓰기 아님
			} 
			//실제 공백 개수
			intent = rCnt*r + cCnt*c + sCnt*s;
			if(intent != cnt) return false;
			
			//다음 줄의 rCnt, cCnt, sCnt 찾기
			for (char ch:prr[i]) {
				switch(ch) {
				case'(':
					rCnt++;
					break;
				case')':
					rCnt--;
					break;
				case'{':
					cCnt++;
					break;
				case'}':
					cCnt--;
					break;
				case'[':
					sCnt++;
					break;
				case']':
					sCnt--;
					break;
				}
			}
		}
		return true;
	}//end of isFind
	
	public static void solve(int r, int c, int s) { 
		// TODO Auto-generated method stub
		int rCnt = 0, cCnt = 0, sCnt = 0, intent = 0;
		for (int i = 0; i < q; i++) {
			
			intent = rCnt*r + cCnt*c + sCnt*s; //들여쓰기 해야하는 값
			if(res[i] == -2 || res[i] == intent) { //처음 들어가는 값이면
				res[i] = intent;
			} else res[i] = -1; //이미 값이 들어있으면.. 주의할 점 같은 값일 경우는 값 그대로

			for (char ch:qrr[i]) {
				switch(ch) {
				case'(':
					rCnt++;
					break;
				case')':
					rCnt--;
					break;
				case'{':
					cCnt++;
					break;
				case'}':
					cCnt--;
					break;
				case'[':
					sCnt++;
					break;
				case']':
					sCnt--;
					break;
				}
			}
		}
	}//end of solve
}//end of class

 

 

예전에 풀었던 풀이도 첨부한다. 사실 위에 코드랑 이론은 똑같은디 StringBuilder를 써서 실행시간을 줄였다.

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

		// 스타일리쉬 들여쓰기
		/**
		 * @author 소라
		 * ! 알고리즘을 잘 하려면 !
		 ********************************************
		 * 1. 프로그래밍 언어 문법+(가독성, 주석, 재활용, 구조화)	*
		 * 2. IDE 이클립스 활용 (자동완성, 디버깅, 템플릿)	 	*
		 * 3. 독해능력 (문제 분석)						 	*
		 * 4. 소스 코드 분석							 	*
		 * 5. 기발한 아이디어+구현 능력  ----> 생각의 절차를 옮기기   *
		 * 6. 자료구조									*
		 * 7. 최적화 : 입출력, 변수 메서드					*
		 * 기출 삼성:백준, 카카오:프로그래머스 				*
		 ********************************************/
public class Solution {
	private static int[][] m;
	private static int[][] dap;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int  TC = Integer.parseInt(br.readLine());
		for (int testCase = 1; testCase <= TC; testCase++) {
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int p = Integer.parseInt(st.nextToken()); // 마스터의 코드 줄 수
			int q = Integer.parseInt(st.nextToken()); // 나의 코드 줄 수
			
			m = new int [p][4]; // ., 소, 중, 대괄호의 개수
			for (int i = 0; i < p; i++) { 
				// 한 줄을 입력받아서
				String line = br.readLine();
				// 앞 부분에 나온 . 의 개수 구하기
				int index = 0;
				while(line.charAt(index)=='.') {
					index++;
				} // end of while
				
				//마스터 코드
				m[i][0] = index; // 자바는 가변 배열
				// 괄호의 개수는 누적처리
				if(i>0) { // 이전 값으로 초기화하기
				m[i][1] = m[i-1][1]; // 소괄호
				m[i][2] = m[i-1][2]; // 중괄호
				m[i][3] = m[i-1][3]; // 대괄호
				}
				
				for (int j = index; j < line.length(); j++) {
					line.charAt(j);
					switch(line.charAt(j)) {
					case '(': m[i][1]++; break;
					case ')': m[i][1]--; break;
					case '{': m[i][2]++; break;
					case '}': m[i][2]--; break;
					case '[': m[i][3]++; break;
					case ']': m[i][3]--; break;
					}
				}
			} // 마스터의 스타일리쉬 코드 분석 for
				
			dap = new int[q][4];
			// 내 코드 분석!!
			for (int i = 0; i < q; i++) {
				// 한 줄을 입력받아서
				String line = br.readLine();
				// 앞 부분에 나온 . 의 개수 구하기
				int index = 0;
				dap[i][0] = index; // 자바는 가변 배열
				// 괄호의 개수는 누적처리
				if (i > 0) { // 이전 값으로 초기화하기
					dap[i][1] = dap[i - 1][1]; // 소괄호
					dap[i][2] = dap[i - 1][2]; // 중괄호
					dap[i][3] = dap[i - 1][3]; // 대괄호
				}
				for (int j = index; j < line.length(); j++) {
					line.charAt(j);
					switch(line.charAt(j)) {
					case '(': dap[i][1]++; break;
					case ')': dap[i][1]--; break;
					case '{': dap[i][2]++; break;
					case '}': dap[i][2]--; break;
					case '[': dap[i][3]++; break;
					case ']': dap[i][3]--; break;
					}
				}
			}// 내 코드 분석 for
			
			
			// dap[i][0] : 초기값 -2 .의 개수가 몇개있는지
			for (int i = 0; i < q; i++) {
				dap[i][0] = -2; // 안쓰는 값 초기화
			}
			
			// 중복 순열 --> for문 중첩시 시간 확인
			for (int R = 1; R <= 20; R++) {
				for (int C = 1; C <= 20; C++) {
					for (int S = 1; S <= 20; S++) {
						if(check(R, C, S)) { // 마스터 코드가 해가 되는지 확인
							cal(R, C, S); 	 //된다면 답 배열에 저장하기
						}
					}
				}
			}
			
			sb.append('#').append(testCase).append(" 0"); //첫번째 줄의 들여쓰기는 0으로 일정
			for (int i = 1; i < dap.length; i++) {
				sb.append(' ').append(dap[i][0]);
			}
			sb.append('\n');
		}//end of testCase
		System.out.println(sb);

	}//end of main
	
	/* 내 코드에서 들여쓰기를 각 라인에 몇개씩 해야한는지 구해서 dap배열에 저장 */
	public static void cal(int R, int C, int S) {
		for (int i = 1; i < dap.length; i++) {
			int x = dap[i-1][1]*R+dap[i-1][2]*C+dap[i-1][3]*S;
			if(dap[i][0] == -2) { // 답을 구한적이 없을 경우
				dap[i][0] = x;
			} else if(dap[i][0] != x) { // 기존 값과 다른 들여쓰기 값이 생긴다면 
				dap[i][0] = -1;
			}
		}
	} // end of check
	
	
	/* 마스터 코드에서 해가 되는지 체크해서 리턴 */
	public static boolean check(int R, int C, int S) {
		for (int i = 1; i < m.length; i++) {
			if(m[i][0] != m[i-1][1]*R+m[i-1][2]*C+m[i-1][3]*S)
				return false;
		}
		return true;
	} // end of check
}//end of class