[JAVA] 프로그래머스 - 단체사진 찍기

문제 내용

https://programmers.co.kr/learn/courses/30/lessons/1835

코딩테스트 연습 - 단체사진 찍기

단체사진 찍기

가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다. 네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다. 사진을 찍고 나서 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해보게 되었다. 각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.

 

입력 형식

입력은 조건의 개수를 나타내는 정수 n과 n개의 원소로 구성된 문자열 배열 data로 주어진다. data의 원소는 각 프렌즈가 원하는 조건이 N~F=0과 같은 형태의 문자열로 구성되어 있다. 제한조건은 아래와 같다.

• 1 <= n <= 100
• data의 원소는 다섯 글자로 구성된 문자열이다. 각 원소의 조건은 다음과 같다.
  • 첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다. {A, C, F, J, M, N, R, T} 각각 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브를 의미한다. 첫 번째 글자는 조건을 제시한 프렌즈, 세 번째 글자는 상대방이다. 첫 번째 글자와 세 번째 글자는 항상 다르다.
  • 두 번째 글자는 항상 ~이다.
  • 네 번째 글자는 다음 3개 중 하나이다. {=, <, >} 각각 같음, 미만, 초과를 의미한다.
  • 다섯 번째 글자는 0 이상 6 이하의 정수의 문자형이며, 조건에 제시되는 간격을 의미한다. 이때 간격은 두 프렌즈 사이에 있는 다른 프렌즈의 수이다.

출력 형식

모든 조건을 만족하는 경우의 수를 리턴한다.

예제 입출력

ndataanswer

2	["N~F=0", "R~T>2"]	3648
2	["M~C<2", "C~M>1"]	0

예제에 대한 설명

첫 번째 예제는 문제에 설명된 바와 같이, 네오는 프로도와의 간격이 0이기를 원하고 라이언은 튜브와의 간격이 2보다 크기를 원하는 상황이다.

두 번째 예제는 무지가 콘과의 간격이 2보다 작기를 원하고, 반대로 콘은 무지와의 간격이 1보다 크기를 원하는 상황이다. 이는 동시에 만족할 수 없는 조건이므로 경우의 수는 0이다.

---

문제 접근 방법

문제는 {A, C, F, J, M, N, R, T} 이 친구들이 일렬로 세우는 data 배열에 제시된 조건에 맞게 세울수 있는 경우의 수를 모두 찾아 리턴하는 것이다.

 

그렇기 때문에 이문제는 백트래킹으로 풀어야한다고 생각했다.

백트래킹을 사용할때 dfs의 매개변수는

 

일렬로 세우는 배열(arr) 혹은 문자열(StringBuilder sb),

방문배열,

data(조건 배열),

깊이(인덱스)를 나타내주는 정수형 depth

 

4가지가 필요하다고 생각했다.

 

 

 

전체적인 풀이방법은 백트래킹을 안다는 전제하에

 

1. solution 함수에서 dfs를 실행한다.

2. dfs 함수를 만드는데 종료조건은 depth(인덱스) == 8 일때 종료한다.

3. 2번에서 depth == 8 일때 일렬로 세워진 친구들이 data 배열 조건에 맞는지 검사, 맞으면 경우의수 1증가

4. 종료 조건이 아닐때 for문을 이용해 {A, C, F, J, M, N, R, T} 요소값을 하나씩 arr 배열에 추가 or sb.append 하기

5. 사용한 요소는 방문처리하고 재귀호출

6. 재귀호출한 함수 종료하면 값을 원래대로 되돌리기.

 

2~6번 과정을 백트래킹 알고리즘을 사용해 반복하면 답이 나온다.

 

그리고 참고로 만약 solution 함수의 return값을 전역변수로 사용 중이라면 반드시 solution 함수 내에서 초기화를 해줘야 한다.

이거때문에 직접문제를 풀었는데 자꾸 틀려서 몇시간 고민하다가 다른사람 풀이도 봤는데 전체적인 풀이방식은 별다른게 없었다. 그래서 뭐때문인지 계속 고민했는데 전역변수 초기화 안해줘서 틀린거였다.

왜그런거냐면 나도 모른다.. 아는사람..??

 

---

풀이

첫 풀이(배열 활용)

public class takePicture {
	static String[] fr = {"A", "C", "F", "J", "M", "N", "R", "T"};
	static int cnt = 0;
	
	public static void main(String[] args) {
		int n = 2;
		String[] data = {"N~F=0","R~T>2"};
		
		solution(n,data);
	}
	
	public static int solution(int n, String[] data) {
		String[] copyFr = new String[8]; //(방문배열)fr 배열 복사해서 쓸꺼임.
		String[] arr = new String[8]; //arr배열에 fr요소값 하나씩 넣으면서 경우의수 셀꺼임.
		copyFr = fr.clone();
		cnt = 0; //초기화
		dfs(data,copyFr,arr,0); //dfs
		
		System.out.println(cnt);
		return cnt;
	}
	
	public static void dfs(String[] data, String[] copyFr, String[] arr, int depth) {
		if(depth == 8) { // 종료조건
			if(check(arr,data)) { //check함수로 arr요소들이 data조건에 만족하는지 확인
				cnt++;
			}
			return;
		}
		
		for(int i=0; i<copyFr.length; i++) {
			if(copyFr[i].equals("completion")) continue;
			
			String temp = copyFr[i]; //값 되돌리기위해 이전값 저장
			arr[depth] = temp; //요소값을 arr에 할당
			copyFr[i] = "completion";//방문처리
			dfs(data,copyFr,arr,depth+1); //재귀 호출
			copyFr[i] = temp; //값 되돌리기
		}
	}
	
	public static boolean check(String[] arr, String[] data) {
		//data의 조건을 하나씩 전부 순회하면서 하나라도 false가 안나오면
		//data의 모든 조건을 만족하게 되는것.
		for(String fullCondition:data) {
			String me = String.valueOf(fullCondition.charAt(0));//나의 요소값
			String you = String.valueOf(fullCondition.charAt(2));//상대방 요소값
			char condition = fullCondition.charAt(3);//= , > , < 중 하나
			int num = Character.digit(fullCondition.charAt(4), 10);//나와 상대방 사이에 몇명을 요구하는지
			
			int start = 0; // 내 위치
			int end = 0; // 상대방 위치
			for(int i=0; i<arr.length; i++) {//위치를 찾아주는 for문
				if(arr[i].equals(me)) {
					start = i;
				}else if(arr[i].equals(you)) {
					end = i;
				}
			}
			
			//= , < , > 에 따라 나와 상대방 사이에 몇명이 있는지 체크하는 분기문.
			if(condition=='=') {
				if(!(Math.abs(end-start) -1 == num)) return false;
			}else if(condition=='>') {
				if(!(Math.abs(end-start) -1 > num)) return false;
			}else {
				if(!(Math.abs(end-start) -1 < num)) return false;
			}
		}//for
		
		return true;
	}
}

 

 

 

다른 풀이(StringBuilder 활용)

public class takePicture2 {
	private static String[] fr = {"A", "C", "F", "J", "M", "N", "R", "T"}; //카카오 친구들
	private static int cnt = 0; // 경우의 수
	
	public static void main(String[] args) {
		int n=2;
		String[] data = {"N~F=0","R~T>2"};
		
		solution(n,data);
	}
	
	public static int solution(int n, String[] data) {
		boolean[] visited = new boolean[8]; //방문 배열
		StringBuilder sb = new StringBuilder(); //경우의수 하나하나 만들어줄 StringBuilder
		cnt = 0; //초기화
		dfs(sb, visited, data, 0); //dfs
		System.out.println(cnt);
		return cnt;
	}
	
	public static void dfs(StringBuilder sb, boolean[] visited, String[] data, int depth) {
		if(depth == 8) { //종료조건, depth가 8이되면 fr요소값 다사용한거
			if(check(sb,data)) {//이때 check가 true면 data의 조건 만족하는거 cnt증가
				cnt++;
			}
			return;
		}
		
		for(int i=0; i<fr.length; i++) {
			if(visited[i]) {continue;}//방문한건 continue
			
			visited[i] = true; //방문처리
			sb.append(fr[i]); //sb에 방문안한 fr요소값 붙이기
			dfs(sb, visited, data, depth+1); //재귀
			visited[i] = false; //되돌려 놓기.
			sb.delete(depth, sb.length()); //되돌려 놓기.
			
		}
	}
	
	public static boolean check(StringBuilder sb, String[] data) {
		String st = sb.toString();
		
		//data의 조건을 하나씩 전부 순회하면서 하나라도 false가 안나오면
		//data의 모든 조건을 만족하게 되는것.
		for(String datas: data) {
			int me = st.indexOf(datas.charAt(0)); //내 위치
			int you = st.indexOf(datas.charAt(2)); //상대방 위치
			char condition = datas.charAt(3); //=,>,< 중 하나
			int num = datas.charAt(4)-'0'; //나와 상대방 사이에 몇명을 요구하는지
			
			//= , < , > 에 따라 나와 상대방 사이에 몇명이 있는지 체크하는 분기문.
			if(condition == '=') {
				if(!(Math.abs(me-you) -1 == num)) return false;
			}else if(condition == '>') {
				if(!(Math.abs(me-you) -1 > num)) return false;
			}else if(condition == '<'){
				if(!(Math.abs(me-you) -1 < num)) return false;
			}
		}//for
		
		return true;
	}
}

 

 

---

마치며

첫번째 풀이보단 두번째 풀이가 더 효율적이다. 첫번째는 arr배열에 계속 새로운 값을 할당해주기 때문에 효율이 더떨어지는것 같다. 그리고 애초에 StringBuilder 자체가 가변하는 문자열에 유리하기 때문에 두번째 방법을 추천한다.

 

마지막으로 다 풀고도 초기화안해서 몇시간동안 고민했기 때문일까.. 백트래킹에 대해 좀더 알게된 기분?이였다 ㅋㅋㅋ.

여튼 전역변수 초기화 안해주면 왜 틀린건지 아는사람이 있을까