베카의에러뿌시기

LeetCode 문제 중 난이도 Easy인 Occurrences After Bigram이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

주어진 first와 second를 이용해 "first second third" 형태의 텍스트로 first바로 다음에 second가 오고 바로 뒤에 third가 오는 경우를 고려하여라.

각각의 경우에 third를 answer에 추가하고 answer를 리턴하라.

1 처음엔 text 내에 third가 몇개인지 알 수 없으므로 크기가 고정된 배열 대신 리스트를 이용하자.

2 text에 있는 단어들을 문자열 배열 words에 넣어준다.

3 words[i]가 first이고 words[i+1]이면 words[i+2]를 answer에 추가한다.

4 마지막으로 answer를 배열로 변환하여 리턴한다.

코드로 나타내면 다음과 같다.

위 코드의 시간복잡도는 O(n), 공간복잡도는 O(n)이다.

문제출처 - https://leetcode.com/problems/occurrences-after-bigram/

시작하기에 앞서 이 포스팅은 특정 보험사나 보험상품을 추천하기 위한 글이 아니라 보험 가입시 주의사항에 대해 일반적으로 알아야 할 것들을 정리한 글이다. 위 이미지에 있는 보험사들도 딱히 내가 추천하는 보험사라기보다는 생각나는대로 넣은 이미지 사진이다. 글쓴이는 특정 보험사의 직원이 아니며 매년 달라지는 보험상품들의 세세한 계약조건에 대해서는 잘 모른다. 각 보험상품에 대한 자세한 설명은 보험사 홈페이지나 담당 설계사를 통해서 확인바란다.

<보험 호갱 안되는법 시리즈>

· 보험 가입시 유의사항 1편(현재글)

· 보험 가입시 유의사항 2편(클릭)

· 보험 가입시 유의사항 3편(예정)

보험이란 노동력에 의하여 생계를 유지하고 있는 자가 질병/부상/사망 등의 사고로 인하여 일을 하지 못하게 되었을 경우를 대비해 다수의 사람이 미리 공통준비재산을 형성하고, 사고를 당한 사람이 이것으로부터 재산적 급여를 받는 경제제도이다.

보험은 주식/펀드/부동산 등 재산을 불리기 위한 투자가 아니라 예기치 못한 사고로 재산이 마이너스가 되는것을 막기 위해 미리 대비하는 것이다. 쉽게 말해 '어느날 갑자기 인생이 좆되지 않기위해' 대비하는거라고 보면 된다.

먼저 보험 관련 반드시 알아야 할 기본적인 용어부터 정리하자.

보험료 : 보험 계약자(내)가 보험 회사에 매달 지불하는 금액

보험금 : 보험기간 내에 보험사고가 발생하여 보험회사가 보험수익자(나)에게 지급하는 금액

주계약 : 해당 상품의 기본이 되는 계약

특약 : 주계약에 추가로 부수적인 보장을 원하는 경우 추가로 넣는 계약조건

납입기간 : 보험료를 내는 기간(20년납, 30년납 등)

보험기간 : 보험사가 보험계약자(나)에게 보험금을 지급할 책임을 지는 기간

만기 : 보험기간이 끝나는 시점

납입면제 : 납입기간 중 불의의 사고 또는 질병으로 인하여 보험료 납입이 곤란한 경우 보험의 보장은 유지하면서 납입을 면제해줌

갱신형 : 기간을 가지고 n년마다 갱신시점에서 보험료가 오름

비갱신형 : 납입기간동안 보험료가 오르지 않는 상품

만기환급형 : 만기에 보험료를 돌려받을 수 있다.

순수보장형 : 만기에 보험료를 돌려받을 수 없다.

주계약은 말 그대로 해당 보험의 주요 계약이다. 보험상품은 주계약(필수)+특약(선택)으로 이루어진다.

만기시 보험료를 돌려받는다는 말에 만기환급형이 좋아보이지만 당연히 보험료가 비싸다. 그리고 물가상승률을 고려했을 때 내가 낸 보험료를 만기시점에 돌려받는 것은 별 의미가 없다. 위에서 말했듯 보험은 위험에 대비하기 위한 수단이므로 순수보장형이 낫다.

납입기간은 최대한 길게 하는것이 좋다. 같은 금액을 20년동안 내는것보다 30년동안 나눠서 내는것이 매달 내는 보험료의 부담이 적고 중간에 납입면제가 발생할 확률도 높아진다. 각 보험사 별로 가입시 납입면제 기준을 확인하자.

납입기간과 보험기간이 다름에 주의하자. 보험료 납입기간이 끝났다고 보장을 더이상 받지 못하는것이 아니다. 31살에 20년납 100세만기 암보험을 가입했다면 31~50살까지 20년동안 보험료를 납부하고 보장은 100살까지 받을 수 있다. 헷갈리지 말자!

※ 보험 가입시 유의사항 ※

보험은 완성된 상품을 구매하는것이 아니라 설계라는 과정을 통해 조합된 담보구성에 가입하는것이다. 따라서 나에게 맞는 설계가 중요하다. 보험 설계사에게 사기당했다 호갱당했다 라고 하는 경우가 이런 경우이다. '나에게 불필요한 상품에 가입하는 것'

지인 중 20대 초반에 사망보험금 3억짜리 보험을 가입해 5년이상 납입하고 있었던 경우를 본 적이 있다. 결혼도 하지 않은 24살의 여성이 3억짜리 사망보험금이 필요할까? 당연히 절대로 아니다. 사망진단금은 보통 가정의 생계를 책임지는 가장이 불의의 사고로 사망한 경우 남겨진 가족들의 생계를 위한 자금 대비를 위함이다.

보통 보험료의 합계는 본인 월소득의 5%이하가 적당하다고 본다. 특히 사회초년생의 경우 보험료로 너무 많은 금액을 지출하면 전세자금/결혼/자동차구입 등에 필요한 목돈마련이 늦어지게 된다. 게다가 무리한 보험료 납입은 해지의 지름길이다.

보험은 만기까지 유지하지 못하면 해지환급금이 거의 없거나 내가 납입한 보험료보다 턱없이 적은경우가 대부분이다. 자신의 재정상황에 맞게 가입하고 절대 깨지 않는것을 추천한다. 또한 처음에 가입할 때 꼼꼼하게 따져서 들고 일단 들고 나서는 생각하지 말자. 가장 바보같은 경우가 보험 가입후 네이버에 내가 가입한 상품을 검색해서 안좋은 말을 보고 댓글로 상담받는 것이다. 거기에는 전 보험사 상품 판매가 가능한 설계사들이 많다. 무슨 말이냐면 내가 A회사 a상품을 가입했으면 B회사 b상품으로 갈아타라고 할것이고 b상품을 가입했다면 c상품으로 갈아타라고 꼬드긴다. 내가 가입한 상품도 네이버에 검색하면 가장 첫번째로 뜨는 글이 "ㅇㅇ보험.. 6년동안 납입했는데 속았습니다."라는 글이다...ㅋㅋ

보험의 종류는 정말 많다. 어떤 보험을 가입해야 할까?

일반적으로 아래와 같은 순서로 가입한다. 가입한 보험이 없다면 아래의 순서대로 내가 가지고 있지 않은 보험에 가입하면 된다.

1 실손의료보험(=실비,실손) > 2 암/수술비보험 > 3 기타

실비보험은 병·의원 및 약국에서 실제로 지출한 의료비를 최대 90%까지 보상하는 보험으로 가입자가 실제 부담한 의료비만을 보장하는 보험상품이다. 중복보장이 되지 않으며 A보험사, B보험사에 각각 가입했다고 하더라도 보험금은 내가 지출한 의료비 내에서만 받을 수 있다.

실비는 나도 모르는 사이에 부모님이 들어놓으신 경우도 꽤 있다. 아직 들지 않았다면 점점 조건이 안좋아지고 있으니 빠른 시일 내에 가입하도록 하자. 실비보험은 전부 갱신형이다. 가끔 갱신 없는 실비라며 추천해주는 경우가 있는데 적립보험료를 높여(=처음부터 보험료가 비쌈) 갱신이 안되는것 처럼 보일뿐이다. 20대후반~30대초반 여성 기준 단독실비 보험료는 약 1만원 정도이다. 보험사별 차이는 크지 않으니 특약 없이 단독실비 가입한다고 하면 된다. 그리고 예전에 실비보험에 가입한 사람이라면 지금보다 조건이 훨씬 좋으니 절대 깨지 않도록 하자.

암/수술비 보험, 진단금/치료비/입원비 차이, 부담보 등에 대해서는 2편에서 다루도록 하겠다.

보험 가입시 유의사항 2편 - 암보험 가입하기

이 포스팅이 도움이 되었다면 아래 공감♡ 버튼을 누르자.

LeetCode 문제 중 난이도 Easy인 Flipping an Image이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

2진 행렬 A를 입력으로 받아 수평으로 뒤집은 다음 숫자를 반대로 바꾸고 결과를 반환하라. 

수평으로 뒤집는것은 각 줄의 이미지가 뒤집히는 것이다. 예를들어 [1,1,0]을 수평으로 뒤집으면 [0,1,1]이 된다.

반대로 바꾸는것은 0은 1로, 1은 0으로 변환하는것이다. 예를들어 [0,1,1]은 [1,0,0]이 된다.

설명이 복잡해 보일때에는 Example을 보자. 우리가 해야 할 일은 입력 배열을 좌우로 뒤집은 뒤 0은 1로, 1은 0으로 바꿔서 반환해주기만 하면 된다.

위의 예시의 첫번째 행을 보자. A[0][2]을 temp에 넣고 A[0][2]에는 A[0][0]의 값과 1의 XOR 연산값(0을 1로, 1을 0으로)을 넣어주자. 위의 예시에서는 가운데 열인 A[0][1]은 temp에 넣을 필요 없이 A[0][1]^1만 해주면 되지만 열이 짝수인 경우에는 temp에 넣고 값을 서로 바꾸어주어야 한다. 반복문으로 전체 행에 연산해준다. XOR연산을 잘 모른다면 아래 비트연산자 포스팅을 참고한다.

2019/03/16 - [프로그래밍문제풀기] - 비트연산자란?

이 방법의 시간복잡도는 O(n)이고 공간복잡도는 O(1)이다.

문제 출처 - https://leetcode.com/problems/flipping-an-image/

LeetCode 문제 중 난이도 Easy인 Lemonade Change이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

레몬에이드 가판대에서 각 레몬에이드의 가격은 $5이다.

레몬에이드를 사기 위해 줄에 선 손님들은 순서대로 한명씩 주문한다. 각각의 손님들은 $5, $10, $20 셋 중에 하나의 지폐를 내고 레몬에이드를 하나씩 주문한다. 정확하게 거스름돈을 돌려주어서 순수한 거래는 손님이 $5씩 지불한게 되어야 한다.

처음에 잔돈 없이 시작해서 모든 손님들에게 정확한 거스름돈을 돌려줄 수 있는 경우에만 true를 리턴하라.

가지고 있는 지폐 수를 체크하기 위해서 5달러 지폐의 수는 five, 10달러 지폐의 수는 ten이라는 변수에 넣는다. 20달러는 거스름돈으로 나갈 일이 없으므로 체크할 필요 없다. 5달러 지폐를 받으면 five+1, 10달러지폐를 받으면 ten+1을 해준다.

20달러 지폐를 받은 경우에는 두가지로 나눌 수 있다. 거스름돈을 10+5 합쳐서 줄 수도 있고 만약에 10달러가 없으면 5+5+5로 줄 수도 있다. 가지고 있는 5달러와 10달러 지폐가 음수가 되는 때가 있다면 거스름돈을 정확하게 돌려줄 수 없는 것이다.

한가지 유의할 점은 if(five<0 || ten<0) return false는 for문 안에 있어야 한다. 그렇지 않으면 지폐수가 음수였다가 다음 손님들에게 지폐를 받는, 실제로 존재할 수 없는 경우에도 true를 리턴한다.

LeetCode 문제 중 난이도 Easy인 Student Attendance Record I이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다

  문제해석

학생의 출석기록을 의미하는 String을 입력으로 받는다. 출석기록은 3가지 문자로만 이루어져 있다

A : 결석

L : 지각

P : 출석

결석이 한번을 넘거나 연속으로 두번 넘게 지각하는 경우가 없어야만 상을 받는다. 해당 학생이 상을 받을 수 있는지 없는지 리턴하라.

이 문제는 정규식을 이용해 1줄의 코드로 풀 수 있다. 정규식에 대해 잘 모른다면 아래 포스팅을 참고하자. {n}은 n번 반복이라는 뜻이다.

2019/03/30 - [프로그래밍문제풀기] - JAVA 정규표현식 (Regular expression)

두번째 방법은 배열을 탐색하면서 A가 1번을 넘는지, L이 2번 넘게 연속인지 확인하는 것이다.

<폰 싸게사는법 시리즈>

1편 호갱 안당하는법(현재글)

2편 자급제폰과 알뜰요금제(클릭)

이 포스팅에서는 자급제폰이나 공기계구입+알뜰통신사 등에 대해서는 다루지 않는다. 그건 2편에서 다루기로 하고 일반적으로 휴대폰을 가장 많이 구매하는 루트인 SK/KT/LG의 통신사 핸드폰 싸게사는법에 대해 써보도록 하겠다.

일단 몇가지 간단한 용어들을 확인하고 넘어가자. 공시지원금 선택약정 등은 뒤에서 자세히 설명한다.

현금완납 : 휴대폰 구매시 기기값을 현금으로 한번에 납부하는것

할부 : 기기값을 할부로 구매

약정기간 : 내가 12개월/24개월 동안 이 통신사를 계속 이용하기로 약속

할부기간 : 기기값을 나눠서 내는 기간

할부원금 : 할부거래로 구매시 내가 내는 기기값

부가서비스 : 판매점에서 요금제 외에 추가적으로 가입시키는 서비스

페이백 : 휴대폰을 구매하면 돈을 줌

우리가 새 폰을 살 때 보통 다음과 같은 과정을 거친다.

1 위약금 확인

현재 쓰고있는 핸드폰으로 114에 전화를 걸어서 직원연결 후 남은 약정기간과 위약금을 확인한다. 약정기간이 많이 남았다면 꼭 필요한 경우를 제외하고는 새 휴대폰 구입은 잠시 미뤄두자. 만약 남은 약정기간이 6개월이하라면 기변으로 구매해야 위약금을 물지 않는다. 기변이란 내가 쓰던 통신사 그대로 기기변경하는것을 말한다. 기변과 기기변경은 같은말이다.

번호이동,번이는 통신사를 변경하는것을 말한다. 번호이동이라는 이름 때문에 번호가 바뀌는건가 많이들 헷갈려하는데 쓰고있는 휴대폰 번호는 바뀌지 않는다. 통신사만 바뀐다.

보통 번호이동이 기기변경보다 15-20만원정도 저렴하지만 인터넷할인, 가족할인등으로 묶여있는 경우에는 번이보다 기변이 나은 경우가 있다. 예를 들어 SK는 온가족의 SK 가입년수를 합쳐 30년이 넘으면 요금을 50%할인해 준다. 이경우에는 기변이 더 유리하다.

2 휴대폰 모델 고르기

최신플래그쉽은 아무래도 그만큼 비싸다. 출시된지 1-2년정도 된 휴대폰들은 상대적으로 저렴하면서도 스펙좋은 모델들을 구할수가 있다. 안드로이드vs아이폰, 삼성vs엘지 등 이건 개인의 취향에 따라 선택하면 된다. 나는 폰 기종은 아무래도 상관없다 싶으면 약정시 기기값이 0원인 모델(페이백까지 받을수 있으면 더 좋고)을 고르면 된다. 사려는 폰을 골랐으면 공시지원금과 선택약정 중 어떤걸 골라야 유리한지 확인해보자.

공시지원 선택약정할인 차이는 휴대폰 기기값을 할인받느냐 아니면 매달내는 요즘을 할인받느냐의 차이이다. 일반적으로 안드로이드는 공시지원금이, 아이폰은 선택약정할인이 유리하다. 그리고 요금제를 6만원이상 고액요금제를 사용한다면 선택약정이 유리하다.

선택약정은 어떤 요금제든 25%를 할인이고 휴대폰 모델별 공시지원금은 아래 사이트에서 확인 가능하다. 단통법 시행으로 전국 공시지원금이 정해졌지만 실제로는 그 가격보다 싸게 살 수 있으니 참고만 하자.

http://www.smartchoice.or.kr/smc/smartlife/dantongList.do

그러면 어떻게 휴대폰을 더 싸게 구입할 수 있을까?

예를 들어 100만원짜리 휴대폰의 공시지원금이 30만원으로 정해져있다. 원래는 전국 모든 매장에서 70만원에 팔아야 한다. 그런데 핸드폰가게는 휴대폰을 팔면 20만원의 리베이트를 받는다. 그러면 받을 리베이트에서 고객에게 10만원을 지원해주더라도 10만원의 이득이 생긴다. 이걸 이용해서 현금완납으로 핸드폰 싸게사는법 이 가능한 것이다. 원래 고객인 나에게 70만원을 받았어야 하는데 실제로는 60만원만 받은 뒤 계약서에 현금완납이라고 적는것이다. 페이백도 같은 원리로 가능한 것이다. 한가지 유의할점은 불법이기 때문에 페이백을 당일에 그자리에서 받는게 아니라면 믿을만한 게 못된다. 주기로 해놓고 안줘도 어떻게 강제할 방법이 없다. 한달뒤에 계좌로 페이백 해주겠다 하는곳은 그냥 거르자.

3. 시세확인

내가 사려는 휴대폰의 시세를 온라인으로 확인하자. 뽐뿌나 알고사, 네이버밴드 등을 눈팅한다. 여기서 말하는 시세란 보통 69요금제를 쓸 경우의 현금완납 시세를 말한다. 가격은 계속 달라지므로 구매하기 하루이틀 전에 확인하면 된다.

※ 눈팅전 은어확인 ※ 대부분 위에서 다룬 용어들의 줄임말이나 자음이라고 보면 된다. 어렵지 않게 유추할 수 있을 것이다.

현완,현아,ㅎㅇ : 현금완납

스크,ㅅㅋ : SK

크트,ㅋㅌ : KT

르그,ㄹㄱ : LG

ㅅㅍ,스팟,대란 : 좋은조건으로 구매할수있는 가격이 뜸

ㄱㅂ : 기기변경(기변)

ㅂㅎㅇㄷ,ㅂㅇ : 번호이동(번이)

욕 : 요금제

선약,ㅅㅇ : 선택약정

ㅍㅇㅂ : 페이백

ㄱㅂ,ㄱㅂㅌㅋㄴ : 강변테크노마트

ㅅㄷㄹ,ㅅㄷㄹㅌㅋㄴ : 신도림테크노마트

ㅂㅁ,부무 : 부가서비스X

ㅂㅇ,부유 : 부가서비스O

갤럭시는 우주, 아이폰은 사과 등으로 부르기도 한다. 이것도 보다보면 금방 적응할 것..

<예시>

s20 ㅅㅋㄱㅂ ㅎㅇ 29면 괜찮나요? > 갤럭시s20 SK 기변 현금완납 69만원이면 괜찮은 가격인가요?

아이폰11 르그번이 599욕 선약 얼만가요? > 아이폰11 LG 번호이동 599요금제로 선택약정하면 할부금 얼마나오나요?

뽐뿌 휴대폰 포럼

http://www.ppomppu.co.kr/zboard/zboard.php?id=phone

알고사 자유게시판

http://rgo4.com/free

4 구매

자 이제 현금을 뽑아서 오프라인으로 구매하러 가보자. 신도림이나 강변이 가장 싸긴 하지만 잘 모르고 가면 호갱잡힐 수도 있다. 그리고 멀리까지 가서 발품파는 시간도 결국 돈이기 때문에 내가 확인한 시세에 5~10만원 정도를 더 얹어서 동네가게에서 사는것도 아주 나쁘진 않다.

테크노마트에 가면 에스컬레이터에서 내리자마자 폰팔이들이 말을 걸 것이다. "잘해드릴게요" "어떤거 보러 오셨어요?" 등등... 눈이 마주치면 왠지 그 가게에서 사야될것 같은 느낌이 든다. 하지만 이들은 게임으로치면 npc라고 보면 된다. 그냥 무시하고 지나가자. 물론 가서 말을 걸어도 된다. 어차피 나는 오늘 수많은 npc들중 하나에게 휴대폰을 구매하러 왔으므로.

내가 온라인으로 확인한 갤럭시S9+의 SK번이 시세가 37만원이라고 치자. 그러면 아무 npc한테나 다가가서 "갤럭시S9+ SK번이 현완 어디까지 가능해요?"라고 물어본다. 이때 일단 앉아보라거나 차한잔 준다고 하는데 그냥 쌩까고 가격이나 빨리 알려달라고 하자. 나는 앉았다가도 잘 일어서는 사람이지만(ㅋㅋ) 보통 앉아서 차한잔 마시면 일어나서 나오기가 어려우니 그냥 서서 바로 물어보면 된다.

그러면 폰팔이들이 대답 대신 계산기에 숫자를 찍어준다. 말을 하지 않는 이유는 폰파라치들의 녹취를 피하기 위해서이다. 계산기에 찍어주는 가격이 35일수도, 37일수도 40일수도 있다. 가게마다 가격이 약간씩 다르다. 알겠다고 하고 다른가게에서 반복한다. 최소 10군데 정도 돌아보고 가장 저렴한 곳에 가서 구매하면 된다. 이때 계약서를 꼭 확인하자. 할부원금이 0원이라고 써있어야 한다.

가끔은 69요금제 대신 79요금제를 사용하면 더 싸게 해준다고 하는 경우가 있다. 높은 요금제일수록 판매자에게 떨어지는 리베이트가 크기 때문에 그렇다. 원래 고액요금제를 쓰는 사람은 상관없겠지만 낮은 요금제를 사용하던 사람은 해당 요금제를 6개월 사용함으로써 추가적으로 드는 요금제를 계산해보고 결정하면 된다. 예를 들어 내가 평소에 59요금제를 사용하는데 79요금제를 6개월간 써야 한다면 2만원X6개월=12만원의 추가지출이 생긴다. 59요금제의 공시지원금보다 79요금제의 공시지원금이 12만원이상 싸지 않다면 굳이 높은 요금제를 사용할 필요가 없다.

5 카드할인을 해야하는가?

폰팔이들이 신용카드를 만들라고 하는 경우가 있다. 나쁜건 아니다 진짜 할인이 되긴 된다. 하지만 여기서 중요한것은 카드할인은 통신사나 판매점에서 해주는 할인이 아니라는 것이다. 자기가 깎아주는 것인양 말하는 폰팔이는 거르면 된다. 카드할인은 일정 금액 이상 실적을 채우면 카드사에서 해주기 때문에 그날이 아니더라도 나중에 언제든 내가 해당 신용카드를 카드사에서 발급받아서 할인받으면 된다.

다음글 : 폰 싸게사는법 2편 - 자급제폰과 알뜰요금제

LeetCode 문제 중 난이도 Easy인 Remove Outermost Parentheses이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

유효한 괄호 문자열은 비어있는 (""), "(" + A + ")", 또는 A + B이다. 여기서 A와 B는 유효한 괄호 문자열이며, +는 문자열의 연결을 나타낸다. 예를 들어 "", "()", "(())()", "(()(()))"는 모두 유효한 괄호 문자열이다.

유효한 괄호 문자열 S가 비어 있지 않고, A와 B가 비어 있지 않은 유효한 괄호 문자열을 사용하여 S = A+B로 분할할 수 있는 방법이 없으면 원시적이라고 한다.

주어진 유효한 괄호 문자열 S의 원시분해를  S = P_1 + P_2 + ... + P_k라 하자. (P_i는 원시적인 유효한 괄호 문자열)

S의 원시 분해에서 가장 바깥쪽 괄호를 제거한 모든 원시 문자열을 반환해라.

가장 바깥쪽 괄호인지 체크하기 위해서 open이라는 변수를 사용한다. i번째 인덱스가 여는괄호이면 +1, 닫는괄호이면 -1을 해준다. open이 양수면 괄호가 열린상태이다.

open이 0일때의 여는괄호와 1일때의 닫는괄호가 가장 바깥쪽 괄호일 것이다. 가장 바깥쪽 괄호를 제거하기 위해서 open이 0일때 여는괄호와 open이 1일때 닫는괄호가 아닌 문자들만 sb에 덧붙인다.

이 풀이의 시간복잡도는 O(n)이고 공간복잡도도 O(n)이다.

문제출처 - https://leetcode.com/problems/remove-outermost-parentheses/

LeetCode 문제 중 난이도 Easy인 Arranging Coins 이다. 문제링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

총 n개의 동전을 가지고 k번째 줄에는 k개의 동전이 오도록 계단모양으로 배열해보자.

주어진 n으로 만들 수 있는 온전한 계단의 최대 라인수를 찾아라.

n은 음수가 아닌 정수로 부호가 있는 32비트 정수의 범위내에 있다.

k번째까지 계단모양을 채우려면 동전의 갯수가 1+2+3+...+k개 필요하다. 1부터 k까지의 숫자의 합은 k(k+1)/2이다. 그러면 n≥k(k+1)/2을 만족하는 k를 찾아야 한다. 중학생 때 배운 완전제곱식을 이용하여 k에 관한 형태로 바꾸어준다.

결과적으로 k는 2n+0.25의 제곱근에서 0.5를 뺀 값보다 작거나 같을 것이다. 구하려는 값은 해당 부등식을 만족하는 자연수 k의 최댓값이므로 좌변의 식에서 소수점을 버림하면 자연수 k의 최댓값을 구할 수 있다. 입력값 n은 정수만 담을 수 있는 int 자료형이므로 소수점 계산을 하기 위해 double 자료형을 이용한다. 코드로 작성하면 다음과 같다.

double 자료형이 익숙하지 않다면 삐멜소프트웨어 엔지니어 - 자바 변수와 자료형(float,double) 포스트를 참고하자.

잘 돌아갈 것 같지만 문제가 하나 있다. 문제에서 n은 32-bit signed integer라고 하였다. 이게 무슨 말이냐 하면 32비트 중 가장 첫번째 비트는 부호비트로 쓰인다는 것이다. 32-bit signed integer로 나타낼 수 있는 범위는 -2,147,483,648 ~ 2,147,483,647이다. 삐멜소프트웨어 엔지니어 - 자바 변수와 자료형(byte,short,int,long)

input으로 받는 n에 2를 곱한 값이 2^31 이상이면 맨앞의 sign bit가 1이 되어 음수로 바뀐다. 이 문제를 해결하기 위해 long자료형을 이용하자. 아래는 이해를 돕기 위한 코드고 실제로 사용할 때에는 L만 붙여주면 자동으로 long자료형으로 바뀐다.

문제 해결 완료!

시간복잡도는 O(1), 공간복잡도는 O(1)이다.

문제출처 - https://leetcode.com/problems/arranging-coins/

LeetCode 문제 중 난이도 Easy인 Contains Duplicate이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

정수 배열을 입력값으로 받아 해당 배열이 중복값을 포함하고 있는지 판별하라.

아무 값이나 배열 내에서 두번 이상 나타나는 값이 있다면 true를 리턴하고 모든 요소가 유일하다면 false를 리턴해라.

첫번째 방법은 배열을 정렬한 후 앞뒤 값을 비교하는 것이다. 이전에 포스팅한 Single Number 문제의 첫번째 풀이법과 원리가 같다.

2019/03/16 - [프로그래밍문제풀기] - [코딩연습] Single Number 하나뿐인 숫자 찾기

정렬하는데 드는 시간 O(nlogn), 탐색하는데 드는 시간 O(n)으로 시간복잡도는 O(nlogn)이고 추가적인 메모리 사용이 없으므로 공간복잡도는 O(1)이다.

두번째 방법은 Set 자료구조를 이용하는 것이다. Set은 중복된 데이터를 허용하지 않는 집합이다. 만약 nums에 중복된 값이 있다면 nums의 길이와 numset의 사이즈가 다를 것이다.

ex) nums = [3,7,7,8,6] 일 경우 nums.length=5, numSet.size()=4

이 방법은 배열을 한번만 탐색하므로 시간복잡도는 O(n)이지만 numSet이라는 추가적인 공간을 사용하므로 공간복잡도는 O(n)이다.

문제 출처 - https://leetcode.com/problems/contains-duplicate/