Algorithm

참 오래 걸렸던 문제다.. 그렇게 어려운 문제는 아닌것같은데 아직 자료구조와 코드 구현에서 미숙하다는 것을 느꼈다. 일단 이 문제가 큐 자료구조를 이용해야 한다는 것을 알아야한다. 문제의 뱀 이라는 게임 내용을 보면 1초에 한번씩 뱀은 움직인다. 뱀은 움직일때 머리를 움직이고자 하는 칸으로 늘려서 이동한다. 그리고 다시 원래 있던 칸의 꼬리를 줄인다. 사과를 만나면 몸통 길이가 1칸 늘어난다. 어딘가에 넣고 다시 빼야 한다. 넣고, 빼는 형태로 문제를 풀어야 할때는 스택, 큐를 떠올려야 한다. 그럼 이 문제는 왜 큐를 사용해야 하는지 알아보자. 뱀의 이동 방식이 이렇기 때문에 큐를 이용해야 한다. 물론 리스트로 구현해도 문제를 풀수는 있다. pop(0)으로 꺼내면 되지만 이렇게 되면 시간복잡도가 O(n)..

규칙을 생각해보자. 1924 라는 숫자가 주어졌을때 k개를 어떻게 지워야 가장 큰 수가 나올까? k개 만큼 지웠을때 가장 왼쪽에 있는 숫자가 주어진 숫자중에서 가장 큰 수이면 된다. 여기선 9가 가장 왼쪽에 오면된다. 그렇다면 9가 왼쪽에 오게 하려면 어떻게 해야 할까? 9가 위치한 왼쪽 인덱스와 비교했을때 9가 더 크면 왼쪽 인덱스는 지우고 9는 남겨둔다. 나머지 2와 4중에서 2를 지우려면 어떻게 해야 할까? 컴퓨터는 사람이 아니므로 딱 보고 2를 지울 수는 없다. 어떤 특정한 규칙을 코드화 해주어야 한다. 규칙화 해보자. 2와 4를 비교했을때 4가 더 큰 수 이므로 작은 수인 2를 지워주면 된다. 아! for문을 돌면서 인덱스가 자신의 왼쪽의 인덱스보다 크면 왼쪽 인덱스를 지우고 그렇지 않다면 그냥..

알고리즘 문제 풀이시 규칙을 찾는 습관을 들여보자. 쇠막대기는 레이져를 만나면 그 개수만큼 잘리고 총 개수에 더해진다. 쇠막대기의 시작은 '(' 쇠막대기의 끝은 ')' 레이져는 '()' 쇠막대기가 몇개인지 파악해야 한다. 레이져를 만나면 현재까지 '(' 로 표시된 쇠막대기 만큼의 개수가 추가된다. 쇠막대기가 몇개인지 파악해야 하므로 '(' 를 어딘가에 저장해야 한다. 쇠막대기는 항상 끝나는 지점 ')' 이 존재하는데 끝이나면 해당 쇠막대기는 저장되어있는 곳에서 제거 되야 한다. 어딘가에 저장해야 하고 제거 해야 한다면 stack과 queue를 떠올려야 한다. 쇠막대기가 제거 될때에는 저장되어있는 곳에서 가장 마지막에 저장된 '('가 제거 된다. (가장 인접한 '('가 방금 들어온 ')'의 한몸이므로) 가..

풀이

풀이

풀이

내 풀이