jo_cw.log

풍선 터뜨리기

Tue, 09 May 2023 09:46:15 GMT

문제

https://school.programmers.co.kr/learn/courses/30/lessons/68646

문제 설명

일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다.

임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다. 여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다.

당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에 서술된 조건대로 풍선을 터트리다 보면, 어떤 풍선은 최후까지 남을 수도 있지만, 어떤 풍선은 무슨 수를 쓰더라도 마지막까지 남기는 것이 불가능할 수도 있습니다.

일렬로 나열된 풍선들의 번호가 담긴 배열 a가 주어집니다. 위에 서술된 규칙대로 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 return 하도록 solution 함수를 완성해주세요.

제한 사항

a의 길이는 1 이상 1,000,000 이하입니다.
- a[i]는 i+1 번째 풍선에 써진 숫자를 의미합니다.
- a의 모든 수는 -1,000,000,000 이상 1,000,000,000 이하인 정수입니다.
- a의 모든 수는 서로 다릅니다.

접근

너무 큰 배열

배열의 길이가 1,000,000로 아주 커서 BFS나 DFS를 사용하면 시간 제한은 물론 재귀의 한계에 도달하거나 큐의 크기가 너무 커져 공간이 부족할 것이라고 생각했다. 따라서 완전 탐색은 시작부터 포기하고 DP에 이용할 수 있는 규칙이 있는지 찾아봤다.

한 번뿐인 기회

인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다.

이 문장에 집중해서 답이 될 수 있는 후보를 고민해봤다. 이 기회를 사용하지 않는다면 결국 이 배열 안에서 가장 작은 숫자만이 남을 것이다. 그렇다면 최솟값이 아닌 다른 숫자를 남기기 위해서는 이 최솟값과 만났을 때 이 기회를 사용해야 한다. 그렇다면 최솟값과 단 둘이 남기 위한 조건은 무엇인가?

결론

최솟값의 양 옆의 숫자는 언제든지 규칙에 따라 제거할 수 있다. 따라서 모든 풍선들은 최솟값의 옆에 오도록 풍선을 터뜨릴 수 있다. 따라서 어떤 풍선이 최솟값과 단 둘이 남기 위해서는 최솟값을 기준으로 반대편의 풍선을 모두 터뜨릴 수 있는지 확인하면 된다.

남길 풍선을 기준으로최솟값이 왼쪽에 있고 자신의 오른쪽에 자신보다 더 작은 수가 없는 경우
남길 풍선을 기준으로최솟값이 오른쪽에 있고 자신의 왼쪽에 자신보다 더 작은 수가 없는 경우

위에 해당하는 풍선의 개수를 구하면 답을 찾을 수 있었다.

예시

[-16,27,65,-2,58,-92,-71,-68,-61,-33] 다음과 같은 배열이 주어졌을 때, 최솟값은 -92이다. -16은 마지막에 남는 것이 가능하다. -16과 -92 사이에 있는 숫자는 모두 -92와 비교하여 터뜨릴 수 있다. -92 오른쪽에 있는 숫자 또한 마찬가지다.

하지만 -2는 불가능하다. 27 65와 비교해서 터뜨리는 것이 가능하지만 -16을 터뜨릴 방법이 없다.

구현

첫 시도

처음에는 2중 for문을 사용해서 확인했다.

let answer = 1;
let min = Infinity;
let min_index = -1;
for (let i = 0; i < a.length; i ++) {
  if (min < a[i]) continue;
  min = a[i];
  min_index = i;
}
for (let i = 0; i < min_index; i++) {
  let result = 1;
  for(let j = 0; j < i; j++) {
    if (a[i] > a[j]) {
      result = 0;
      break;
    }
  }
  answer += result;
}
//이하 생략

하지만 이 방법은 $O(n^2)$의 시간 복잡도를 가지기 때문에 여전히 느렸다.

개선

약간의 생각 후, 양 끝에서 최솟값으로 순회하는 동안 최솟값을 갱신한다면 그것이 바로 자신보다 작은 숫자가 반대편의 없는 경우라는 것에 도달했다.

최종 코드

function solution(a) {
      // 최솟값의 위치 탐색.
    let min = Infinity;
    let min_index = -1;
    for (let i = 0; i < a.length; i ++) {
        if (min < a[i]) continue;
        min = a[i];
        min_index = i;
    }
      // 정답에 최솟값을 포함하고 시작.
    let answer = 1; 

      // 만약 최솟값을 갱신한다면 마지막에 남을 수 있는 풍선.
      // 왼쪽에서 최솟값 위치까지 순회
    let temp_min = Infinity;
    for (let i = 0; i < min_index; i ++) {
        if (temp_min > a[i]) {
            temp_min = a[i];
            answer ++;
        }
    }
      // 오른쪽에서 최솟값 위치까지 순회
    temp_min = Infinity;
    for (let i = a.length - 1; i > min_index; i --) {
        if (temp_min > a[i]) {
            temp_min = a[i];
            answer ++;
        }
    }
    return answer;
}

$O(n)$의 시간 복잡도를 가지는 코드로 통과할 수 있었다.

후기

어떤 알고리즘을 알고 있느냐 보다는 시간 복잡도에 대해서 이해하고 어떤 방향으로 문제를 해결해야 하는지 방향을 잡는 것이 중요한 문제라고 생각한다. 제한 사항을 통해 완전 탐색이라는 선택지를 제외했고, 운좋게 규칙을 빠르게 찾아 시간이 오래 걸리지는 않았다.

[TIL] 프론트엔드 22.05.31

Thu, 02 Jun 2022 11:10:13 GMT

📚 공부한 내용

Components 구현

강의를 들으며 페이지를 구성할 때 사용할 수 있는 아주 작은 단위의 컴포넌트를 구현해봤다.

1. Avatar

여러 SNS에서 프로필 사진을 표시할 때 사용하는 Avatar 컴포넌트이다. 기본적으로 사진을 표시하는 것 이외에도 Image 객체의 onload()메소드를 사용해서 로딩 시에 추가적인 애니메이션이나 이팩트를 추가하는 방식을 접할 수 있었다.

2. Slider

와 동일한 역할을 하는 Slider 컴포넌트이다.

전체 범위를 나타내는 Rail, 현재 범위를 나타내는 Track, 사용자와 상호작용하여 범위를 변경할 수 있는 Handle 3개의 컴포넌트로 나누어 각각 구현
제어를 위해서 mousemove, mousedown, mouseup 총 3개의 이벤트를 사용
mousemove와 mouseup의 경우는 좌우로 이동하는 과정에서 Handle의 범위를 이탈 할 수 있어서 전역 이벤트로 지정
Slider 컴포넌트의 왼쪽 끝의 x좌표 offsetLeft와 드래깅 중인 마우스의 x좌표 pageX를 사용해서 Track의 길이와 Handle의 위치를 구한다.

Slider 컴포넌트를 storybook으로 테스트하는 중 마우스를 빠르게 움직이는 경우 드래그가 동작하지 않는 문제를 발견했는데 정확한 이유를 찾지 못했다.

와 비교하면 추가적인 최적화가 필요하지만 각 컴포넌트의 디자인이 자유로운 것이 유용해보인다.

3. Progress

진행상황을 나타내는 Progress 컴포넌트

props의 width 값에 따라서 로딩바가 길어지는 아주 단순한 구조이다.
시각적인 효과를 주기위해서 animation과 @keyframe css 속성을 사용

크게 복잡하진 않았지만 CSS animation과 관련된 속성들을 알 수 있었다.

!codepen[jochaewoo/embed/QWQrPov?default-tab=css%2Cresult&theme-id=dark] [ progress bar에 마우스를 올려보자 ]

4. Divider

네비게이션 바에서 메뉴를 분리할 때 사용하는 컴포넌트. styled component를 사용해서 단순하게 구현할 수 있었다.

5. Skeleton

< discode의 로딩화면 >

로딩중인 컨탠츠를 더 자세하게 나타낼 수 있는 컴포넌트. 위의 Progress에서 사용했던 animation을 이용하여 동적인 느낌을 줄수도 있다.

여러 모양의 컴포넌트를 하나의 객체에 담아 export, import 할 수 있다.
이를 이용해서 Circle Box Paragraph 등 여러 모양의 Skeleton을 하나의 객체만 import 해서 사용할 수 있다.
```
// 예시
import Skeleton from 'Skeleton'
const App = () => {
return (
  <>
    
    
  
)
}
```
6. Select

기존 에서 사용할 수 없던 placeholer를 props에 전달해서 설정이 가능하도록 구성했다.
placeholer의 경우 가장 위의 태그에 placeholer의 값을 넣고 hidden 속성을 적용하면, 가장 위에 있는 값이 노출되지만 클릭시 노출되지 않는다.
강의에서는