오늘 스터디에서 풀었던 문제는 알고리즘 스택에 대한 문제였다.
문제를 이해하는 것부터 시간이 꽤나 걸렸다,,😩
막대가 생기는 조건? 에 대해 이해하는게 굉장히 어려웠다.
처음에는 괄호 두개가 연속으로 있을때("((" 혹은 "))") 막대가 생기는 건가,, 싶었는데
그렇게 했을 때 예시로 보여주는 것과 다른 결과가 나왔다
회사에서 일을 하면서 계속 생각하고 생각한 결과,
그냥 앞에서부터 한자리씩 옮겨가며 확인하면서 괄호가 열린 부분이 막대의 시작부분이고,
닫힌 괄호가 막대의 끝 부분이라고 생각하고 적용해보니 예시와 같은 결과가 나왔다!!
(단, 열린 괄호와 닫힌 괄호가 연속으로 나온 경우("()")는 레이저의 경우이므로 제외)
public static void main(String[] args) { Scanner scan = new Scanner(System.in); String input = scan.next(); int start = 0; int out = 0; for(int i=0; i<input.length(); i++){ if(input.charAt(i) == '('){ start++; }else { start--; if(input.charAt(i-1) == '('){ out += start; }else{ out++; } } } System.out.println(out); }
변수를 선언할 때 단순히 막대의 시작 부분이라고 생각해서 변수명을 start로 잡아두긴 했지만,,
막대의 갯수? 라고 생각하면 편할 것 같다.
입력된 문자열에서 자리를 하나씩 옮겨가며 괄호가 열려 있을때는 막대의 갯수(start)를 1씩 증가시켜주고,
괄호가 닫혀 있을때는 막대의 갯수(start)를 1씩 감소시켜줬다.
이렇게 구현하면 레이저의 경우에는 막대의 갯수(start)가 결국 0이 되므로 막대의 갯수를 체크할 수 있다.
그리고 레이저가 생성되는 부분("()")에서는 잘라진 막대(out)이 생기므로 그 때의 막대의 갯수(start)를 더해주고,
막대의 끝 부분에서는 잘라진 막대 하나가 생기는 것과 같으므로 out에 1씩 더해주면 완성이다,,!
그런데,, 여기에는 함정카드가 숨어있다.
알고리즘 분류는 스택이었으나,, 스택없이 풀어버렸다,,,,,,,,,,ㅎ,,,,
