[TIL] 230529 - 백준 알고리즘 문제 풀이

오늘 한 것

- 백준 알고리즘 문제 풀이
1021번 : 회전하는 큐
9012번 : 괄호

---

백준 문제풀이

1021번 : 회전하는 큐 (중상)

2023.05.30 - [알고리즘/백준] - [백준] 1021번: 회전하는 큐 (Javascript)

[백준] 1021번: 회전하는 큐 (Javascript)

문제

문제에서 제시된 연산들과 어떻게 풀어야 하는지는 구상이 됐지만 문제는 2번, 3번 연산을 결정하는 기준이였다.

패드에 한 메모들

시도 & 해결

1. 처음에는 현재 큐의 크기/2를 하여 없애려는 숫자가 반보다 크면 뒤와 가까우니 3번 연산을, 작으면 앞과 가까우니 2번 연산을 하도록 했는데 답이 이상하게 나왔다.
2. 그 뒤로는 (없애려는 값 - 첫 원소), (마지막 원소 - 없애려는 값)의 절대값을 구해서 더 작은 쪽, 즉 첫 원소와 마지막 원소와의 거리가 더 가까운 쪽의 연산을 하도록 했는데 이도 답이 이상하게 나왔다.
3. 그렇게 계속 삽질한 결과... 하나를 깨닫게 되는데 없애려는 숫자는 큐가 회전하면서 계속 위치가 이동하기 때문에 결국 없애려는 숫자 값이 중요한 게 아니라 그 값이 큐 안에 있는 위치를 알아야하구나 알게 되었다... 
4. 그래서 1번 방법에서 없애려는 숫자 ->  없애려는 숫자를 가지는 배열 속 인덱스 값, 즉 위치로 바꾸어 보았다.
5. 없애려는 숫자의 위치가 현재 배열의 크기의 반보다 작으면, 왼쪽으로 가는 게 더 효율적이니 2번 연산을, 크면 오른쪽으로 가는 게 더 효율적이니 3번 연산을 진행하도록 케이스를 나누어 주었고, 답을 얻을 수 있었다.
 

알게된 점

- unshift()연산 시 처음에는 연산 이후에 첫 원소를 넣어주었는데, 그렇게 하니 이미 unshift가 완료된 후라 이미 밀려진 후의 첫 원소가 다시 처음으로 와있어서 값이 덮어씌워지는 문제가 있었다. 그런데 찾아보니 unshift()의 값으로 비워진 첫 원소에 넣을 값을 넣어주면 정상적으로 들어간다는 것을 알게 되었다.

arr.unshift('넣어줄 값');

- 배열 속 인덱스 값을 구하려면 indexOf()를 사용하면 된다.

arr.indexOf('값');

---

9012번 : 괄호 

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

9012번: 괄호

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
const input = fs.readFileSync(filePath).toString().split('\n');

const test = Number(input[0]);

let result = "";

for (let i = 1; i<=test; i++){
    let vps = [...input[i]];

    let count = 0;

    for(let e of vps){ // element
        switch(e){
            case '(':
            count++;
            break;
            case ')':
            count--;
            break;
        }
        if(count < 0) {
            break;
        }
    }
    if(count == 0) result += "YES\n";
    else result += "NO\n";
}
console.log(result);

 
시도 & 해결

1. 이 문제는 팀원 Jun과 함께 풀었는데, 처음에는 혼자 풀어보면서 도대체 어떻게 괄호가 맞는지 확인하지? 하면서 되는 케이스와 안되는 케이스를 나열하며 공통점을 찾아보았다.
찾았던 공통점은 괄호가 짝이 맞은 후에는 ' ) ' 가 오면 무조건 NO라는 것이었긴 했지만 그 전까지 짝이 맞는지 아닌지 확인하는 방법을 알 수가 없었다. 된다고 해도 엄청난 if문만 생각났다...

2. 그 뒤로 Jun님이 주신 힌트를 바탕으로 왼쪽 괄호 카운트와 오른쪽 괄호 카운트를 세서 비교하면 되겠다 생각하고 코드를 짜보았다.

3. 처음에는 왼쪽 괄호와 오른쪽 괄호를 lcount, rcount로 따로 나눠서 셌는데 count 하나로 왼쪽은 +, 오른쪽은 - 하여 결과값을 보는 방법을 알게 되었다.
 
4. ' ( ' 와 ' ) '의 개수를 배열을 돌며 카운트해주고, 카운트 값이 음수가 되는 경우가 나오면 foreach문을 종료한다.
5. 종료 후 count값이 0이면 -> 짝이 맞으므로 "YES", 아니면 ' ) ' 이 더 나온 것이므로 "NO"를 출력해준다.

 
알게된 점

- 처음에는 forEach()문을 써서 하니 break가 먹질 않아서 Jun님께 물어봤는데 for ~ of 라는 for문을 사용하니 break가 되었다.

for (변수 of 객체) { ~~ }

- 반복할 수 있는 객체를 순회할 수 있도록 해 주는 반복문
- 반복할 때 마다 객체의 요소를 변수에 대입해 줌
* 출처

https://yjshin.tistory.com/entry/JavaScript-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-for-%EB%AC%B8-for-in-%EB%AC%B8-for-of-%EB%AC%B8

[JavaScript] 자바스크립트 for 문, for in 문, for of 문

---

일기

- 처음으로 알고리즘 문제를 처음부터 끝까지 나 혼자 풀고 정답까지 나와서 제일 올려보고 싶었던 백준 카테고리에 처음으로 글도 써보았다! ㅎㅎㅎ 한참 뒤에나 내 지식을 작게라도 공유할 수 있겠거니 했는데 이렇게나 빨리 올리게 되다니 너무 신나고 뿌듯했다,,, 이 맛에 코딩하고 알고리즘 문제 푸는군요 다들 ㅎ 알고리즘 열심히 풀어서 얼른 백준 카테고리 채워야지~~

- TIL 특강 받은 대로 문시해알 따라 써봤는데,, 역시 시간이 오래 걸린다,, 두시간 째 작성중,, 그래도 나중에 다 자산이 되겠지 시간 많은 백수일 때 열심히 써 두자 홧팅,,,