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

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

문제번호: 단체사진 찍기

풀이(java)

총 두가지의 과정으로 푼다.

모든 조합으로 줄을 세워본다. -> 백트래킹 줄을 세웠으면 조건에 만족하는지 확인한다.

모든 조합으로 줄을 세우기 위해 스택을 사용하고, 선택여부를 확인하기 위해 boolean배열을 만든다.

줄 세우기는 순열이기 때문에 백트래킹의 반복을 index = 0부터 계속 해줘야 한다!

조건에 만족하는지 판단하기 위해서 문자열을 파싱하고 '>'일때, '대상문자 두개의 인덱스 차이의 절대값 - 1'이 요구 되는 distance보다 커야 한다. 이런식으로 연산자가 '='일때와 '<'일때를 다 판단해주면 쉽게 풀 수 있다!

import java.util.*; class Solution { static Stack line = new Stack<>(); static boolean[] visit = new boolean[8]; static char[] fr = new char[]{'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'}; static int cnt; public int solution(int n, String[] data) { int answer = 0; cnt = 0; dfs(0, 8, n, data); answer = cnt; return answer; } public static void dfs(int startCnt, int endCnt, int n ,String[] data) { if (startCnt == endCnt) { if (isOk(n, data)) cnt++; return; } for (int i = 0; i < 8; i++) { if (!visit[i]) { visit[i] = true; line.push(fr[i]); dfs(startCnt + 1, 8, n, data); visit[i] = false; line.pop(); } } } public static boolean isOk(int n, String[] data) { for (int i = 0; i < n; i++) { char first = data[i].charAt(0); char last = data[i].charAt(2); char oper = data[i].charAt(3); int distance = data[i].charAt(4) - '0'; if (oper == '>' && Math.abs(line.indexOf(first) - line.indexOf(last)) - 1 <= distance) { return false; } else if (oper == '=' && Math.abs(line.indexOf(first) - line.indexOf(last)) - 1 != distance) { return false; } else if (oper == '<' && Math.abs(line.indexOf(first) - line.indexOf(last)) - 1 >= distance) { return false; } } return true; } }

from http://lee-s-k.tistory.com/3 by ccl(A) rewrite - 2021-12-04 03:02:12